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

来源期刊：工程科学学报2005年第3期

论文作者：李擎 宋顶立 张双江 李哲 刘建光 王志良

文章页码：367 - 370

关键词：路径规划;车辆导航;Dijkstra算法;A*算法;

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