基于路径优化的A~*算法与Dijkstra算法的性能比较

Performance comparison between A~* algorithm and Dijkstra algorithm based on path optimization

路径优化成为解决道路拥挤和阻塞的重要途径。传统单源最短路径的Dijkstra算法可以找到从起始点到其他点的最短路径信息,在地图障碍物较多的情况下,其搜索时间较长。人工智能领域带启发式函数的A*算法由于本身就具有记忆性的功能,在路网中可以自主性的选择最优路径,并且随着障碍物信息和地理位置信息的增多,其搜索效率更高。通过实验将A~*算法与传统的Dijkstra算法进行仿真比较,对比它们的搜索速度和搜索效率,结果证明在实际路网中A~*算法的搜索效果更明显。

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.