A*算法

第一部分： A* 算法簡介?
寫這篇文章的初衷是應一個網友的要求，當然我也發現現在有關人工智能的中文站點實在太少，我在這里拋磚引玉，希望大家都來熱心的參與。?
還是說正題，我先拿A*算法開刀，是因為A*在游戲中有它很典型的用法，是人工智能在游戲中的代表。?
A*算法在人工智能中是一種典型的啟發式搜索算法，為了說清楚A*算法，我看還是先說說何謂啟發式算法。?

一、何謂啟發式搜索算法： ?

在說它之前先提提狀態空間搜索。狀態空間搜索，如果按專業點的說法就是將問題求解過程表現為從 初始狀態到目標狀態尋找這個路徑的過程。通俗點說，就是在解一個問題時，找到一條解題的過程可以從 求解的開始到問題的結果（好象并不通俗哦）。由于求解問題的過程中分枝有很多，主要是求解過程中求 解條件的不確定性，不完備性造成的，使得求解的路徑很多這就構成了一個圖，我們說這個圖就是狀態空 間。問題的求解實際上就是在這個圖中找到一條路徑可以從開始到結果。這個尋找的過程就是狀態空間搜 索。 ?

常用的狀態空間搜索有深度優先和廣度優先。廣度優先是從初始狀態一層一層向下找，直到找到目標 為止。深度優先是按照一定的順序前查找完一個分支，再查找另一個分支，以至找到目標為止。這兩種算 法在數據結構書中都有描述，可以參看這些書得到更詳細的解釋。 ?

前面說的廣度和深度優先搜索有一個很大的缺陷就是他們都是在一個給定的狀態空間中窮舉。這在狀 態空間不大的情況下是很合適的算法，可是當狀態空間十分大，且不預測的情況下就不可取了。他的效率 實在太低，甚至不可完成。在這里就要用到啟發式搜索了。 ?

啟發式搜索就是在狀態空間中的搜索對每一個搜索的位置進行評估，得到最好的位置，再從這個位置 進行搜索直到目標。這樣可以省略大量無畏的搜索路徑，提到了效率。在啟發式搜索中，對位置的估價是 十分重要的。采用了不同的估價可以有不同的效果。我們先看看估價是如何表示的。 ?

啟發中的估價是用估價函數表示的，如： ?

f(n) = g(n) + h(n) ?

其中 f(n) 是節點 n 的估價函數， g(n) 實在狀態空間中從初始節點到 n 節點的實際代價， h(n) 是從 n 到目 標節點最佳路徑的估計代價。在這里主要是 h(n) 體現了搜索的啟發信息，因為 g(n) 是已知的。如果說詳細 點， g(n) 代表了搜索的廣度的優先趨勢。但是當 h(n) >> g(n) 時，可以省略 g(n), 而提高效率。這些就深了， 不懂也不影響啦！我們繼續看看何謂 A* 算法。 ?

二、初識 A* 算法： ?

啟發式搜索其實有很多的算法，比如：局部擇優搜索法、最好優先搜索法等等。當然 A* 也是。這些算法 都使用了啟發函數，但在具體的選取最佳搜索節點時的策略不同。象局部擇優搜索法，就是在搜索的過程中 選取“最佳節點”后舍棄其他的兄弟節點，父親節點，而一直得搜索下去。這種搜索的結果很明顯，由于舍 棄了其他的節點，可能也把最好的節點都舍棄了，因為求解的最佳節點只是在該階段的最佳并不一定是全局 的最佳。最好優先就聰明多了，他在搜索時，便沒有舍棄節點（除非該節點是死節點），在每一步的估價中 都把當前的節點和以前的節點的估價值比較得到一個“最佳的節點”。這樣可以有效的防止“最佳節點”的 丟失。那么 A* 算法又是一種什么樣的算法呢？其實 A* 算法也是一種最好優先的算法。只不過要加上一些約束 條件罷了。由于在一些問題求解時，我們希望能夠求解出狀態空間搜索的最短路徑，也就是用最快的方法求 解問題， A* 就是干這種事情的！我們先下個定義，如果一個估價函數可以找出最短的路徑，我們稱之為可采 納性。 A* 算法是一個可采納的最好優先算法。 A* 算法的估價函數克表示為： ?

