一种基于随机游走的A*算法

刘浩翰，郭晶晶，李建伏，冯 梅，贺怀清

（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]等。由于易于实现，蒙特卡罗随机游走算法更为流行。其基本思路为，当检测到搜索陷入高原搜索期时，采用随机游走策略帮助其迅速跳出。

本文结合蒙特卡罗随机游走算法，提出了一种改进的 A*算法（RWA*，A*algorithmbasedonrandomwalk）。与现有的随机游走协助下的最好优先搜索算法[14]不同，RWA*采用了一种新的检测高原搜索期的方法，即当连续扩展n次节点的启发值都比上一次最后扩展出的节点的启发值大时，则认为搜索陷入高原搜索期。

1 A*算法与蒙特卡罗随机游走搜索

1.1 A*算法

A*算法是一种静态路网中求解最短路径较有效的直接搜索方法。算法每次选择具有最小启发值的节点进行扩展，直到找到目标节点。通常使用open表和closed表维护算法搜索过程中产生的节点，open表保存已产生并待扩展的节点，closed表保存已被扩展的节点。

算法通过启发函数对节点状态进行估价，启发函数的形式一般为

其中：g（S）表示状态空间中从初始节点到当前节点S的实际代价；h（S）表示从节点S到目标节点最佳路径的估计代价。

从理论上讲，一个完全正确的启发函数可以迅速得到问题的正确解，并保证h（S）随着搜索过程单调递减，在遇到目标节点时变为0。但一般完全正确的启发函数是得不到的，h（S）并没有单调递减，从而使算法在搜索过程中出现高原搜索现象。

本文提出新的检测高原搜索期的方法，即若x次当前待扩展节点的启发值大于上次扩展节点时最后一个被扩展出的节点的启发值，即节点出现了一定的相似性，则认为算法陷入了高原搜索期。再使用蒙特卡罗随机游走寻找出口迅速跳出高原搜索期。

1.2 蒙特卡罗随机游走搜索

蒙特卡罗随机游走搜索使用随机游走跳跃搜索当前状态的一个邻居状态，它重复循环该过程直到寻找到目标状态。如果在m次跳跃搜索后，所有状态的最小启发函数值仍然没有减小，或遇到终端状态，蒙特卡罗随机游走会回到初始状态重新开始搜索。

随机游走搜索每次从一个状态开始搜索其邻居状态空间，试图找到一个具有更小启发式函数值的状态。在最多n次的循环中，它每次搜索一条路径，计算每条路径末尾状态的启发式函数值，如果其值小于已搜索路径的最小值，则更新节点和节点的启发式函数值。最后返回具有最小启发式函数值的状态。

2 基于随机游走的A*算法

本文提出的基于随机游走的A*算法的基本结构，与一般的基于随机游走的A*算法相同，即当检测到搜索陷入高原搜索期时，采用随机游走策略帮助搜索迅速跳出高原搜索期。与一般的基于随机游走的A*算法不同的是高原搜索期的检测方法。

在该算法中，若x次当前待扩展节点的启发值大于上次扩展节点时最后一个被扩展出的节点的启发值时，即节点出现了一定的相似性，则认为算法陷入了高原搜索期。算法表示如下：

算法1为本文提出的RWA*算法。RWA*算法在标准A*算法的基础上增加了扩展新节点后的“高原搜索期”检测（第13行）。如果检测到搜索算法陷入了“高原搜索期”，就使用新的蒙特卡罗随机游走搜索算法（算法2）来快速找到一个出口跳出（第14行）。

算法2为随机游走搜索程序，采用Nakhost和Msller提出的蒙特卡罗搜索算法[15]。从原始节点s开始，其启发值为h*，使用一系列的随机游走搜索s点的邻居节点。如果一个节点的启发值小于h*，就返回该节点（第6行）。

每一次迭代使用不同的用于游走的参数l和n值。然后，游走访问新的节点s′。如果s′是死节点，算法将重新输入一个s节点。如果s′的启发值更小，则该节点将返回给算法1。另外，节点s′将被用作下一次游走的初始节点。该循环将会重复m次，只要找到一个节点的启发值小于h（*当前高原搜索期的一个出口状态），则立即退出搜索。

算法3详细描述了游走过程。给定初始节点s，算法3尝试n次，找到一条长为l的路径。该过程返回这n条路径中其中一条路径的终端节点，该终端节点具有最小启发值。

3 实验结果及分析

3.1 实验环境及度量标准

为检测算法的执行效率，通过实验将RWA*算法与A*算法和RW-BFS算法进行了对比。实验环境为CPU为英特尔酷睿i7-6700，主频3.40 GHz，内存4 G，Win7专业版，编程环境为Visual Studio 2010。实验数据来自全球航线网络，其中涉及3 769个节点和66 857条边。其中节点对应机场的名称，包括出发机场名称和到达机场名称，及它们各自的经度和纬度。两个节点之间的边表示两节点间存在直达航班。

