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

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

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

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

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

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

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

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

1.1 A*算法

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

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

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

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

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

1.2 蒙特卡羅隨機(jī)游走搜索

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

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

2 基于隨機(jī)游走的A*算法

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果及分析

3.1 實(shí)驗(yàn)環(huán)境及度量標(biāo)準(zhǔn)

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

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

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

3.2 實(shí)驗(yàn)結(jié)果與分析

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

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

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

表1 20組實(shí)驗(yàn)結(jié)果Tab.1 20 sets of experimental results

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

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

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

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

4 結(jié)語(yǔ)

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

接下來(lái)的工作可以考慮使用多啟發(fā)式評(píng)估函數(shù)。因?yàn)椴煌膯l(fā)式函數(shù)會(huì)以不同的排序方法排列open表中的節(jié)點(diǎn)，這樣就會(huì)包括不同的搜索拓?fù)浣Y(jié)構(gòu)。當(dāng)一個(gè)啟發(fā)式函數(shù)在高原搜索期失去作用時(shí)，可以考慮使用其他啟發(fā)式函數(shù)引導(dǎo)搜索跳出高原搜索期。

[1]胡 欣,徐 濤,丁曉璐,等.國(guó)際航線(xiàn)網(wǎng)絡(luò)中K條最短路徑算法改進(jìn)與仿真[J].計(jì)算機(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]呂 強(qiáng).面向高性能和表達(dá)力的自動(dòng)規(guī)劃[D].合肥:中國(guó)科學(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.