改进A^＊算法及其在GIS路径搜索中的应用  

Application of Improved A^＊ Algorithm for Path Searching in GIS

作　　者：李志建[1] 郑新奇[1] 王淑晴[1] 杨鑫[1] 

机构地区：[1]中国地质大学(北京)土地科学技术学院,北京100083

出　　处：《系统仿真学报》2009年第10期3116-3119,共4页Journal of System Simulation

基　　金：国家自然科学基金(40571119)

摘　　要：路径选择在实际运用中主要追求的是最优而不是最短。为此通常采用精度换效率的策略。这种策略虽然在一定程度上达到了路径搜索的任务要求,但如果能在精度和效率之间综合取值的话,效果往往会更令人满意。采用了一种改进的A*算法来实现这一目的。主要是通过变权值的方式来控制算法的搜索精度和搜索效率。实验证明,改进的A*算法可以实现最优路径的选择,且效率有很大的提高。About path selection in practical application, the optimal one rather than the shortest one is mainly pursued, so sacrificing precision for efficiency is a good strategy. This strategy achieves the searching tasks in path selection to some extent, but if the integrated value of precision and efficiency are used, the result is often more satisfying. An improved A ^＊ algorithm was used to achieve the target. It is mainly through the value of the variable weight to control the algorithm search precision and efficiency. An instance proves that the improved,A^＊ algorithm can achieve the searching optimal path task, and efficiency is greatly enhanced.

关 键 词：A^＊算法 DIJKSTRA算法 最短路径 时间复杂度 

分 类 号：TP320.7[自动化与计算机技术—计算机系统结构]