本文提出的RWA*算法使用的评估函数为

其中：（fs）表示从初始节点经由节点s到目标节点的估计函数；g（s）表示源点到节点 s的实际距离；h（s）表示节点s到目标节点的球面距离。

3.2 实验结果与分析

实验结果如表1所示，第1列为路径搜索的起始节点和目标节点，第2、3、4列分别为A*算法、RWBFS算法和RWA*算法所用的搜索时间。第5、6、7列分别为A*算法、RW-BFS算法和RWA*算法在路径搜索过程中扩展的节点数。

由表1得出以下4点结论：

1）两项检测指标，即搜索用时和搜索过程中扩展节点数呈现正比关系。搜索过程中扩展的节点数越多，搜索用时就越长；

表1 20组实验结果Tab.1 20 sets of experimental results

2）RW-BFS算法比A*算法搜索用时平均减少22.93%，扩展节点数平均减少30.39%；

3）RWA*算法比RW-BFS算法搜索用时平均减少27.53%，扩展节点数平均减少12.01%；

4）算法中参数n和l的值关乎检测高原搜索期的敏感度，该检测不能太敏感也不能太迟钝，RWA*算法的搜索用时随着参数n和l的增大而变长。

由此得出，本文提出的新的检测A*算法是否陷入高原搜索期的方法优于RW-BFS算法中的检测高原搜索期的方法。

4 结语

针对A*算法中出现的高原搜索现象，本文提出了一种新的检测高原搜索期的方法，并且提出了一种基于随机游走的A*算法（RWA*），当检测到A*算法陷入高原搜索期时，使用随机游走帮助A*算法快速找到一个出口跳出高原搜索期。实验证明：RWA*算法的搜索时间和搜索过程中扩展的节点数两方面优于RWBFS算法，且发现搜索时间和搜索过程中扩展的节点数呈现正比的关系。

接下来的工作可以考虑使用多启发式评估函数。因为不同的启发式函数会以不同的排序方法排列open表中的节点，这样就会包括不同的搜索拓扑结构。当一个启发式函数在高原搜索期失去作用时，可以考虑使用其他启发式函数引导搜索跳出高原搜索期。

[1]胡 欣,徐 涛,丁晓璐,等.国际航线网络中K条最短路径算法改进与仿真[J].计算机应用,2014,34(4):1192-1195.

[2]DECHTER R,PEARL J.Generalized best-first search strategies and the optimality of A*[J].Journal of the ACM,1985,32(3):505-536.

[3]吕 强.面向高性能和表达力的自动规划[D].合肥:中国科学技术大学,2012.

[4]HELMERT M,ROGER G.How Good is Almost Perpect[C]//Proceedings of the AAAI Conference on Artificial Intelligence,2008:944-949.

[5]HAMPSON S,KIBLER D.Plateaus and Plateau Search in Boolean Satisfiability Problems:When to Give Up Searching and Start Again[C]//In the 2nd DIMACS Implementation Challenge,1993:437-456.

[6]FRANK J D,CHEESEMAN P,STUTZ J.When gravity fails:local search topology[J].Journal of Artificial Intelligence Research,1997(12):249-281.

[7]HOFFMANN J.Local Search Topology in Planning Benchmarks:An Empirical Analysis[C]//Proceedings of the International Joint Conference on Artificial Intelligence,2001:453-458.

[8]HOFFMANN J.Local Search Topology in Planning Benchmarks:A Theoretical Analysis[C]//Proceedings of the International Conference on AI Planning and Scheduling,2002:92-100.

[9]BENTONJ,TALAMADUPULAK,EYERICHP,etal.G-ValuePlateaus:Challenge for Planning[C]//Proceedings of the International Conference on Automated Planning and Scheduling,2010:259-262.

[10]GOVER F,LAGUNA M.Tabu Search[M].Boston:Kluwer Academic Publishers,1997.

[11]KAUTZ H,SEMAN B.Pushing the Envelope:Planning,Propositional Logic and Stochastic Search[C]//Proceedings of the AAAI Coference on Aritifical Intelligence,1996:1194-1201.

[12]NAKHOST H,MSLLER M.Monte-Carlo Exploration for Deterministic Planning[C]//IJCAI,2009:1766-1771.

[13]NAKHOSTH,HOFFMANNJ,MULLER M.Resource Constrained Planning:A Monte Carlo Random Walk Approach[C]//Proceedings of the Twenty-Second International Conference on Automated Planning and Scheduling(ICAPS-2012),2012:181-189.

[14]LU Qiang,XU You,HUANG Ruoyun,et al.The Roamer Planner Random-Walk Assisted Best-FirstSearch[C]//The2011 International Planning Competition,2011:73-76.

[15]NAKHOST H,MULLER M,VALENZANO R,et al.Arvand:The Art of Random Walks[C]//The 2011 International Planning Competition,2011:15-16.