一種基于隨機游走的A*算法

劉浩翰，郭晶晶，李建伏，馮 梅，賀懷清

（1.中國民航大學(xué)計算機科學(xué)與技術(shù)學(xué)院，天津 300300；2.中國民用航空華北地區(qū)空中交通管理局，北京 100621）

最短路徑問題是圖論中的一個重要研究課題，其目的是在多項式時間內(nèi)找到圖中任意兩節(jié)點之間的最短路徑[1]。最短路徑搜索算法有Dijkstra算法、Floyd算法和A*算法[2]等。A*算法的基本策略是在啟發(fā)式函數(shù)的引導(dǎo)下，優(yōu)先擴展最有希望盡快到達目標(biāo)節(jié)點的節(jié)點。與Dijkstra算法、Floyd算法相比，A*無須擴展所有節(jié)點，具有較高的搜索效率。

在實際應(yīng)用中，A*算法的搜索效率在很大程度上依賴于啟發(fā)式函數(shù)的質(zhì)量。一個理想的啟發(fā)式可以使得搜索節(jié)點數(shù)目為O（|L|），L是找到的解的長度（從初始節(jié)點到目標(biāo)節(jié)點的節(jié)點個數(shù)）[3]。然而找到一個完美的啟發(fā)式函數(shù)是不可能的，現(xiàn)實中往往只能犧牲搜索效率而選擇近似最優(yōu)的啟發(fā)式函數(shù)[4]。

在A*搜索過程中，經(jīng)常會陷入高原搜索期，即對任意節(jié)點S，假設(shè)當(dāng)前搜索過的所有節(jié)點的最小啟發(fā)式函數(shù)值為h*（S），顯然，h*隨著搜索過程單調(diào)遞減，并且在遇到目標(biāo)節(jié)點時變?yōu)?，但是在A*搜索的大部分時間里，h*并沒有隨著更多節(jié)點的展開而減小，這樣的搜索過程被稱為“高原搜索”（plateauexploration）[3]。當(dāng)搜索陷入高原搜索期時，A*算法的性能急劇下降。而研究表明，啟發(fā)式搜索中普遍存在著高原搜索現(xiàn)象[5-9]。

如何及時地識別并跳出高原搜索期對提高整個A*算法的性能至關(guān)重要。針對這一問題已開展了很多相關(guān)研究，如狀態(tài)空間約簡技術(shù)[10-11]、蒙特卡羅隨機游走搜索[12-14]等。由于易于實現(xiàn)，蒙特卡羅隨機游走算法更為流行。其基本思路為，當(dāng)檢測到搜索陷入高原搜索期時，采用隨機游走策略幫助其迅速跳出。

本文結(jié)合蒙特卡羅隨機游走算法，提出了一種改進的 A*算法（RWA*，A*algorithmbasedonrandomwalk）。與現(xiàn)有的隨機游走協(xié)助下的最好優(yōu)先搜索算法[14]不同，RWA*采用了一種新的檢測高原搜索期的方法，即當(dāng)連續(xù)擴展n次節(jié)點的啟發(fā)值都比上一次最后擴展出的節(jié)點的啟發(fā)值大時，則認為搜索陷入高原搜索期。

1 A*算法與蒙特卡羅隨機游走搜索

1.1 A*算法

A*算法是一種靜態(tài)路網(wǎng)中求解最短路徑較有效的直接搜索方法。算法每次選擇具有最小啟發(fā)值的節(jié)點進行擴展，直到找到目標(biāo)節(jié)點。通常使用open表和closed表維護算法搜索過程中產(chǎn)生的節(jié)點，open表保存已產(chǎn)生并待擴展的節(jié)點，closed表保存已被擴展的節(jié)點。

算法通過啟發(fā)函數(shù)對節(jié)點狀態(tài)進行估價，啟發(fā)函數(shù)的形式一般為

其中：g（S）表示狀態(tài)空間中從初始節(jié)點到當(dāng)前節(jié)點S的實際代價；h（S）表示從節(jié)點S到目標(biāo)節(jié)點最佳路徑的估計代價。