f'(n) = g'(n) + h'(n) ?

這里， f'(n) 是估價函數， g'(n) 是起點到終點的最短路徑值， h'(n) 是 n 到目標的最斷路經的啟發值。由 于這個 f'(n) 其實是無法預先知道的，所以我們用前面的估價函數 f(n) 做近似。 g(n) 代替 g'(n) ，但 g(n)>=g'(n) 才可（大多數情況下都是滿足的，可以不用考慮）， h(n) 代替 h'(n) ，但 h(n)<=h'(n) 才可（這一點特別的重 要）。可以證明應用這樣的估價函數是可以找到最短路徑的，也就是可采納的。我們說應用這種估價函數的 最好優先算法就是 A* 算法。哈！你懂了嗎？肯定沒懂！接著看！ ?
?

舉一個例子，其實廣度優先算法就是 A* 算法的特例。其中 g(n) 是節點所在的層數， h(n)=0 ，這種 h(n) 肯 定小于 h'(n) ，所以由前述可知廣度優先算法是一種可采納的。實際也是。當然它是一種最臭的 A* 算法。 ?

再說一個問題，就是有關 h(n) 啟發函數的信息性。 h(n) 的信息性通俗點說其實就是在估計一個節點的值 時的約束條件，如果信息越多或約束條件越多則排除的節點就越多，估價函數越好或說這個算法越好。這就 是為什么廣度優先算法的那么臭的原因了，誰叫它的 h(n)=0 ，一點啟發信息都沒有。但在游戲開發中由于實 時性的問題， h(n) 的信息越多，它的計算量就越大，耗費的時間就越多。就應該適當的減小 h(n) 的信息，即 減小約束條件。但算法的準確性就差了，這里就有一個平衡的問題。可難了，這就看你的了！ ?

好了我的話也說得差不多了，我想你肯定是一頭的霧水了，其實這是寫給懂 A* 算法的同志看的。哈哈！ 你還是找一本人工智能的書仔細看看吧！我這幾百字是不足以將 A* 算法講清楚的。只是起到拋磚引玉的作用 希望大家熱情參與嗎！ ?

預知 A* 算法的應用，請看《深入 A* 算法》。

?

第二部分：深入 A* 算法———淺析 A* 算法在搜索最短路徑中的應用

一、前言 ?

在這里我將對 A* 算法的實際應用進行一定的探討，并且舉一個有關 A* 算法在最短路徑搜索 的例子。值得注意的是這里并不對 A* 的基本的?

概念作介紹，如果你還對 A* 算法不清楚的話， 請看姊妹篇《初識 A* 算法》。 ?

這里所舉的例子是參考 AMIT 主頁中的一個源程序，你可以在 AMIT 的站點上下載也可以在我 的站點上下載。你使用這個源程序時，應該遵?

守一定的公約。 ?

二、 A* 算法的程序編寫原理 ?

我在《初識 A* 算法》中說過， A* 算法是最好優先算法的一種。只是有一些約束條件而已。 我們先來看看最好優先算法是如何編寫的吧。 ?

如圖有如下的狀態空間：（起始位置是 A ，目標位置是 P ，字母后的數字表示節點的估價值） ?

?

搜索過程中設置兩個表： OPEN 和 CLOSED 。 OPEN 表保存了所有已生成而未考察的節點， CLOSED 表中記錄已訪問過的節點。算法中有一步是?

根據估價函數重排 OPEN 表。這樣循環中的每一 步只考慮 OPEN 表中狀態最好的節點。具體搜索過程如下： ?
?

??????1）初始狀態：???

?????????????OPEN=[A5]；CLOSED=[]；

