刘云翔+杜杰+张晴

摘 要： 路径优化成为解决道路拥挤和阻塞的重要途径。传统单源最短路径的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]则是将二者结合起来，其启发函数采用如下的计算公式：