两种改进的最优路径规划算法

在对经典Dijkstra算法和A*算法分析的基础上对它们分别进行了改进.在经典Dijkstra算法中,针对当前不相连节点间路径长度为无穷大这一特点,首先对两个节点是否相连进行判断;若发现两个节点并不相连时,则舍去相应计算,从而减小计算量.针对A*算法在实际应用中搜索效率低的缺点,将经典A*算法搜索出的原始最优路径中的节点依次进行封堵后,再按照经典A*算法搜索出相应的新最优路径,最后再将原始最优路径与这些新最优路径进行对比,以便确定最终的最优路径.仿真研究表明:改进的Dijkstra算法可以减少大量的无关节点计算,提高运算的效率;改进的A*算法则可以提高搜索到最优路径的成功率.

Two improved optimum path planning algorithms

An improved Dijkstra's and an improved A* algorithm were proposed based on the analysis of their drawbacks. In the traditional Dijkstra's algorithm, the distance between two unconnected nodes is infinite and some relative calculations are useless. The improved Dijkstra's algorithm proposed that the connection between nodes should be tested at first so that it can decrease the computing overhead to a great extent. When the traditional A* algorithm is used in practice, its efficiency is not satisfied. The improved A* algorithm includes such steps as the following: firstly, the original optimum path should be planned by the traditional A* algorithm; secondly the nodes in the original optimum path; should be blocked in turn and the traditional A* algorithm is used again in order to look for another new optimum path. finally, these new optimum paths should be compared with the original one so that the final optimum path can be selected. Simulation results show that the improved Dijkstra's algorithm can enhance the calculation efficiency and the improved A* algorithm can find the more optimum path.