一種基于狀態(tài)空間的啟發(fā)式搜索算法及其實現(xiàn)

摘 要：深度優(yōu)先和廣度優(yōu)先搜索算法由于需遍歷所有狀態(tài)空間才能求出最佳解，使其在狀態(tài)空間較大時效率極低，此時必需采用啟發(fā)式算法實現(xiàn)快速求解。闡述啟發(fā)式搜索算法在狀態(tài)空間較大時的廣泛應用，深入分析一種啟發(fā)式算法－AStar算法實現(xiàn)快速求解的原理，并詳細介紹了其實現(xiàn)步驟及過程。最后，得出結(jié)論：基于合理估價函數(shù)的AStar算法能極大提高求解效率。

關鍵詞：啟發(fā)式算法；AStar算法；狀態(tài)空間；估價函數(shù)

中圖分類號：TP393 文獻標識碼：B 文章編號：1004373X(2008)1607902

Heuristic Search Algorithm and Its Implementation Based On State Space

ZHANG Sheng

(Communication and Command Academy，Wuhan，430010，China)

Abstract：Depthfirst and breadthfirst searching algorithm must traversal all state space to seek out the optimum solution，their efficiency is extremely low when the state space is big.In this case，heuristic algorithm can work quickly to get the solution.Heuristic algorithm′s wide application is stated in the large state space.Furthermore，one kind of Heuristic algorithm′s principleA-Star algorithm is analysed thoroughly，the process and the steps of its realization are described in details.Finally，a conclusion is drawn:AStar Algorithm based on reasonable evaluation function can improve the solution efficiency enormously.

Keywords：heuristic algorithm；AStar algorithm；state space；evaluation function

1 引 言

基于狀態(tài)空間的路徑搜索，即將問題求解過程表現(xiàn)為從初始狀態(tài)到目標狀態(tài)尋找路徑的過程，普通應用于各個領域。基于狀態(tài)空間的路徑搜索算法通常可分為3類：深度優(yōu)先搜索算法、寬度優(yōu)先搜索算法（或稱廣度優(yōu)先搜索算法）和啟發(fā)式搜索算法。前兩種算法均需在給定的狀態(tài)空間中窮舉，以求解中最佳路徑，其非常適合狀態(tài)空間不大時的求解，但當狀態(tài)空間十分大，且不預測的情況下，他們的效率極低，甚至不可完成。而啟發(fā)式搜索算法在狀態(tài)空間搜索時，對每一個搜索的節(jié)點進行評估，得到最佳的節(jié)點，再從這個節(jié)點進行搜索直到目標節(jié)點，可省略大量無謂的搜索路徑，極大提到效率，這使得其在狀態(tài)空間較大的領域得到了廣泛應用，如自駕車路線、網(wǎng)絡傳輸路徑、游戲中角色行走路線等。

2 啟發(fā)式算法

在狀態(tài)空間搜索時，為了更有效地搜索一個給定的狀態(tài)空間，可設計一個估價函數(shù)來決定每一次擴展時，哪一個節(jié)點最有希望到達目標節(jié)點，然后搜索就可能沿著某個被認為是最有希望的節(jié)點向外擴展。如果能夠給定一個比較合適的估價函數(shù)，將會大大的減少搜索工作量。對節(jié)點的估價十分重要，采用不同的估價可以有不同的效果。估價函數(shù)可表示為：f(n)=g(n)+h(n) 其中f(n)是節(jié)點n的估價函數(shù)；g(n)稱為“深度因子”，在狀態(tài)空間中從初始節(jié)點到節(jié)點n的一條最佳路徑的實際代價；h(n)是從節(jié)點n到目標節(jié)點的一條最佳路徑的估計代價。f(n)的值就是從初始節(jié)點開始約束通過節(jié)點n的一條最佳路徑的代價，而最小的f(n)值的節(jié)點就是所估計的加有最少嚴格約束條件的節(jié)點。不難發(fā)現(xiàn)，搜索的啟發(fā)信息主要由h(n)來體現(xiàn)，因為g(n)是已知的，其代表了搜索的廣度的優(yōu)先趨勢。

3 AStar算法

啟發(fā)式搜索算法有局部擇優(yōu)搜索法、最好優(yōu)先搜索法等。其均使用了啟發(fā)函數(shù)，但在具體的選取最佳搜索節(jié)點時策略不同。如局部擇優(yōu)搜索法在搜索的過程中選取“最佳節(jié)點”后舍棄其他的兄弟節(jié)點和父親節(jié)點，而一直搜索下去。由于其舍棄了其他的節(jié)點，可能也把最好的節(jié)點舍棄，因為求解的最佳節(jié)點只是在該階段的最佳并不一定是全局的最佳。最好優(yōu)先算法克服了這種不足，在搜索時，并沒有舍棄節(jié)點（除非該節(jié)點是死節(jié)點），在每一步的估價中都把當前的節(jié)點和以前的節(jié)點的估價值比較得到一個“最佳節(jié)點”，可以有效地防止“最佳節(jié)點”的丟失。

AStar算法是一種加上一些約束條件的最好優(yōu)先的算法。當狀態(tài)空間較大時，希望能夠求解出狀態(tài)空間搜索的最短路徑，即用最快的方法求解問題，AStar算法正是基于這種思想。

