改进的双向A星搜索算法在路径搜索中的应用

改进的双向A星搜索算法在路径搜索中的应用

算法设计与代码实现

作者：wxh5055

本文基于A*算法和双向搜索算法提出一种改进的双向A*搜索算法，该算法也是从起始点和目标点同时进行搜索，并在一个简化的中国地图上进行实例验证。一般双向A*搜索算法是当正向搜索的open表的最优估值节点在逆向搜索的open表中，或者是逆向搜索的最优估值节点在正向搜索的open表中时，即停止搜索。该方法在路径导航中可以大大降低搜索的节点和时间，并且在大多数情况下搜索出的路径是最佳路径，但在某些极端情况下搜索出的路径可能离最佳路径相差比较远。本文介绍的双向A*搜索算法是记录下每一次正向搜索和逆向搜索的最佳路径，且当正向搜索的open表的最优估值节点在逆向搜索的最佳搜索路径中，或者逆向搜索的open表的最优估值节点在正向搜索的最佳搜索路径中时，即停止搜索。注意该改进的双向搜索算法和普通双向搜索算法的重要区别是，后者是当搜索的open表的最优估值节点在另一搜索方向的open表中时停止搜索，而前者是当搜索的open表的最优估值节点在另一搜索方向的最佳搜索路径中时停止搜索，显然前者搜索出的路径是一条更优的路径。假设正向搜索的open表的最优估值节点在逆向搜索的最佳搜索路径中，则说明从起始点到该节点的搜索路径是正向搜索的最佳路径；而该节点又在逆向搜索的最佳搜索路径中，则说明从目标点到该节点的搜索路径是逆向搜索的最佳路径，然后从该节点按逆向查询一直到目标点即可找出一条搜索路径。该方法在路径导航中也可以大大降低搜索的节点和时间，且在实际应用中基本都能搜索出一条最佳路径，但需要多记录一条丛起始点开始搜索的最佳路径和从目标点开始搜索的最佳路径。为了让读者能更加明白该算法的搜索原理，我们以一实例来进行详细说明，并在文章后面给出具体实现的代码。

该实例的连接情况如下。在中国地图上取出34个城市作为节点，为了说明本文介绍的双向A*搜索算法，我把各城市作如下的简化连接，并给每个城市如下进行编号。

51781516141332244253130291012181922320212226283433277139611

本文介绍的双向A*搜索算法操作过程如下：

1， 初始化地图，根据上图的连接情况初始化地图。本文用二维数组表示地图之间的连接，

相互节点之间有连接则值为1，否则为0，并存储在mapLink数组中，如下图所示：

2， 初始化每个城市节点的基本信息。本文在计算A*搜索的f、g、h值时，是通过每个城市

的经度和纬度来计算两个城市之间的距离的。因本文主要是为了说明改进的双向A*搜索的算法设计和代码实现，所以就把每个城市看成是在以经度和纬度定位的二维平面坐标上，两者之间的距离是欧拉距离。所使用的每个城市的经度和纬度如下： 北京(116.28,39.54),上海(121.29,31.14), 天津(117.11,39.09), 重庆(106.32,29.32), 哈尔滨(126.41,45.45), 长春(125.19,43.52), 沈阳(123.24,41.5), 呼和浩特(111.48,40.49), 石家庄(114.28,38.02), 太原(112.34,37.52), 济南(117,36.38), 郑州(113.42,34.48), 西安(108.54,34.16), 兰州(103.49,36.03), 银川(106.16,38.2), 西宁(101.45,36.38), 乌鲁木齐(87.36,43.48), 合肥(117.18,31.51), 南京(118.5,32.02), 杭州(120.09,30.14), 长沙(113,28.11),

南昌(115.52,28.41), 武汉(114.21,30.37), 成都(104.05,30.39), 贵阳(106.42,26.35), 福州(119.18,26.05), 台北(121.31,25.03), 广州(113.15,23.08), 海口(110.2,20.02), 南宁(108.2,22.48),

昆明(102.41,25), 拉萨(90.08,29.39), 香港(114.1,22.18),澳门(113.35,22.14)。 每个节点的基本信息用如下结构体表示： //节点的基本信息结构体 typedef struct _tagNodeInfo {

int number;//编号 char* name;//地名

float longitude;//经度 float latitude;//纬度 }tagNodeInfo;

比如北京的基本信息为： //1,beijing {

1,

beijing\ 116.28, 39.54, },

按地图中所示的编号顺序依次初始化每个城市节点的基本信息。

3， 输入搜索的起点信息和目标点信息，假设我们需要找出一条从广州到北京的路径，该段

代码和运行时效果如下所示，具体实现代码会在文章后面给出：

4， 初始化每个节点信息。在第二步把每个节点的基本信息填写好且在第三步输入起始点和

目标点信息之后，现在初始化每个节点的信息，包括初始化f，g，h值为0等节点为初始状态，并存储在数组node[CITY_NUMBER]中。然后设置起始点广州和目标点北京的初始状态，包括把节点广州添加到正向搜索的open表forwardOpenTable中和把节点北京添加到逆向搜索的open表backOpenTable中并计算相应的值。初始化完成后，就开始进行后面的双向A*搜索。 5， 进行正向搜索。

5.1 在正向搜索的open表forwardOpenTable取出有最优估计距离的节点currNode，如果open表已空，则说明正向搜索所有能到达的节点都已经搜索完毕还没到达目标节点，返回搜索失败标志；否则进行步骤5.2。

5.2 更新正向搜索的最佳路径，然后判断如果currNode在逆向搜索的最佳路径中，则说明找到了一条到达目标点的路径，返回搜索完成标志；否则把currNode添加到正向搜索的close表中。

5.3对当前最优节点进行处理。根据地图数组mapLink找出与当前节点currNode有连接的节点nodeTemp。如果节点nodeTemp在正向搜索的close表中，则继续搜索下一个与节点currNode有连接节点；否则判断节点nodeTemp是否在正向搜索的open表中。如果不在open表中，则分别计算nodeTemp的g、h、f值，设置nodeTemp的父节点为currNode，并把nodeTemp按f值大小从小到大添加到正向搜索的open表中；如果节点nodeTemp在正向搜索的open表中，则判断节点currNode的g值加上从节点currNode到节点nodeTemp的距离是否大于节点nodeTemp的g值，如果大于则继续搜索与节点currNode有连接的下一个节点；否则重新计算nodeTemp的g、h、f值，设置nodeTemp的父节点为currNode，并把nodeTemp按f值大小从小到大添加到正向搜索的open表中，然后再继续搜索与节点currNode有连接的下一个节点。直到所有与节点currNode有连接的节点都搜索完毕，才进行逆向搜索。

6， 进行逆向搜索。逆向搜索的过程和正向搜索一样，具体可以查看本文后面的代码。双向

A*搜索算法就是不断地在步骤5和步骤6之间反复交替搜索，直到找到一条路径或把所有与起始点和目标点有连接的节点搜索完毕才结束搜索。

7， 判断步骤5和步骤6的返回值，如果返回搜索失败信息，则提示搜索失败状态。如果返

回搜索完成标志，则打印搜索出的从起始点到目标点的完整路径。

代码说明：

本文给出的代码实例是在VC++6.0环境下编译的，代码运行时会先提示输入起始城市名字和输入目标城市名字，注意输入的城市的名字均为汉语拼音的小写的全拼。然后代码就进行搜索，搜索完成后显示搜索的结果，如下图所示(F表示正向搜索出的节点，B表示逆向搜索出的节点)：