Application of an Improved A~* Algorithm in Shortest Route Planning
Baoshan Zhu · Geomatics & Spatial Information Technology · 2009
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.