基于A~*算法的最短路径搜索的优化与研究  

作　　者：余博文 

机构地区：[1]华北电力大学

出　　处：《数码世界》2019年第8期35-38,共4页Digital Space

摘　　要：A*(A星算法),是一种比盲目搜索更高效的启发式搜索.一般的,运用A*算法搜索图的最短路径,尤其是针对于无向图,可采用A*算法的搜索策略.为了改进A*算法的存储方式和搜索效率,将在A*算法的理论基础上,结合迪克斯特拉算法和宽度优先搜索实现改进.本文主要针对A*算法的搜索效率、剪枝等问题进行优化,并得出改进后的最短路径搜索算法.针对A*算法的搜索效率,提出了通过从某一结点开始进行宽度优先搜索,作为启发信息并记录在可以到达的结点上.利用好该启发信息,可以对状态空间搜索树进行大量的剪枝.在此基础上,通过A*算法的思想,对迪克斯特拉算法进行优化.此外,算法中有一步是根据某些启发信息来排列open表,是一个按状态的启发估价函数值的大小排列的一个"表".根据其估价的大小插入到表中合适的位置,每次从表中优先取出启发估价函数值最小的状态加以扩展.但是,open表必须保证在启发信息相同的情况下,保证表内元素的稳定性;启发信息不同,则自小向大排列.通过实验,结果证明,该启发信息与"曼哈顿"距离相比,在最短路径搜索正确率上有一定提高,搜索效率有相对优势.

关 键 词：A*算法 启发式搜索 最短路径 启发函数 open表 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]