直线优化A^＊算法在最短路径问题中的改进与实现  

Improvement and Realization of Beeline Optimizing A＊ Algorithm in Shortest Path Problem

作　　者：王海梅[1] 周献中[2] 

机构地区：[1]南京理工大学自动化学院,江苏南京210094 [2]南京大学控制与系统工程系,江苏南京210093

出　　处：《工程图学学报》2009年第6期121-126,共6页Journal of Engineering Graphics

基　　金：总装"十一五"资助项目

摘　　要：最短路径算法的效率是汽车实时导航、动态路径规划等应用领域普遍关注和迫切需要解决的问题。在深入分析经典Dijkstra最短路径算法的基础上,从数据结构和搜索策略两方面对算法进行了改进,采用存储桶排序方式,提出了带启发因子的直线优化A*算法。实验结果表明改进的算法具有较高的稳定性和效率。The efficiency of shortest path algorithm brings wide attention and needs to be solved urgently in real-time auto navigation and dynamic route programming. The optimization means based on the classical Dijkstra＇s algorithm is analyzed, and then the improvement of algorithm is presented from two aspects： bucket-sort structure and beeline optimizing A^＊ algorithm with heuristic gene. Experiment results show that the algorithm is stable and effective.

关 键 词：计算机应用 最短路径 直线优化A*算法 存储桶排序 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]