基于A*算法的路径规划仿真平台的设计与实现

杨阳

（湖北职业技术学院 湖北省孝感市 432100）

1 引言

最短路径算法广泛应用于机器人路径规划、大型游戏寻路、障碍物规避、无人机航迹规划及网络应用中，在实际生活生产中具有重要的作用。针对不同领域、不同条件下该问题的算法研究及设计改进也具有十分重要的理论价值和现实意义。最短路径问题包含几种形式:第一种是某两个点之间，即确定好起点终点，求起点到终点之间的最短路径；第二种是一张图中，求任意两个点、即所有两点之间的最短距离；第三种是求某个指定点，到所有其余任意一点之间的最短距离。对于这几种问题，目前国内外有各种特定的的算法研究。

对于单源最短路径问题，即求出某个指定点到所有点之间的最短距离，1959年Dijkstra[1]在论文中提出相应的问题及解决算法。1962年Floyd[2]在提出了采用动态规划的方法求多源点之间，即图中任意两个点之间最短路径的算法。鉴于Dijkstra 算法在带有负权边的图中不适用，Bellman-Ford 算法（Richard Bellman[3]和Lester Ford 分别提出）则能够更普遍地解决单源最短路径问题。这些算法都有不同的优势、算法复杂度与适用场景，在特定情况下，可以综合各自的优势，实现目标算法效率的提升。

2 基础路径规划算法

2.1 Floyd算法

Floyd（弗洛伊德）算法也称为插点法，它采用动态规划的方法寻找多源点之间最短路径的解法。对于一张加权图，每条边上的权重可以是负值（避免负权回路），通过Floyd 算法可以计算出任意两个点之间的最短路径。Floyd 算法采用公式（1）[4]所示：

在上式中，G 为顶点之间的距离矩阵，s 为起点，g 为终点，i表示中间点，n 为顶点的个数。该表达式的含义是，计算出顶点s、i 之间的距离G[s][i]与顶点i、g 之间的距离G[i][g]，如果它们的和小于G[s][g]，则更新G[s][g]的值。按该方法循环遍历所有i 的取值，发现其中G[s][g]的最小值，从而找到起点s 与终点g 之间的最短距离。为了描述该算法思想[5]，首先建立路径规划问题中各顶点距离值所对应的初始邻接矩阵A，并定义G(0)=A。

G(1)表示若只以顶点v1 为中间点所生成的距离矩阵更新值，G(2)表示若只以顶点v1、v2 为中间点所生成的距离矩阵更新值……以此类推，G(k)表示若只以顶点v1、v2、……vk 为中间点所生成的距离矩阵更新值。当k=n 时，便可求出G(n)的值，即可插入顶点v1、v2、……vn 作为中间点生成最终的距离矩阵更新值，从而求出任意两个顶点之间的最短距离。

Floyd 算法的伪代码可以表示为：

容易看出，Floyd 算法时间复杂度是O(N3)，空间复杂度是O(N2)，存在复杂度较高、路径规划时间较长的问题。

2.2 Dijkstra算法

Dijkstra(迪杰斯特拉)算法是基于贪心算法[6]的设计思想，是一种典型的单源最短路径算法，既可以计算一个点到剩余所有点之间的最短距离，也可以用来获得某两个点之间的最短路径。在该算法中，首先将某个顶点V0 作为根节点，然后将整个顶点集合分成两个部分，即已计算出到V0 的最短距离的顶点的集合V（初始时只有V0）和剩余点集U，U 中每个顶点都保存着与V0 的最短距离值。在每次迭代中，在U 中寻找离V0 距离最短的顶点加入到V 中，并更新U 中剩余顶点距离V0 的最短距离值（因为V 中加入了新的顶点）。直到U 集合为空。Dijkstra 算法的伪代码可以表示为：

在一般实现下，Dijkstra 算法时间复杂度是O(N2)，在优化实现的情况下，算法时间复杂度可达到O(ElogV)，其中，E 为边的条数，V 为顶点的个数。

2.3 Bellman-Ford算法

图1：A*算法结果图

Bellman-Ford(贝尔曼-福特)算法是一种求解单源最短路径的算法，相比于Dijkstra 算法，它的优点在于能够处理负权边的情况。该算法最多进行|V-1|次“松弛”[7]操作，从而得到从源点到|V-1|个顶点的最短路径。在每次松弛操作中，根据每条边的权值更新源点到顶点的距离值（源点到各顶点的初始化距离是∞）。在所有指定松弛操作结束后，如果增加一次遍历还能产生更新值，则说明存在负权环。该算法的时间复杂度是O(VE)，其中，V 代表顶点数，E 代表边数，该算法存在改进优化的空间。

