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

车载导航仪也称为车载定位和导航系统(Vehicle Location and Navigation System。它的主要功能是利用全球定位系统(GPS)获取定位信息并与电子地图进行匹配，以决定车辆的当前位置并用图形化方式显示；按要求规划从出发地到目的地的最优驾驶路线；按照预先设定的路线，自动根据车辆的位置向驾驶员提供操作指令引导驾驶；提供与电子地图相关的集成信息服务；提供无线通信服务等。车载导航仪把先进的全球卫星定位技术、地理信息技术、数据库技术、多媒体技术和现代通信技术综合在一起?能够实时、高效地向驾驶员提供多种重要信息，具有很强的实用价值和广阔的市场前景。

路径规划是车载导航仪的重要功能模块。在开发车载导航仪过程中，为了实现路径规划模块，对单车辆路径规划算法进行了研究。

1 路径规划算法

所谓路径规划，就是在路网中找到任意给定两点之间的最优路径。最优的标准是旅行费用最小或最大。旅行费用可以是距离、时间或速度等因素。路径规划主要算法有：迪杰斯特拉(Dijkstra)算法及其改进算法、启发式搜索算法、双向搜索算法和双向启发式搜索算法等。

迪杰斯特拉算法是解决两点之间最短距离的有效算法。算法的思想是?从原节点开始，算法每前进一步，都找到一个与原节点之间费用（距离）最小的节点，直至找到所有节点离原节点的最小费用。该算法的特点是?只要各段路径的费用非负，一定可以找到从原节点到各节点的最优解。缺点是需遍历所有节点。算法的运行时间为O slogn 1，其中n、s分别为路径节点和路段的总数。单车导航没有必要找到所有节点到原节点的最优路径。改进的迪杰斯特拉算法在找到目标节点的最优路径后，算法停止。其运行时间为O bd，其中b是各节点的平均后继节点数，d为算法的搜索深度，即遍历树的层数。

启发式搜索算法引入启发式估价函数f'n＝g n+h'n，其中gn表示从原节点到当前节点n的实际费用，h'n为当前节点ｎ到目标节点的估计费用。启发式搜索算法基本同于改进的迪杰斯特拉算法，唯一不同的是前者的费用是f'n，而后者为g n。估计费用h' n能引导算法优先搜索接近目标节点的节点，因此比改进的迪杰斯特拉算法有更快的速度。其运行时间为O bd。注意这里的d要比改进的迪杰斯特拉算法中的d要小。若路网中任意两点之间存在最优路径，而且估计费用满足可纳性，即h' n小于从节点n到目标节点之间的实际费用，那么通过该算法一定可以找到一条最优路径。

前面两种算法都是从原节点到目标节点没单一方向进行搜索的算法。双向搜索算法的思想是：不仅进行从原节点到目标节点的前向搜索，而且进行从目标节点到原节点的后向搜索。在单CPU硬件平台条件下，两个方向的搜索交替进行。成功实现双向搜索有两个条件，即合适的搜索停止条件和前向后向搜索切换标准。其算法时间为O bd/2。若双向搜索算法中加入估计费用函数，便是更快的双向启发式搜索算法１。

2 双向启发式搜索算法的改进和实现

2.1 算法的优化与改进

通过对双向启发式搜索算法的仔细分析，发现算法主要围绕两个表进行操作，即OPEN表和CLOSE表。前者用于存放已经搜索但尚未确定最小费用的节点，称labbled节点；后者用于存放已经搜索且最小费用已知的节点，称scanned节点。后者也用于存放路径回朔指针等。对OPEN表的主要操作有插入一个i节点insert i，删除费用值最小的节点delete 和减小其中某个节点i的费用decrease i。算法对OPEN表的操作极为频繁。若用高效的数据结构来实现该表及其操作，可以提高算法的效率和速度。最后用有高效算法的最小堆4实现了OPEN表及其操作，优化了算法。具体实现的函数如下：

void filter_down int START int ENDOFHEAP//由起点START从上而下排列堆；
void decrease int NODE//更新减少堆中节点NODE的费用f'值；
void filter_up int START //由起点START从下而上排列堆；
void heap_create int MAXSIZE //创建堆；
void heap_destructor//析构函数；
int insert int NODE//把节点NODE插入堆；
int remove_min int &iMinNode//删除堆中最小费用f'值的节点。

在实际的路网中，路段有不同的属性，如高速公路、收费路段、单行路段等。有些路段可能因修建或发生交通故障而暂时封闭。因此在进行路径规划时，算法应该考虑路网中路段的属性，才能进行符合实际的规划，否则理论上规划出来的最优路径可能是不通的。为此，对算法进行了改进。增加一个变量纪录各路段的属性，算法每搜索一新的路段，都要检查该路段的属性，若是限制的路段，算法不做任何处理。同时路径规划算法入口参数中应说明限制的内容。这样就能根据用户的意愿或实时交通信息，避免走某些特定的路段。

2.2 搜索停止条件、搜索切换标准和估计费用函数

前面提到，成功实现双向搜索算法必须有合适的搜索停止条件和切换标准。两个标准没有现成的理论依据。经过对车载导航仪实际应用的分析和反复试验，终于找到可靠有效的标准。其中停止条件为：(1)搜索到这样一个节点iNODEmin，它在前向后向搜索过程中均被标为scanned节点；(2)gl iNODEmin +g2 iNODEmin确实是最小的，其中gl iNODEmin表示从原节点到iNODEmin的最小费用，g2 iNODEmin表示从目标节点到iNODEmin的最小费用。如果只满足第一个条件就停止搜索，找到的最优路径不一定是最优的。只有加上第二个条件，才能确保找到最优的路径，但付出的代价是要多搜索几十个点。具体的搜索停止条件如图1所示。

此外，经过实验发现，如前向搜索的步数和后向搜索的步数不同，则算法的总的搜索节点数增加。因此两个方向上的搜索步数应相同，然后切换。但搜索步距过小或过大，也会增加总搜索量。最后定下的切换标准是，每个方向搜索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的硬件平台。总之改进的双向启发式搜索算法快速高效，已经成功用于正在开发的车载导航仪。