基于路径优化的A*算法与Dijkstra算法的性能比较
刘云翔+杜杰+张晴
摘 要： 路径优化成为解决道路拥挤和阻塞的重要途径。传统单源最短路径的Dijkstra算法可以找到从起始点到其他点的最短路径信息，在地图障碍物较多的情况下，其搜索时间较长。人工智能领域带启发式函数的A*算法由于本身就具有记忆性的功能，在路网中可以自主性的选择最优路径，并且随着障碍物信息和地理位置信息的增多，其搜索效率更高。通过实验将A*算法与传统的Dijkstra算法进行仿真比较，对比它们的搜索速度和搜索效率，结果证明在实际路网中A*算法的搜索效果更明显。
关键词： 最短路径； A*算法； Dijkstra算法； 路径优化
中图分类号： TN911.1?34； TP312 文献标识码： A 文章编号： 1004?373X（2017）13?0181?03
Abstract： The path optimization is an important way to solve the traffic congestion and blocking. The traditional Dijkstra algorithm based on monophyletic shortest path can find the shortest path information from the starting point to other points， but its search time is long in the situation of various map obstacles. The A* algorithm with heuristic function in the field of artificial intelligence can select the optimum path by itself because of its memory function. With the increase of obstacle information and location information， the search efficiency of A* algorithm becomes higher. The A* algorithm and traditional Dijkstra algorithm were simulated and compared with experiments， and their search speed and search efficiency were compared. The simulation results show that the search effect of A* algorithm is more effective in the actual road network.
Keywords： shortest path； A* algorithm； Dijkstra algorithm； path optimization
最短路徑问题[1]是图论中网络分析的经典问题，近年来，随着路径搜索技术的不断发展，已经涌现出很多成熟的路径规划算法，比如，基于图论的Dijkstra算法[2?3]，以及关于人工智能领域的启发式搜索算法和动态规划算法等。A*启发式搜索算法作为人工智能领域的重要组成部分，其针对网格数据有着更高的运算效率，而且利用启发信息大幅度提高了搜索速度。这种全新的启发式搜索算法[4]将会极大地改变现有的交通管理与服务模式。
1 A*算法原理
传统的BFS算法的评估函数只考虑当前点与终点的距离，其策略是选择与终点最近的点进行搜索。而Dijkstra算法则只关注当前点与起点的距离，选择与起点最近的点开始搜索。A*算法[5]则是将二者结合起来，其启发函数采用如下的计算公式：
式中：就是A*算法[5]对每个节点的评估函数[2]，其包含两部分信息：是从起点到当前节点的实际代价，也就是从起点到当前节点的移动距离；相邻的两个点的移动距离是1，当前点距离起点越远，这个值就越大。是从当前节点到终点的距离评估值，这是一个从当前节点到终点的移动距离的估计值。
A*算法的搜索过程需要两个表：一个是OPEN表，存放当前已经被发现但是还没有搜索过的节点；另一个是CLOSE表，存放已经搜索过的节点，具体的算法流程图如图1所示。
1.1 常用的距离评估函数
是A*算法的距离估计值[6]，A*算法需要一个距离评估函数来计算这个值。常用的距离评估函数有曼哈顿距离、欧式几何平面距离和切比雪夫距离。在没有障碍物的地图上，这三种距离评估函数得到的效果是一样的，但是在有障碍物的情况下，这三种距离评估函数的效果略有差异。当距离评估函数总是0时，A*算法就退化为Dijkstra算法[6]的效果。
1.1.1 曼哈顿距离
从数学上描述，曼哈顿距离是两个点在各个坐标轴上的距离差值的总和，维几何空间中曼哈顿距离的数学描述为：
对于二维平面上的两个点和，其曼哈顿距离为：
即欧式几何平面距离为在直角坐标系中两个坐标轴上的投影距离和。
1.1.2 欧式几何平面距离
欧式几何平面距离（Euclidean distance）又称为欧式距离或欧几里得距离[7]，其数学定义是维空间中两个点之间的真实距离（几何距离），其数学符号可以描述为：
对于二维平面上的两个点和其欧式几何平面距离为：
即平面几何中两点之间的几何距离。
1.1.3 切比雪夫距离
切比雪夫距离（Chebyshev Distance）是由一致范数（或称上确界范数）衍生的度量，从数学角度上理解，对于两个向量和其切比雪夫距离就是向量中各个分量的差的绝对值中最大的那一个，用数学符号可以描述为：
特别情况下，对于平面上的两个点和，其切比雪夫距离为：
距离评估函数与A*算法的结果之间存在很微妙的关系，如果令始终为0，相当于一点启发信息都没有，则A*算法[5]退化为Dijkstra算法，这种情况即为最差的A*算法。的值越小，启发信息越少，搜索范围越大，速度越慢，但是越有希望得到最短路径；的值越大，启发信息越多，搜索的范围越大，但是其有可能得不到真正的最短路径。当大到一定程度时，公式中的就可以忽略不计，则A*算法演化成为BFS（广度优先搜索算法），速度最快，但是不一定能够得到最短路径。所以通过调整和函数，可以使得A*算法[6]在速度与准确性之间获得一个折中的效果。
1.2 A*算法的实现
A*算法实现的关键在于维护OPEN表和CLOSE表，其中对于OPEN表的主要操作就是查询最小的节点以及删除节点，因此考虑在算法实现时将OPEN表[7]设计为有序表。这样在OPEN列表存储数据时就可以自动将数据按照距离进行排序，这样算法的执行效率比较高。A*算法的参数设置见表1，参数的迭代次数见图2。
通过仿真实验分析可以得出，A*算法[5]在有障碍物的情况下中和了BFS算法和Dijkstra算法的优点，能够更有效地找到最终的最短路径。
2 A*算法与Dijkstra算法效率的比较
Dijkstra算法是典型的单源最短路径算法，其适用于求解没有负权边的带权有向图的单源最短路径问题。由于Dijkstra算法[2?3]使用了广度优先搜索的策略，它可以一次得到所有点的最短路径。但是，它只是简单地做广度优先搜索而忽略了很多有用的信息。盲目搜索的效率很低，耗费很多时间和空间。考虑到实际地图上面两点之间存在位置和距离等信息，A*算法既能够像Dijkstra算法那样搜索到最短路径，又能像BFS（广度优先搜索算法）一样使用启发式函数进行启发式搜索，是目前各种寻径算法中最受欢迎的选择。
将A*算法同Dijkstra算法[6]进行仿真比较，用于比较性能的主要指标有：时间复杂度分析；搜索到最短路径的成功率分析。利用C++语言编制了三种算法的最短路径搜索程序，运行在本地计算机上，并得出仿真模拟图。
搜索效率的对比结果如表2所示。
由表2可以看出：当地图节点的个数和弧的条数比较多时，A*算法[5]的搜索效率比Dijkstra算法快很多，当节点数不断增多时，其搜索最短路径的效率更高。在相同路网和位置信息的条件下进行仿真实验的结果如图3所示。
由图3可以看出，两种算法在相同障碍物条件下进行模拟仿真时，A*算法的搜索效率和时间复杂度要明显优于Dijkstra算法，并对不同实验场景下的效率进行对比，结果如图4所示。
3 结 语
从Dijkstra算法和A*算法[2]的实现可知，Dijkstra算法的时间复杂度是其中是有向图中顶点的个数。对于不含负权边的有向图来说，Dijkstra算法是目前最快单源最短路径算法。A*算法兼有Dijkstra算法和广度优先搜索算法的特点，在速度和准确性之间有很大的灵活性。除了调整和可以获得不同的效果外，A*算法还有很多可以提高效率的改进方法。比如，在地图比较大的情况下使用二叉堆来维护OPEN表以获得更好的运算效率。
参考文献
[1] WORBOYS M. Event?oriented approaches to geographic phenomena [J]. International journal of geographical information science， 2010， 19（1）： 1?28.
[2] NARAYANASAMY V. Game programming gems 6 [EB/OL]. [2015?05?12]. www.download.csdn.net/data.
[3] DYBSAND E. A finite state machine class [J]. Game programming gems， 2000（1）： 237?248.
[4] 周郭许，唐西林.基于栅格模型的机器人路径规划快速算法[J].计算机工程与应用，2006，42（21）：197?199.
[5] 李大生，刘欣，吴明华，等.基于动力学约束的机器人无碰运动规划[J].机器人，1990（5）：14?19.
[6] VIDALVERD? F， BARQUERO M J， CASTELLANOSRAMOS J， et al. A large area tactile sensor patch based on commercial force sensors [J]. Sensors， 2010， 11（5）： 5489?5507.
[7] 李得伟，韩宝明，韩宇.一种逆向改进型A*路径搜索算法[J].系统仿真学报，2007，19（22）：5175?5177.
[8] 林丹.一种室内清洁机器人返回路径规划算法[J].重庆科技学院学报（自然科学版），2009，12（1）：110?113.
[9] 赵真明，孟正大.基于加权A～*算法的服务型机器人路径规划[J].华中科技大学学报（自然科学版），2008（z1）：196?198.
[10] KHATIB M， CHATILA R. An extended potential field approach for mobile robot sensor?based motions [C]// Proceedings of 1995 IEEE International Conference on Intelligent Autonomous Systems. [S.l.]： IEEE， 1995： 490?496.
[11] SILVERMAN M C， NIES D， JUNG B， et al. Staying alive： a docking station for autonomous robot recharging [C]// Procee?dings of 2002 IEEE International Conference on Robotics and Automation. Washington， DC： IEEE， 2002： 1050?1055.
摘 要： 路径优化成为解决道路拥挤和阻塞的重要途径。传统单源最短路径的Dijkstra算法可以找到从起始点到其他点的最短路径信息，在地图障碍物较多的情况下，其搜索时间较长。人工智能领域带启发式函数的A*算法由于本身就具有记忆性的功能，在路网中可以自主性的选择最优路径，并且随着障碍物信息和地理位置信息的增多，其搜索效率更高。通过实验将A*算法与传统的Dijkstra算法进行仿真比较，对比它们的搜索速度和搜索效率，结果证明在实际路网中A*算法的搜索效果更明显。
关键词： 最短路径； A*算法； Dijkstra算法； 路径优化
中图分类号： TN911.1?34； TP312 文献标识码： A 文章编号： 1004?373X（2017）13?0181?03
Abstract： The path optimization is an important way to solve the traffic congestion and blocking. The traditional Dijkstra algorithm based on monophyletic shortest path can find the shortest path information from the starting point to other points， but its search time is long in the situation of various map obstacles. The A* algorithm with heuristic function in the field of artificial intelligence can select the optimum path by itself because of its memory function. With the increase of obstacle information and location information， the search efficiency of A* algorithm becomes higher. The A* algorithm and traditional Dijkstra algorithm were simulated and compared with experiments， and their search speed and search efficiency were compared. The simulation results show that the search effect of A* algorithm is more effective in the actual road network.
Keywords： shortest path； A* algorithm； Dijkstra algorithm； path optimization
最短路徑问题[1]是图论中网络分析的经典问题，近年来，随着路径搜索技术的不断发展，已经涌现出很多成熟的路径规划算法，比如，基于图论的Dijkstra算法[2?3]，以及关于人工智能领域的启发式搜索算法和动态规划算法等。A*启发式搜索算法作为人工智能领域的重要组成部分，其针对网格数据有着更高的运算效率，而且利用启发信息大幅度提高了搜索速度。这种全新的启发式搜索算法[4]将会极大地改变现有的交通管理与服务模式。
1 A*算法原理
传统的BFS算法的评估函数只考虑当前点与终点的距离，其策略是选择与终点最近的点进行搜索。而Dijkstra算法则只关注当前点与起点的距离，选择与起点最近的点开始搜索。A*算法[5]则是将二者结合起来，其启发函数采用如下的计算公式：
式中：就是A*算法[5]对每个节点的评估函数[2]，其包含两部分信息：是从起点到当前节点的实际代价，也就是从起点到当前节点的移动距离；相邻的两个点的移动距离是1，当前点距离起点越远，这个值就越大。是从当前节点到终点的距离评估值，这是一个从当前节点到终点的移动距离的估计值。
A*算法的搜索过程需要两个表：一个是OPEN表，存放当前已经被发现但是还没有搜索过的节点；另一个是CLOSE表，存放已经搜索过的节点，具体的算法流程图如图1所示。
1.1 常用的距离评估函数
是A*算法的距离估计值[6]，A*算法需要一个距离评估函数来计算这个值。常用的距离评估函数有曼哈顿距离、欧式几何平面距离和切比雪夫距离。在没有障碍物的地图上，这三种距离评估函数得到的效果是一样的，但是在有障碍物的情况下，这三种距离评估函数的效果略有差异。当距离评估函数总是0时，A*算法就退化为Dijkstra算法[6]的效果。
1.1.1 曼哈顿距离
从数学上描述，曼哈顿距离是两个点在各个坐标轴上的距离差值的总和，维几何空间中曼哈顿距离的数学描述为：
对于二维平面上的两个点和，其曼哈顿距离为：
即欧式几何平面距离为在直角坐标系中两个坐标轴上的投影距离和。
1.1.2 欧式几何平面距离
欧式几何平面距离（Euclidean distance）又称为欧式距离或欧几里得距离[7]，其数学定义是维空间中两个点之间的真实距离（几何距离），其数学符号可以描述为：
对于二维平面上的两个点和其欧式几何平面距离为：
即平面几何中两点之间的几何距离。
1.1.3 切比雪夫距离
切比雪夫距离（Chebyshev Distance）是由一致范数（或称上确界范数）衍生的度量，从数学角度上理解，对于两个向量和其切比雪夫距离就是向量中各个分量的差的绝对值中最大的那一个，用数学符号可以描述为：
特别情况下，对于平面上的两个点和，其切比雪夫距离为：
距离评估函数与A*算法的结果之间存在很微妙的关系，如果令始终为0，相当于一点启发信息都没有，则A*算法[5]退化为Dijkstra算法，这种情况即为最差的A*算法。的值越小，启发信息越少，搜索范围越大，速度越慢，但是越有希望得到最短路径；的值越大，启发信息越多，搜索的范围越大，但是其有可能得不到真正的最短路径。当大到一定程度时，公式中的就可以忽略不计，则A*算法演化成为BFS（广度优先搜索算法），速度最快，但是不一定能够得到最短路径。所以通过调整和函数，可以使得A*算法[6]在速度与准确性之间获得一个折中的效果。
1.2 A*算法的实现
A*算法实现的关键在于维护OPEN表和CLOSE表，其中对于OPEN表的主要操作就是查询最小的节点以及删除节点，因此考虑在算法实现时将OPEN表[7]设计为有序表。这样在OPEN列表存储数据时就可以自动将数据按照距离进行排序，这样算法的执行效率比较高。A*算法的参数设置见表1，参数的迭代次数见图2。
通过仿真实验分析可以得出，A*算法[5]在有障碍物的情况下中和了BFS算法和Dijkstra算法的优点，能够更有效地找到最终的最短路径。
2 A*算法与Dijkstra算法效率的比较
Dijkstra算法是典型的单源最短路径算法，其适用于求解没有负权边的带权有向图的单源最短路径问题。由于Dijkstra算法[2?3]使用了广度优先搜索的策略，它可以一次得到所有点的最短路径。但是，它只是简单地做广度优先搜索而忽略了很多有用的信息。盲目搜索的效率很低，耗费很多时间和空间。考虑到实际地图上面两点之间存在位置和距离等信息，A*算法既能够像Dijkstra算法那样搜索到最短路径，又能像BFS（广度优先搜索算法）一样使用启发式函数进行启发式搜索，是目前各种寻径算法中最受欢迎的选择。
将A*算法同Dijkstra算法[6]进行仿真比较，用于比较性能的主要指标有：时间复杂度分析；搜索到最短路径的成功率分析。利用C++语言编制了三种算法的最短路径搜索程序，运行在本地计算机上，并得出仿真模拟图。
搜索效率的对比结果如表2所示。
由表2可以看出：当地图节点的个数和弧的条数比较多时，A*算法[5]的搜索效率比Dijkstra算法快很多，当节点数不断增多时，其搜索最短路径的效率更高。在相同路网和位置信息的条件下进行仿真实验的结果如图3所示。
由图3可以看出，两种算法在相同障碍物条件下进行模拟仿真时，A*算法的搜索效率和时间复杂度要明显优于Dijkstra算法，并对不同实验场景下的效率进行对比，结果如图4所示。
3 结 语
从Dijkstra算法和A*算法[2]的实现可知，Dijkstra算法的时间复杂度是其中是有向图中顶点的个数。对于不含负权边的有向图来说，Dijkstra算法是目前最快单源最短路径算法。A*算法兼有Dijkstra算法和广度优先搜索算法的特点，在速度和准确性之间有很大的灵活性。除了调整和可以获得不同的效果外，A*算法还有很多可以提高效率的改进方法。比如，在地图比较大的情况下使用二叉堆来维护OPEN表以获得更好的运算效率。
参考文献
[1] WORBOYS M. Event?oriented approaches to geographic phenomena [J]. International journal of geographical information science， 2010， 19（1）： 1?28.
[2] NARAYANASAMY V. Game programming gems 6 [EB/OL]. [2015?05?12]. www.download.csdn.net/data.
[3] DYBSAND E. A finite state machine class [J]. Game programming gems， 2000（1）： 237?248.
[4] 周郭许，唐西林.基于栅格模型的机器人路径规划快速算法[J].计算机工程与应用，2006，42（21）：197?199.
[5] 李大生，刘欣，吴明华，等.基于动力学约束的机器人无碰运动规划[J].机器人，1990（5）：14?19.
[6] VIDALVERD? F， BARQUERO M J， CASTELLANOSRAMOS J， et al. A large area tactile sensor patch based on commercial force sensors [J]. Sensors， 2010， 11（5）： 5489?5507.
[7] 李得伟，韩宝明，韩宇.一种逆向改进型A*路径搜索算法[J].系统仿真学报，2007，19（22）：5175?5177.
[8] 林丹.一种室内清洁机器人返回路径规划算法[J].重庆科技学院学报（自然科学版），2009，12（1）：110?113.
[9] 赵真明，孟正大.基于加权A～*算法的服务型机器人路径规划[J].华中科技大学学报（自然科学版），2008（z1）：196?198.
[10] KHATIB M， CHATILA R. An extended potential field approach for mobile robot sensor?based motions [C]// Proceedings of 1995 IEEE International Conference on Intelligent Autonomous Systems. [S.l.]： IEEE， 1995： 490?496.
[11] SILVERMAN M C， NIES D， JUNG B， et al. Staying alive： a docking station for autonomous robot recharging [C]// Procee?dings of 2002 IEEE International Conference on Robotics and Automation. Washington， DC： IEEE， 2002： 1050?1055.
