摘要
A*算法是一种启发式搜索算法,在路径规划中得到广泛的应用,其中启发函数的设计尤其重要。本文针对路径规划问题,对A*算法作了以下改进:一是在估价函数中考虑以距离和方向两个要素,通过归一化处理解决了单位不统一的问题;二是利用k-d树空间索引结构,动态加载节点信息,减小内存使用空间。实验结果表明,改进后的A*算法的搜索效率得到了明显的提高。
A^＊ algorithm as a heuristic algorithm has been used widely in route planning,in which the heuristic function plays an important part.Through the analysis of problems in route planning,the paper makes some improvement as bellow：one is that the cost function takes the distance and direction as two heuristic elements,and the paper solves the problem that they have different unit by normalization;another is the paper establishes an k-d tree structure,loads the node information dynamically,and reduces consumption of the memory.The experimental results show that the efficiency of A^＊ algorithm has been improved greatly.
出处
《测绘与空间地理信息》
2009年第6期208-211,共4页
Geomatics & Spatial Information Technology