2.4 A*算法

A*算法是一种启发式寻路算法。该算法在选择最短路径的下一个顶点时会计算起点到待检测点的距离加上待检测点到终点的估计距离之和作为判断依据，用公式表示为F=G+H。其中，F 表示起始点到目标点的距离函数，G 表示起始点到待检测点的真实代价值，H 是待检测点到目标点的估计代价值。当H=0 时，该算法退化成Dijkstra 算法[8]。根据A*算法的核心原理，它在Dijkstra 算法的基础上，增加了对待检测点的启发式评估，从而筛选了待检测点，加快了生成最短路径的效率。

3 A*算法的设计与实现

3.1 OPEN表和CLOSE表

和Dijkstra 算法类似，A*算法也把整个顶点集合分成两个部分，已完成点集（CLOSE 表）和待检测点集（OPEN 表）。从起点开始，将起点设置为当前点，不断将周围可达点加入到OPEN 表中。根据A*算法的基准公式F=G+H，选择这些可达点中F 值最小的点作为新的当前点，旧的当前点被加入到CLOSE 表中。CLOSE 表中的顶点表示不再需要被关注的点。在算法运行过程当中，可达点加入到OPEN 表后，需要基于当前点更新其F 值，更新成功则设置当前点作为它的前驱顶点。算法在终点加入到OPEN 表时结束。最后，从终点沿着前驱回溯可以找到最短路径。

表1：A*算法运行时间

图2：A*算法运行时间图

3.2 启发式函数

A*算法中，每个顶点F 值的计算包括两个部分：G 表示起点到待检测点之间的距离，由于待检测点是当前点的相邻顶点或可达顶点，这个值可以直接计算出来；H 表示待检测点到终点的估计值，也称为启发式函数，该值的计算需要考虑障碍物、移动方向（能否走对角线）、搜索区域的划分等实际场景问题，以及距离计算公式的选择。对于一个棋盘方格区域，距离计算公式可以采用曼哈顿距离，即将水平位移和垂直位移加和作为距离结果。同样，也可以采用对角线距离、欧式距离等。

A*算法的优化主要集中在OPEN 表的设计结构和启发式函数的选择。一般情况下，可以使用顺序查找表、优先队列等作为OPEN 表的数据结构；启发式函数则可以选择曼哈顿距离、对角线距离、欧式距离等计算公式。

3.3 A*算法实现

如图1 所示，在方阵地图中，红色方块表示起点，紫色方块表示终点，黑色方块表示障碍物，绿色方块表示路径。在本A*算法路径检测中，会判断周围8 个位置是否可以通行，如果某位置没有障碍物，将作为候选路径选择。障碍物采用随机算法生成。

如果采用线性查找表作为OPEN 表结构，A*算法每次都需要遍历整个线性查找表，寻找其中F 值最小的顶点作为新的当前点，继而将该当前点的有效相邻顶点加入到OPEN 表中；并更新这些新加入顶点的F 值，以便下次搜索；

如果采用优先队列作为OPEN 表结构，根据优先队列的性质，具有最高优先级的顶点先出队列，这样避免了线性查找表中全表搜素的时间消耗，加快了算法的运行速度。

图1 展示了地图大小分别为10*10 和20*20，OPEN 表结构分别为线性查找表和优先队列情况下的运行效果图。

分析图2 关于A*算法在不同实现方式下运行时间的统计结果可得：随着地图规模的不断增大，运行时间呈递增趋势；在同规模地图大小的情况下，Open 表结构采用优先队列的运行时间更短。如表1 所示。

4 结论（Conclusion）

路径规划算法是计算机应用技术实践于机器人寻径和避障、大型游戏寻路、网络路由等场景中的重要算法。本文讨论分析了Floyd 算法、Dijkstra 算法、Bellman-Ford 算法的基本定义、原理、算法复杂度，详细介绍了A*算法的设计与实现，并构建路径规划仿真平台对A*算法进行验证。实验结果表明：算法运行时间同地图规模及OPEN 表结构相关。随着地图规模的不断增大，运行时间呈递增趋势；在同规模地图大小的情况下，OPEN 表结构采用优先队列的运行速度更快。