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

作     者：李擎 宋顶立 张双江 李哲 刘建光 王志良 LI Qing;Song Dingli;ZHANG Shuangjiang;LI Zhe;Liu Jianguang;WANG Zhiliang

作者机构：北京科技大学信息工程学院北京100083 河北理工大学唐山063009 唐山市交通局货运科唐山063000 海湾科技集团北京100102 

出 版 物：《北京科技大学学报》 (Journal of University of Science and Technology Beijing)

年 卷 期：2005年第27卷第3期

页      面：367-370页

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0802[工学-机械工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 080201[工学-机械制造及其自动化] 

基　　金：国家十五科技攻关项目(No.2001BA 605A-02) 

主　　题：路径规划 车辆导航 Dijkstra算法 A^＊算法 

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