從理論上講，一個完全正確的啟發(fā)函數(shù)可以迅速得到問題的正確解，并保證h（S）隨著搜索過程單調(diào)遞減，在遇到目標(biāo)節(jié)點時變?yōu)?。但一般完全正確的啟發(fā)函數(shù)是得不到的，h（S）并沒有單調(diào)遞減，從而使算法在搜索過程中出現(xiàn)高原搜索現(xiàn)象。

本文提出新的檢測高原搜索期的方法，即若x次當(dāng)前待擴展節(jié)點的啟發(fā)值大于上次擴展節(jié)點時最后一個被擴展出的節(jié)點的啟發(fā)值，即節(jié)點出現(xiàn)了一定的相似性，則認為算法陷入了高原搜索期。再使用蒙特卡羅隨機游走尋找出口迅速跳出高原搜索期。

1.2 蒙特卡羅隨機游走搜索

蒙特卡羅隨機游走搜索使用隨機游走跳躍搜索當(dāng)前狀態(tài)的一個鄰居狀態(tài)，它重復(fù)循環(huán)該過程直到尋找到目標(biāo)狀態(tài)。如果在m次跳躍搜索后，所有狀態(tài)的最小啟發(fā)函數(shù)值仍然沒有減小，或遇到終端狀態(tài)，蒙特卡羅隨機游走會回到初始狀態(tài)重新開始搜索。

隨機游走搜索每次從一個狀態(tài)開始搜索其鄰居狀態(tài)空間，試圖找到一個具有更小啟發(fā)式函數(shù)值的狀態(tài)。在最多n次的循環(huán)中，它每次搜索一條路徑，計算每條路徑末尾狀態(tài)的啟發(fā)式函數(shù)值，如果其值小于已搜索路徑的最小值，則更新節(jié)點和節(jié)點的啟發(fā)式函數(shù)值。最后返回具有最小啟發(fā)式函數(shù)值的狀態(tài)。

2 基于隨機游走的A*算法

本文提出的基于隨機游走的A*算法的基本結(jié)構(gòu)，與一般的基于隨機游走的A*算法相同，即當(dāng)檢測到搜索陷入高原搜索期時，采用隨機游走策略幫助搜索迅速跳出高原搜索期。與一般的基于隨機游走的A*算法不同的是高原搜索期的檢測方法。

在該算法中，若x次當(dāng)前待擴展節(jié)點的啟發(fā)值大于上次擴展節(jié)點時最后一個被擴展出的節(jié)點的啟發(fā)值時，即節(jié)點出現(xiàn)了一定的相似性，則認為算法陷入了高原搜索期。算法表示如下：

算法1為本文提出的RWA*算法。RWA*算法在標(biāo)準A*算法的基礎(chǔ)上增加了擴展新節(jié)點后的“高原搜索期”檢測（第13行）。如果檢測到搜索算法陷入了“高原搜索期”，就使用新的蒙特卡羅隨機游走搜索算法（算法2）來快速找到一個出口跳出（第14行）。

算法2為隨機游走搜索程序，采用Nakhost和Msller提出的蒙特卡羅搜索算法[15]。從原始節(jié)點s開始，其啟發(fā)值為h*，使用一系列的隨機游走搜索s點的鄰居節(jié)點。如果一個節(jié)點的啟發(fā)值小于h*，就返回該節(jié)點（第6行）。

每一次迭代使用不同的用于游走的參數(shù)l和n值。然后，游走訪問新的節(jié)點s′。如果s′是死節(jié)點，算法將重新輸入一個s節(jié)點。如果s′的啟發(fā)值更小，則該節(jié)點將返回給算法1。另外，節(jié)點s′將被用作下一次游走的初始節(jié)點。該循環(huán)將會重復(fù)m次，只要找到一個節(jié)點的啟發(fā)值小于h（*當(dāng)前高原搜索期的一個出口狀態(tài)），則立即退出搜索。

算法3詳細描述了游走過程。給定初始節(jié)點s，算法3嘗試n次，找到一條長為l的路徑。該過程返回這n條路徑中其中一條路徑的終端節(jié)點，該終端節(jié)點具有最小啟發(fā)值。