??????2）估算A5，取得搜有子節點，并放入OPEN表中；

?????????????OPEN=[B4，C4，D6]；CLOSED=[A5]

??????3）估算B4，取得搜有子節點，并放入OPEN表中；

?????????????OPEN=[C4，E5，F5，D6]；CLOSED=[B4，A5]

??????4）估算C4；取得搜有子節點，并放入OPEN表中；

?????????????OPEN=[H3，G4，E5，F5，D6]；CLOSED=[C4，B4，A5]

??????5）估算H3，取得搜有子節點，并放入OPEN表中；

?????????????OPEN=[O2，P3，G4，E5，F5，D6]；CLOSED=H3C4，B4，A5]

??????6）估算O2，取得搜有子節點，并放入OPEN表中；

?????????????OPEN=[P3，G4，E5，F5，D6]；CLOSED=[O2，H3，C4，B4，A5]

??????7）估算P3，已得到解；?

看了具體的過程，再看看偽程序吧。算法的偽程序如下： ??

??????Best_First_Search()

?????? {

??????Open? = ?[起始節點];?Closed? = ?[];

?????? while ?(?Open表非空?)

?????? {

??????????從Open中取得一個節點X，并從OPEN表中刪除。

?????????? if ?(X是目標節點)

?????????? {

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

????????????}

?????????? for ?(每一個X的子節點Y)

?????????? {

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

????????????? {

????????????????求Y的估價值；并將Y插入OPEN表中； // 還沒有排序

?????????????}

????????????? else

????????????????? if (?Y在OPEN表中?)

????????????????? {

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

????????????????????????更新OPEN表中的估價值；?

?????????????????}

????????????????? else ?? // Y在CLOSE表中

???????????????????? {

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

???????????????????? {

????????????????????????更新CLOSE表中的估價值；?

????????????????????????從CLOSE表中移出節點，并放入OPEN表中；

????????????????????}

?????????????????}

??????????????將X節點插入CLOSE表中；

??????????????按照估價值將OPEN表中的節點排序；

?????????????} // end?for

??????} // end?while

??????} // end?func?

啊！偽程序出來了，寫一個源程序應該不是問題了，依葫蘆畫瓢就可以。 A* 算法的程序與此 是一樣的，只要注意估價函數中的 g(n) 的 h(n) 約束條件就可以了。不清楚的可以看看《初識 A* 算法》。好了，我們可以進入另一個重要的話題，用 A* 算法實現最短路徑的搜索。在此之 前你最好認真的理解前面的算法。不清楚可以找我。我的 Email 在文章尾。 ?

三、用 A* 算法實現最短路徑的搜索 ?

在游戲設計中，經常要涉及到最短路徑的搜索，現在一個比較好的方法就是用 A* 算法進行設 計。他的好處我們就不用管了，反正就是好！ ^_* ?

注意下面所說的都是以 ClassAstar 這個程序為藍本，你可以在這里下載這個程序。這個程 序是一個完整的工程。里面帶了一個 EXE 文件。可以先看看。 ?

先復習一下， A* 算法的核心是估價函數 f(n) ，它包括 g(n) 和 h(n) 兩部分。 g(n) 是已經走過的 代價， h(n) 是 n 到目標的估計代價。在這個例子中 g(n) 表示在狀態空間從起始節點到 n 節點的 深度， h(n) 表示 n 節點所在地圖的位置到目標位置的直線距離。啊！一個是狀態空間，一個是 實際的地圖，不要搞錯了。再詳細點說，有一個物體 A ，在地圖上的坐標是 (xa,ya) ， A 所要到 達的目標 b 的坐標是 (xb,yb) 。則開始搜索時，設置一個起始節點 1 ，生成八個子節點 2 - 9 因 為有八個方向。如圖： ?

?

