二、初識 A* 算法： ?

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

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

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

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

再說一個問題，就是有關(guān) h(n) 啟發(fā)函數(shù)的信息性。 h(n) 的信息性通俗點(diǎn)說其實(shí)就是在估計(jì)一個節(jié)點(diǎn)的值 時的約束條件，如果信息越多或約束條件越多則排除的節(jié)點(diǎn)就越多，估價函數(shù)越好或說這個算法越好。這就 是為什么廣度優(yōu)先算法的那么臭的原因了，誰叫它的 h(n)=0 ，一點(diǎn)啟發(fā)信息都沒有。但在游戲開發(fā)中由于實(shí) 時性的問題， h(n) 的信息越多，它的計(jì)算量就越大，耗費(fèi)的時間就越多。就應(yīng)該適當(dāng)?shù)臏p小 h(n) 的信息，即 減小約束條件。但算法的準(zhǔn)確性就差了，這里就有一個平衡的問題?？呻y了，這就看你的了！ ?

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

預(yù)知 A* 算法的應(yīng)用，請看《深入 A* 算法》。

?

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

一、前言 ?

在這里我將對 A* 算法的實(shí)際應(yīng)用進(jìn)行一定的探討，并且舉一個有關(guān) A* 算法在最短路徑搜索 的例子。值得注意的是這里并不對 A* 的基本的?

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

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

守一定的公約。 ?

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

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

如圖有如下的狀態(tài)空間：（起始位置是 A ，目標(biāo)位置是 P ，字母后的數(shù)字表示節(jié)點(diǎn)的估價值） ?

?

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

根據(jù)估價函數(shù)重排 OPEN 表。這樣循環(huán)中的每一 步只考慮 OPEN 表中狀態(tài)最好的節(jié)點(diǎn)。具體搜索過程如下： ?
?

??????1）初始狀態(tài)：???

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

??????2）估算A5，取得搜有子節(jié)點(diǎn)，并放入OPEN表中；

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

??????3）估算B4，取得搜有子節(jié)點(diǎn)，并放入OPEN表中；

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

??????4）估算C4；取得搜有子節(jié)點(diǎn)，并放入OPEN表中；

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

??????5）估算H3，取得搜有子節(jié)點(diǎn)，并放入OPEN表中；

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

??????6）估算O2，取得搜有子節(jié)點(diǎn)，并放入OPEN表中；

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

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

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

??????Best_First_Search()

?????? {

??????Open? = ?[起始節(jié)點(diǎn)];?Closed? = ?[];

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

?????? {

??????????從Open中取得一個節(jié)點(diǎn)X，并從OPEN表中刪除。

?????????? if ?(X是目標(biāo)節(jié)點(diǎn))

?????????? {

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

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

?????????? for ?(每一個X的子節(jié)點(diǎn)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é)點(diǎn)，并放入OPEN表中；

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

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

??????????????將X節(jié)點(diǎn)插入CLOSE表中；

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

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

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

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

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

三、用 A* 算法實(shí)現(xiàn)最短路徑的搜索 ?

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

注意下面所說的都是以 ClassAstar 這個程序?yàn)樗{(lán)本，你可以在這里下載這個程序。這個程 序是一個完整的工程。里面帶了一個 EXE 文件?？梢韵瓤纯?。 ?

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

?

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

先看搜索主函數(shù)： ??

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

?????? {

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

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

??????????? // 得到目標(biāo)位置，作判斷用

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

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

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

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

????????? // 生成起始節(jié)點(diǎn)，并放入Open表中

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

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

????????? // 這是計(jì)算h值?

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

????????? // 這是計(jì)算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表中取得一個估價值最好的節(jié)點(diǎn)

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

????????????? // 如果該節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)就退出

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

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

????????????? // 否則生成子節(jié)點(diǎn)

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

?????????}

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

??????} ?

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

??????{

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

?????????//哦！依次生成八個方向的子節(jié)點(diǎn)，簡單！

????????????????????????//?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;

?????????//計(jì)算子節(jié)點(diǎn)的?g?值??

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

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

?????????//子節(jié)點(diǎn)再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表中的估價值和當(dāng)前的估價值（只要比較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表中的估價值和當(dāng)前的估價值（只要比較g值就可以了）

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

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

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

?????????????????//再依次更新Old的所有子節(jié)點(diǎn)的估價值

??????????????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表中

?????????{?

?????????????//生成新的節(jié)點(diǎn)

?????????????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)  編輯 收藏 引用