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

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

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

2 啟發(fā)式算法

在狀態(tài)空間搜索時，為了更有效地搜索一個給定的狀態(tài)空間，可設(shè)計一個估價函數(shù)來決定每一次擴(kuò)展時，哪一個節(jié)點最有希望到達(dá)目標(biāo)節(jié)點，然后搜索就可能沿著某個被認(rèn)為是最有希望的節(jié)點向外擴(kuò)展。如果能夠給定一個比較合適的估價函數(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到目標(biāo)節(jié)點的一條最佳路徑的估計代價。f(n)的值就是從初始節(jié)點開始約束通過節(jié)點n的一條最佳路徑的代價，而最小的f(n)值的節(jié)點就是所估計的加有最少嚴(yán)格約束條件的節(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é)點），在每一步的估價中都把當(dāng)前的節(jié)點和以前的節(jié)點的估價值比較得到一個“最佳節(jié)點”，可以有效地防止“最佳節(jié)點”的丟失。

AStar算法是一種加上一些約束條件的最好優(yōu)先的算法。當(dāng)狀態(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到目標(biāo)的最短路徑的啟發(fā)值。由于f′(n)不可預(yù)知，其可近似于上面提到的f(n)。當(dāng)g(n)≥g′(n)時（通常情況下均滿足），g′(n)可由g(n)代替。當(dāng)h(n)≤h′(n)時，h′(n)可由h(n)代替。可以證明應(yīng)用這樣的估價函數(shù)是可以找到最短路徑的，也就是可采納的。

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

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

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

AStar算法示例AStar算法搜索時需設(shè)置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)，解求完成。

下面是相應(yīng)的偽程序：

Search()

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

while ( Open表非空 ) {

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

if (X是目標(biāo)節(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é)點進(jìn)行評估以確定最有可能到達(dá)目標(biāo)的節(jié)點，即“最佳節(jié)點”，從而極大地減少了對狀態(tài)空間的搜索過程，使其能快速求解出一條最佳路徑。估價函數(shù)的合理性直接決定AStar算法的執(zhí)行效率，合理的估價函數(shù)能極大提高算法效率。這使得AStar算法具體應(yīng)用時，應(yīng)根據(jù)實際需要設(shè)計啟發(fā)值，即確定估價函數(shù)，以使求解最優(yōu)。

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

參 考 文 獻(xiàn)

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

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

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

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

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

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