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

• 作者: 余博文
• 来源期刊: 数码世界
• 关键词: A*算法 启发式搜索 最短路径 启发函数 open表
• 年，卷（期）: 2019,（8）
• 所属期刊栏目: IT大视野
• 页码范围: 35-38
• 页数: 4页
• 字数: 6093字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	余博文		1	0	0.0	0.0