仔細看看節點 1 、 9 、 17 的 g(n) 和 h(n) 是怎么計算的。現在應該知道了下面程序中的 f(n) 是如何 計算的吧。開始講解源程序了。其實這個程序是一個很典型的教科書似的程序，也就是說只要 你看懂了上面的偽程序，這個程序是十分容易理解的。不過他和上面的偽程序有一些的不同， 我在后面會提出來。 ?

先看搜索主函數： ??

?????? void ?AstarPathfinder::FindPath( int ?sx,? int ?sy,? int ?dx,? int ?dy)

?????? {

?????????NODE? * Node,? * BestNode;

????????? int ?TileNumDest;

??????????? // 得到目標位置，作判斷用

?????????TileNumDest? = ?TileNum(sx,?sy);

????????? // 生成Open和Closed表

?????????OPEN = (?NODE * ?)calloc( 1 , sizeof (?NODE?));

?????????CLOSED = (?NODE * ?)calloc( 1 , sizeof (?NODE?));

????????? // 生成起始節點，并放入Open表中

?????????Node = (?NODE * ?)calloc( 1 , sizeof (?NODE?));

?????????Node -> g? = ? 0 ;

????????? // 這是計算h值?

?????????Node -> h? = ?(dx - sx) * (dx - sx)? + ?(dy - sy) * (dy - sy);?? // ?should?really?use?sqrt().

????????? // 這是計算f值，即估價值

?????????Node -> f? = ?Node -> g + Node -> h;

?????????Node -> NodeNum? = ?TileNum(dx,?dy);

?????????Node -> x? = ?dx;

?????????Node -> y? = ?dy;

????????

?????????OPEN -> NextNode = Node;???????? // ?make?Open?List?point?to?first?node

????????? for ?(;;)

????????? {???? // 從Open表中取得一個估價值最好的節點

?????????????BestNode = ReturnBestNode();

????????????? // 如果該節點是目標節點就退出

????????????? if ?(BestNode -> NodeNum? == ?TileNumDest)???? // ?if?we've?found?the?end,?break?and?finish

????????????????? break ;

????????????? // 否則生成子節點

?????????????GenerateSuccessors(BestNode,sx,sy);

?????????}

?????????PATH? = ?BestNode;

??????} ?

??????void?AstarPathfinder::GenerateSuccessors(NODE?*BestNode,?int?dx,?int?dy)

??????{

?????????int?x,?y;

?????????//哦！依次生成八個方向的子節點，簡單！

????????????????????????//?Upper-Left

????????if?(?FreeTile(x=BestNode->x-TILESIZE,?y=BestNode->y-TILESIZE)?)

????????????GenerateSucc(BestNode,x,y,dx,dy);

????????????????????????//?Upper

?????????if?(?FreeTile(x=BestNode->x,?y=BestNode->y-TILESIZE)?)

????????????GenerateSucc(BestNode,x,y,dx,dy);

????????????????????????//?Upper-Right

?????????if?(?FreeTile(x=BestNode->x+TILESIZE,?y=BestNode->y-TILESIZE)?)

????????????GenerateSucc(BestNode,x,y,dx,dy);

????????????????????????//?Right

?????????if?(?FreeTile(x=BestNode->x+TILESIZE,?y=BestNode->y)?)

????????????GenerateSucc(BestNode,x,y,dx,dy);

????????????????????????//?Lower-Right

?????????if?(?FreeTile(x=BestNode->x+TILESIZE,?y=BestNode->y+TILESIZE)?)

????????????GenerateSucc(BestNode,x,y,dx,dy);

????????????????????????//?Lower

?????????if?(?FreeTile(x=BestNode->x,?y=BestNode->y+TILESIZE)?)

????????????GenerateSucc(BestNode,x,y,dx,dy);

????????????????????????//?Lower-Left

?????????if?(?FreeTile(x=BestNode->x-TILESIZE,?y=BestNode->y+TILESIZE)?)

????????????GenerateSucc(BestNode,x,y,dx,dy);

????????????????????????//?Left

?????????if?(?FreeTile(x=BestNode->x-TILESIZE,?y=BestNode->y)?)

????????????GenerateSucc(BestNode,x,y,dx,dy);

??????}?

