一种基于随机游走的A*算法
2018-01-24刘浩翰郭晶晶李建伏贺怀清
中国民航大学学报 2017年6期
关键词:检测
刘浩翰,郭晶晶,李建伏,冯 梅,贺怀清
(1.中国民航大学计算机科学与技术学院,天津 300300;2.中国民用航空华北地区空中交通管理局,北京 100621)
最短路径问题是图论中的一个重要研究课题,其目的是在多项式时间内找到图中任意两节点之间的最短路径[1]。最短路径搜索算法有Dijkstra算法、Floyd算法和A*算法[2]等。A*算法的基本策略是在启发式函数的引导下,优先扩展最有希望尽快到达目标节点的节点。与Dijkstra算法、Floyd算法相比,A*无须扩展所有节点,具有较高的搜索效率。
在实际应用中,A*算法的搜索效率在很大程度上依赖于启发式函数的质量。一个理想的启发式可以使得搜索节点数目为O(|L|),L是找到的解的长度(从初始节点到目标节点的节点个数)[3]。然而找到一个完美的启发式函数是不可能的,现实中往往只能牺牲搜索效率而选择近似最优的启发式函数[4]。
在A*搜索过程中,经常会陷入高原搜索期,即对任意节点S,假设当前搜索过的所有节点的最小启发式函数值为h*(S),显然,h*随着搜索过程单调递减,并且在遇到目标节点时变为0,但是在A*搜索的大部分时间里,h*并没有随着更多节点的展开而减小,这样的搜索过程被称为“高原搜索”(plateauexploration)[3]。当搜索陷入高原搜索期时,A*算法的性能急剧下降。而研究表明,启发式搜索中普遍存在着高原搜索现象[5-9]。
如何及时地识别并跳出高原搜索期对提高整个A*算法的性能至关重要。针对这一问题已开展了很多相关研究,如状态空间约简技术[10-11]、蒙特卡罗随机游走搜索[12-14]等。……
登录APP查看全文