如果一個估價函數(shù)可以找出最短的路徑，稱之為可采納性。AStar算法是一個可采納的最好優(yōu)先算法。AStar算法的估價函數(shù)可表示為：f′(n)=g′(n)+h′(n) 其中，f′(n)是估價函數(shù)；g′(n)是起點到節(jié)點n的最短路徑值；h′(n)是節(jié)點n到目標的最短路徑的啟發(fā)值。由于f′(n)不可預知，其可近似于上面提到的f(n)。當g(n)≥g′(n)時（通常情況下均滿足），g′(n)可由g(n)代替。當h(n)≤h′(n)時，h′(n)可由h(n)代替。可以證明應用這樣的估價函數(shù)是可以找到最短路徑的，也就是可采納的。

應用此估價函數(shù)的最好優(yōu)先算法即AStar算法，其在每一步的估價時，把比較當前節(jié)點和以前節(jié)點的估價值，以確定“最佳節(jié)點”。

4 A算法實現(xiàn)步驟及過程

如圖1所示狀態(tài)空間A到N，欲用AStar算法求起始節(jié)點A到目標節(jié)點M的路徑，括號內(nèi)為該節(jié)點的估價值。

AStar算法示例AStar算法搜索時需設置2個表：OPEN表和CLOSED表。OPEN表保存所有已生成而未考察的節(jié)點，CLOSED 表記錄已訪問過的節(jié)點。算法中有一步為根據(jù)估價函數(shù)重排OPEN表。這使得循環(huán)的每一步只需考慮OPEN表中狀態(tài)最好的節(jié)點。具體搜索過程如下：

Step 1:狀態(tài)初使化

OPEN=｛A(6)｝；CLOSED={}；

Step 2:估算A(6)，取得所有子節(jié)點，并放入OPEN表中；

OPEN={B(4)，C(4)，D(5)}；CLOSED={A(6)}；

Step 3:估算B(4)，取得所有子節(jié)點，并放入OPEN表中；

OPEN={C(4)，E(5)，D(5)］；CLOSED={B(4)，A(6)}；

Step 4:估算C(4)；取得所有子節(jié)點，并放入OPEN表中；

OPEN={G(3)，F(xiàn)(4)，E(5)，D(5)}；CLOSED={C(4)，

B(4)，A(6)}；

Step 5:估算G(3)，取得所有子節(jié)點，并放入OPEN表中；

OPEN={L(2)，M(3)，F(xiàn)(4)，E(5)，D(5)}；CLOSED=

{G(3)，C(4)，B(4)，A(6)}；

Step 6:估算L(2)，取得所有子節(jié)點，并放入OPEN表中；

OPEN={M(3)，F(xiàn)(4)，E(5)，D(5)}；CLOSED={ L(2)，

G(3)，C(4)，B(4)，A(6)}；

Step 7:估算M(3)，解求完成。

下面是相應的偽程序：

Search()

{ Open = ［起始節(jié)點］; Closed = ［］;

while ( Open表非空 ) {

從Open中取得1個節(jié)點X，并從OPEN表中刪除。

if (X是目標節(jié)點) {

求得路徑PATH；返回路徑PATH；}

for (每一個X的子節(jié)點Y){

if( Y不在OPEN表和CLOSE表中 ){

求Y的估價值；并將Y插入OPEN表中；}

else

if( Y在OPEN表中 ) {

if( Y的估價值小于OPEN表的估價值 )

更新OPEN表中的估價值；}

else //Y在CLOSE表中 {

if( Y的估價值小于CLOSE表的估價值 ){

更新CLOSE表中的估價值；

從CLOSE表中移出節(jié)點，并放入OPEN表中；}

}

將X節(jié)點插入CLOSE表中；

按照估價值將OPEN表中的節(jié)點排序；

}//end for

}//end while

}//end function

5 結(jié) 語

分析AStar算法原則后，不難發(fā)現(xiàn)AStar算法由于采用估價函數(shù)，對各個節(jié)點進行評估以確定最有可能到達目標的節(jié)點，即“最佳節(jié)點”，從而極大地減少了對狀態(tài)空間的搜索過程，使其能快速求解出一條最佳路徑。估價函數(shù)的合理性直接決定AStar算法的執(zhí)行效率，合理的估價函數(shù)能極大提高算法效率。這使得AStar算法具體應用時，應根據(jù)實際需要設計啟發(fā)值，即確定估價函數(shù)，以使求解最優(yōu)。

如應用于自駕車路線時，節(jié)點n到目標的最短路徑的啟發(fā)值h′(n)可由第n點的經(jīng)緯度和目標點的經(jīng)緯度通過距離計算得到。

參 考 文 獻

［1］蔡自興.人工智能及其應用［M］.北京：清華大學出版社，1997.

［2］NilssonNJ.人工智能［M］.鄭扣根，莊越挺，譯.北京：機械工業(yè)出版社，2000.

［3］嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)［M］ 北京：清華大學出版社，1999.

［4］叢明煜，王麗萍.現(xiàn)代啟發(fā)式算法理論研究［J］.高技術(shù)通訊，2003，13(5)：105110.

［5］王瀟瀟，韓家新，馬剛.一種啟發(fā)式的足球機器人傳球路徑搜索算法\\.現(xiàn)代電子技術(shù)，2007，30(20):7576，79.

作者簡介 張 勝 男，1979年出生，湖北潛江人，講師。主要研究方向為信息系統(tǒng)集成、數(shù)據(jù)挖掘。