3 實驗結(jié)果及分析

3.1 實驗環(huán)境及度量標(biāo)準

為檢測算法的執(zhí)行效率，通過實驗將RWA*算法與A*算法和RW-BFS算法進行了對比。實驗環(huán)境為CPU為英特爾酷睿i7-6700，主頻3.40 GHz，內(nèi)存4 G，Win7專業(yè)版，編程環(huán)境為Visual Studio 2010。實驗數(shù)據(jù)來自全球航線網(wǎng)絡(luò)，其中涉及3 769個節(jié)點和66 857條邊。其中節(jié)點對應(yīng)機場的名稱，包括出發(fā)機場名稱和到達機場名稱，及它們各自的經(jīng)度和緯度。兩個節(jié)點之間的邊表示兩節(jié)點間存在直達航班。

本文提出的RWA*算法使用的評估函數(shù)為

其中：（fs）表示從初始節(jié)點經(jīng)由節(jié)點s到目標(biāo)節(jié)點的估計函數(shù)；g（s）表示源點到節(jié)點 s的實際距離；h（s）表示節(jié)點s到目標(biāo)節(jié)點的球面距離。

3.2 實驗結(jié)果與分析

實驗結(jié)果如表1所示，第1列為路徑搜索的起始節(jié)點和目標(biāo)節(jié)點，第2、3、4列分別為A*算法、RWBFS算法和RWA*算法所用的搜索時間。第5、6、7列分別為A*算法、RW-BFS算法和RWA*算法在路徑搜索過程中擴展的節(jié)點數(shù)。

由表1得出以下4點結(jié)論：

1）兩項檢測指標(biāo)，即搜索用時和搜索過程中擴展節(jié)點數(shù)呈現(xiàn)正比關(guān)系。搜索過程中擴展的節(jié)點數(shù)越多，搜索用時就越長；

表1 20組實驗結(jié)果Tab.1 20 sets of experimental results

2）RW-BFS算法比A*算法搜索用時平均減少22.93%，擴展節(jié)點數(shù)平均減少30.39%；

3）RWA*算法比RW-BFS算法搜索用時平均減少27.53%，擴展節(jié)點數(shù)平均減少12.01%；

4）算法中參數(shù)n和l的值關(guān)乎檢測高原搜索期的敏感度，該檢測不能太敏感也不能太遲鈍，RWA*算法的搜索用時隨著參數(shù)n和l的增大而變長。

由此得出，本文提出的新的檢測A*算法是否陷入高原搜索期的方法優(yōu)于RW-BFS算法中的檢測高原搜索期的方法。

4 結(jié)語

針對A*算法中出現(xiàn)的高原搜索現(xiàn)象，本文提出了一種新的檢測高原搜索期的方法，并且提出了一種基于隨機游走的A*算法（RWA*），當(dāng)檢測到A*算法陷入高原搜索期時，使用隨機游走幫助A*算法快速找到一個出口跳出高原搜索期。實驗證明：RWA*算法的搜索時間和搜索過程中擴展的節(jié)點數(shù)兩方面優(yōu)于RWBFS算法，且發(fā)現(xiàn)搜索時間和搜索過程中擴展的節(jié)點數(shù)呈現(xiàn)正比的關(guān)系。

接下來的工作可以考慮使用多啟發(fā)式評估函數(shù)。因為不同的啟發(fā)式函數(shù)會以不同的排序方法排列open表中的節(jié)點，這樣就會包括不同的搜索拓撲結(jié)構(gòu)。當(dāng)一個啟發(fā)式函數(shù)在高原搜索期失去作用時，可以考慮使用其他啟發(fā)式函數(shù)引導(dǎo)搜索跳出高原搜索期。

[1]胡 欣,徐 濤,丁曉璐,等.國際航線網(wǎng)絡(luò)中K條最短路徑算法改進與仿真[J].計算機應(yīng)用,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]呂 強.面向高性能和表達力的自動規(guī)劃[D].合肥:中國科學(xué)技術(shù)大學(xué),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.