??????void?AstarPathfinder::GenerateSucc(NODE?*BestNode,int?x,?int?y,?int?dx,?int?dy)

??????{

?????????int?g,?TileNumS,?c?=?0;

?????????NODE?*Old,?*Successor;

?????????//計算子節點的?g?值??

?????????g?=?BestNode->g+1;?????//?g(Successor)=g(BestNode)+cost?of?getting?from?BestNode?to?Successor

?????????TileNumS?=?TileNum(x,y);??//?identification?purposes

?????????//子節點再Open表中嗎？?

?????????if?(?(Old=CheckOPEN(TileNumS))?!=?NULL?)?//?if?equal?to?NULL?then?not?in?OPEN?list,?else?it?returns?the?Node?in?Old

?????????{

?????????????//若在

?????????????for(?c?=?0;?c?<8;?c++)?if(?BestNode->Child[c]?==?NULL?)?//?Add?Old?to?the?list?of?BestNode's?Children?(or?Successors).

???????????break;

?????????????BestNode->Child[c]?=?Old;

?????????????//比較Open表中的估價值和當前的估價值（只要比較g值就可以了）

?????????????if?(?g?g?)??//?if?our?new?g?value?is?Parent?=?BestNode;

???????????Old->g?=?g;

??????????Old->f?=?g?+?Old->h;

?????????????}

?????????}

?????????else?//在Closed表中嗎？

?????????if?(?(Old=CheckCLOSED(TileNumS))?!=?NULL?)?//?if?equal?to?NULL?then?not?in?OPEN?list,?else?it?returns?the?Node?in?Old

?????????{

??????????//若在

??????????????for(?c?=?0;?c<8;?c++)?if?(?BestNode->Child[c]?==?NULL?)?//?Add?Old?to?the?list?of?BestNode's?Children?(or?Successors).

???????????break;

?????????????BestNode->Child[c]?=?Old;

?????????????//比較Closed表中的估價值和當前的估價值（只要比較g值就可以了）

?????????????if?(?g?g?)??//?if?our?new?g?value?is?Parent?=?BestNode;

??????????????Old->g?=?g;

??????????????Old->f?=?g?+?Old->h;

?????????????????//再依次更新Old的所有子節點的估價值

??????????????PropagateDown(Old);??//?Since?we?changed?the?g?value?of?Old,?we?need

???????????????????????????????????//?to?propagate?this?new?value?downwards,?i.e.

???????????????????????????????????//?do?a?Depth-First?traversal?of?the?tree!

?????????????}

?????????}

?????????else//不在Open表中也不在Close表中

?????????{?

?????????????//生成新的節點

?????????????Successor?=?(?NODE*?)calloc(1,sizeof(?NODE?));

?????????????Successor->Parent?=?BestNode;

?????????????Successor->g?=?g;

?????????????Successor->h?=?(x-dx)*(x-dx)?+?(y-dy)*(y-dy);??//?should?do?sqrt(),?but?since?we?don't?really

?????????????Successor->f?=?g+Successor->h;?????//?care?about?the?distance?but?just?which?branch?looks

?????????????Successor->x?=?x;?????????????????//?better?this?should?suffice.?Anyayz?it's?faster.

?????????????Successor->y?=?y;

?????????????Successor->NodeNum?=?TileNumS;

?????????????//再插入Open表中，同時排序。

?????????????Insert(Successor);?????//?Insert?Successor?on?OPEN?list?wrt?f

?????????????for(?c?=0;?c?<8;?c++)?if?(?BestNode->Child[c]?==?NULL?)?//?Add?Old?to?the?list?of?BestNode's?Children?(or?Successors).

??????????????break;

?????????????BestNode->Child[c]?=?Successor;

?????????}

??????}?

posted on 2007-02-10 17:52 楊粼波 閱讀(270) 評論(0)  編輯 收藏 引用