改进双向启发式搜索算法及其车载导航仪中应用

此外，经过实验发现，如前向搜索的步数和后向搜索的步数不同，则算法的总的搜索节点数增加。因此两个方向上的搜索步数应相同，然后切换。但搜索步距过小或过大，也会增加总搜索量。最后定下的切换标准是，每个方向搜索20步后切换方向。此外，前向搜索估计费用函数hl'n定义为从当前节点n到终点的欧氏距离，后向估计费用函数h2' n定义为从n到原节点的欧氏距离。由于这两个距离均小于从n到目标节点或原节点的路径的实际距离，因此hl'n和h2'n满足可纳性。

2.3 算法流程

改进的双向启发式搜索算法主要流程如下：

(1)把原节点移入前向CLOSE表，即令flagl原节点＝scanned，其费用gl原节点＝0，其它节点的费用为无穷。

(2)对原节点所有后继节点i进行如下操作：

·判断路径(原节点，I)是否限制路段，是处理下一个后继节点，否则继续；
·计算i的费用f1I ＝g1 I+hl'i；
·置i的搜索状态flag1 i＝labbled；
·把i的后向指针指向原节点，即link1 i＝原节点；
·把i插入OPEN1表，即insert1 i。

(3)判断OPEN1表是否为空，若为空提示出错，算法停止；否则从OPEN1表中移出费用值f1最小的节点iNODEmin，令节点i的搜索状态flag1 iNODEmin＝scanned，判断iNODEmin是否满足搜索终止条件。若满足跳转至(7)，否则对iNODEmin的所有后继节点i进行如下操作：

·判断路径(iNODEmin，I)是否限制路段，是处理下一节点，否则继续；
·计算i的费用f1 i＝g1 I+h1'i；
·若节点i的搜索状态flag1 i＝unlabbled，则令其费用f1 i＝g1 I+h1' i，link1i＝iNODEmin insert1 i；
·如果节点i的flag1 i＝labbled，计算节点i新的费用g1'I ＝g1 iNODEmin+从iNODEmin到i的实际费用，若g1' I ＜g1 i，令g1 i＝g1'I ，link1 i＝iNODEmin，decrease1 i；否则继续。
·若flag1 i＝scanned，计算g1'i ＝g1 iNODEmin+从iNODEmin到i的实际费用，若g1' i＜g1 i，令g1 i＝g1' i，link1i＝iNODEmin，flag1 i＝labbled，inertl i；
·判断前向搜索是否进行了20步，是跳转至(4)(第一次切换)或(6)(第二次以后的切换)，否则跳转至(3)。

(4)同(1)，只是对CLOSE2操作；

(5)同(2)，只是对OPEN2和CLOSE2操作；

(6)同(3)，只是对OPEN2和CLOSE2操作，切换时跳转至(3)；

(7)计算最优路径的费用，分别从搜索停止节点到原节点和从搜索停止节点到目标节点回朔，报告解路径。上述流程中(1～3)步为前向搜索，(4～6)为后向搜索。

3 试验结果及结论

作者用C语言实现了双向启发式搜索算法和其它三种算法，并用约有10000个节点的美国纽约地图进行了大量路径规划试验。试验的部分数据如表1所示。

表中的数据除起止节点外，为相关算法的搜索节点数，括弧中数据为一次测试中该算法的搜索点数少于改进的迪杰斯特拉算法的搜索点数的百分比。大量试验统计表明，启发式搜索算法的搜索空间比改进的迪杰斯特拉算法少1.5%，双向搜索算法的搜索空间比改进的迪杰斯特拉算法减少26.6%，双向启发式搜索算法的搜索空间比改进的迪杰斯特拉算法少28.0%。算法运算时间与搜索点数成正比。双向搜索的效果较好，启发式的效果较差。主要原因是试验地图数据库给出的节点坐标是经纬度，估计费用直接用两点的经纬度算出，其值很小，所以引导的效果不好。进行坐标变换后，启发式的效果应有比较大的改善，双向启发式搜索算法的速度会更快。

算法程序全部用C语言编写，所用功能模块均以函数的形式给出，以便移植到基于WindowCE的硬件平台。总之改进的双向启发式搜索算法快速高效，已经成功用于正在开发的车载导航仪。