A*算法的改进及其在路径规划中的应用

被引:52
作者
史辉
曹闻
朱述龙
朱宝山
机构
[1] 信息工程大学测绘学院
关键词
最短路径; A*算法; 估价函数; k-d树;
D O I
暂无
中图分类号
TP301.6 [算法理论];
学科分类号
081202 ;
摘要
A*算法是一种启发式搜索算法,在路径规划中得到广泛的应用,其中启发函数的设计尤其重要。本文针对路径规划问题,对A*算法作了以下改进:一是在估价函数中考虑以距离和方向两个要素,通过归一化处理解决了单位不统一的问题;二是利用k-d树空间索引结构,动态加载节点信息,减小内存使用空间。实验结果表明,改进后的A*算法的搜索效率得到了明显的提高。
引用
收藏
页码:208 / 211
页数:4
相关论文
共 10 条
[1]  
Correction to a formal basis for the heuristic determination of minimum cost paths. Hart,P.E.,Nilsson,N.J.,Raphael,B. SIGART Newsletter . 1972
[2]  
A path algorithm based on dynamic networks and restricted searching area. Fu Meng-yin,Xue Bin. Proceeeding of the IEEE Interna-tional Conference on Automation and Logistics . 2007
[3]  
A procedure for quantitatively site layout alter-natives. Li Z,Anson M,Li G. Constra Manage Econ . 2001
[4]  
Adaptations of theA*Algorithmfor the Computation of Fastest Paths in Deterministic Dis-crete-Time Dynamic Networks. Ismail Chabini,Shan Lan. IEEE Transactionson Intelligent Transportation Systems . 2004
[5]  
EfficientModified BidirectionalA*Algorithm for Optimal Route-Finding. Taeg-Keun Whangbo. IEA/AIE2007 . 2007
[6]  
Schedule-de-pendent evolution of site layout planning. Elbeltagi E,Hegazy T,Hosny AD,et al. Constr Man-age Econ . 2003
[7]  
A Multiple-PlatformDecentralized Route Finding System. Hans W.Guesgen,Debasis Mitra. IEA/AIE99 . 2001
[8]  
A New Shortest Path AlgorithmBased on Heuristic Strategy. Chen Xi,Fei Qi,Li Wei. Proceedings of the 6thWord Congress on Intelligence Control and Automation . 2006
[9]  
LaVatle Planning Algorithms. Steven M. . 2006
[10]  
Introduction to Algorithms. T. H. Cormen,C. E. Leiserson,R. L. Rivest,and C. Stein. McGraw Hill s Washington Report on Medicine Health . 2001