寫(xiě)這篇文章的初衷是應(yīng)一個(gè)網(wǎng)友的要求，當(dāng)然我也發(fā)現(xiàn)現(xiàn)在有關(guān)人工智能的中文站點(diǎn)實(shí)在太少，我在這里拋磚引玉，希望大家都來(lái)熱心的參與。還是說(shuō)正題，我先拿A*算法開(kāi)刀，是因?yàn)锳*在游戲中有它很典型的用法，是人工智能在游戲中的代表。A*算法在人工智能中是一種典型的啟發(fā)式搜索算法，為了說(shuō)清楚A*算法，我看還是先說(shuō)說(shuō)何謂啟發(fā)式算法。
1、何謂啟發(fā)式搜索算法
在說(shuō)它之前先提提狀態(tài)空間搜索。狀態(tài)空間搜索，如果按專業(yè)點(diǎn)的說(shuō)法就是將問(wèn)題求解過(guò)程表現(xiàn)為從初始狀態(tài)到目標(biāo)狀態(tài)尋找這個(gè)路徑的過(guò)程。通俗點(diǎn)說(shuō)，就是在解一個(gè)問(wèn)題時(shí)，找到一條解題的過(guò)程可以從求解的開(kāi)始到問(wèn)題的結(jié)果（好象并不通俗哦）。由于求解問(wèn)題的過(guò)程中分枝有很多，主要是求解過(guò)程中求解條件的不確定性，不完備性造成的，使得求解的路徑很多這就構(gòu)成了一個(gè)圖，我們說(shuō)這個(gè)圖就是狀態(tài)空間。問(wèn)題的求解實(shí)際上就是在這個(gè)圖中找到一條路徑可以從開(kāi)始到結(jié)果。這個(gè)尋找的過(guò)程就是狀態(tài)空間搜索。
常用的狀態(tài)空間搜索有深度優(yōu)先和廣度優(yōu)先。廣度優(yōu)先是從初始狀態(tài)一層一層向下找，直到找到目標(biāo)為止。深度優(yōu)先是按照一定的順序前查找完一個(gè)分支，再查找另一個(gè)分支，以至找到目標(biāo)為止。這兩種算法在數(shù)據(jù)結(jié)構(gòu)書(shū)中都有描述，可以參看這些書(shū)得到更詳細(xì)的解釋。
前面說(shuō)的廣度和深度優(yōu)先搜索有一個(gè)很大的缺陷就是他們都是在一個(gè)給定的狀態(tài)空間中窮舉。這在狀態(tài)空間不大的情況下是很合適的算法，可是當(dāng)狀態(tài)空間十分大，且不預(yù)測(cè)的情況下就不可取了。他的效率實(shí)在太低，甚至不可完成。在這里就要用到啟發(fā)式搜索了。
啟發(fā)式搜索就是在狀態(tài)空間中的搜索對(duì)每一個(gè)搜索的位置進(jìn)行評(píng)估，得到最好的位置，再?gòu)倪@個(gè)位置進(jìn)行搜索直到目標(biāo)。這樣可以省略大量無(wú)畏的搜索路徑，提到了效率。在啟發(fā)式搜索中，對(duì)位置的估價(jià)是十分重要的。采用了不同的估價(jià)可以有不同的效果。我們先看看估價(jià)是如何表示的。
啟發(fā)中的估價(jià)是用估價(jià)函數(shù)表示的，如：
其中f(n) 是節(jié)點(diǎn)n的估價(jià)函數(shù)，g(n)實(shí)在狀態(tài)空間中從初始節(jié)點(diǎn)到n節(jié)點(diǎn)的實(shí)際代價(jià)，h(n)是從n到目標(biāo)節(jié)點(diǎn)最佳路徑的估計(jì)代價(jià)。在這里主要是h(n)體現(xiàn)了搜索的啟發(fā)信息，因?yàn)間(n)是已知的。如果說(shuō)詳細(xì)點(diǎn)，g(n)代表了搜索的廣度的優(yōu)先趨勢(shì)。但是當(dāng)h(n) >> g(n)時(shí)，可以省略g(n)，而提高效率。這些就深了，不懂也不影響啦！我們繼續(xù)看看何謂A*算法。
2、初識(shí)A*算法
啟發(fā)式搜索其實(shí)有很多的算法，比如：局部擇優(yōu)搜索法、最好優(yōu)先搜索法等等。當(dāng)然A*也是。這些算法都使用了啟發(fā)函數(shù)，但在具體的選取最佳搜索節(jié)點(diǎn)時(shí)的策略不同。象局部擇優(yōu)搜索法，就是在搜索的過(guò)程中選取“最佳節(jié)點(diǎn)”后舍棄其他的兄弟節(jié)點(diǎn)，父親節(jié)點(diǎn)，而一直得搜索下去。這種搜索的結(jié)果很明顯，由于舍棄了其他的節(jié)點(diǎn)，可能也把最好的節(jié)點(diǎn)都舍棄了，因?yàn)榍蠼獾淖罴压?jié)點(diǎn)只是在該階段的最佳并不一定是全局的最佳。最好優(yōu)先就聰明多了，他在搜索時(shí)，便沒(méi)有舍棄節(jié)點(diǎn)（除非該節(jié)點(diǎn)是死節(jié)點(diǎn)），在每一步的估價(jià)中都把當(dāng)前的節(jié)點(diǎn)和以前的節(jié)點(diǎn)的估價(jià)值比較得到一個(gè)“最佳的節(jié)點(diǎn)”。這樣可以有效的防止“最佳節(jié)點(diǎn)”的丟失。那么A*算法又是一種什么樣的算法呢？其實(shí)A*算法也是一種最好優(yōu)先的算法。只不過(guò)要加上一些約束條件罷了。由于在一些問(wèn)題求解時(shí)，我們希望能夠求解出狀態(tài)空間搜索的最短路徑，也就是用最快的方法求解問(wèn)題，A*就是干這種事情的！我們先下個(gè)定義，如果一個(gè)估價(jià)函數(shù)可以找出最短的路徑，我們稱之為可采納性。A*算法是一個(gè)可采納的最好優(yōu)先算法。A*算法的估價(jià)函數(shù)可表示為：
這里，f'(n)是估價(jià)函數(shù)，g'(n)是起點(diǎn)到終點(diǎn)的最短路徑值，h'(n)是n到目標(biāo)的最斷路經(jīng)的啟發(fā)值。由于這個(gè)f'(n)其實(shí)是無(wú)法預(yù)先知道的，所以我們用前面的估價(jià)函數(shù)f(n)做近似。g(n)代替g'(n)，但 g(n)>=g'(n)才可（大多數(shù)情況下都是滿足的，可以不用考慮），h(n)代替h'(n)，但h(n)<=h'(n)才可（這一點(diǎn)特別的重要）。可以證明應(yīng)用這樣的估價(jià)函數(shù)是可以找到最短路徑的，也就是可采納的。我們說(shuō)應(yīng)用這種估價(jià)函數(shù)的最好優(yōu)先算法就是A*算法。哈。你懂了嗎？肯定沒(méi)懂。接著看。
舉一個(gè)例子，其實(shí)廣度優(yōu)先算法就是A*算法的特例。其中g(shù)(n)是節(jié)點(diǎn)所在的層數(shù)，h(n)=0，這種h(n)肯定小于h'(n)，所以由前述可知廣度優(yōu)先算法是一種可采納的。實(shí)際也是。當(dāng)然它是一種最臭的A*算法。
再說(shuō)一個(gè)問(wèn)題，就是有關(guān)h(n)啟發(fā)函數(shù)的信息性。h(n)的信息性通俗點(diǎn)說(shuō)其實(shí)就是在估計(jì)一個(gè)節(jié)點(diǎn)的值時(shí)的約束條件，如果信息越多或約束條件越多則排除的節(jié)點(diǎn)就越多，估價(jià)函數(shù)越好或說(shuō)這個(gè)算法越好。這就是為什么廣度優(yōu)先算法的那么臭的原因了，誰(shuí)叫它的h(n)=0，一點(diǎn)啟發(fā)信息都沒(méi)有。但在游戲開(kāi)發(fā)中由于實(shí)時(shí)性的問(wèn)題，h(n)的信息越多，它的計(jì)算量就越大，耗費(fèi)的時(shí)間就越多。就應(yīng)該適當(dāng)?shù)臏p小h(n)的信息，即減小約束條件。但算法的準(zhǔn)確性就差了，這里就有一個(gè)平衡的問(wèn)題。可難了，這就看你的了！
好了我的話也說(shuō)得差不多了，我想你肯定是一頭的霧水了，其實(shí)這是寫(xiě)給懂A*算法的同志看的。哈哈。你還是找一本人工智能的書(shū)仔細(xì)看看吧！我這幾百字是不足以將A*算法講清楚的。只是起到拋磚引玉的作用希望大家熱情參與嗎。 在這里我將對(duì)A*算法的實(shí)際應(yīng)用進(jìn)行一定的探討，并且舉一個(gè)有關(guān)A*算法在最短路徑搜索的例子。值得注意的是這里并不對(duì)A*的基本的概念作介紹，如果你還對(duì)A*算法不清楚的話，請(qǐng)看姊妹篇《初識(shí)A*算法》。
這里所舉的例子是參考AMIT主頁(yè)中的一個(gè)源程序，你可以在AMIT的站點(diǎn)上下載也可以在我的站點(diǎn)上下載。你使用這個(gè)源程序時(shí)，應(yīng)該遵守一定的公約。
1、A*算法的程序編寫(xiě)原理
我在《初識(shí)A*算法》中說(shuō)過(guò)，A*算法是最好優(yōu)先算法的一種。只是有一些約束條件而已。我們先來(lái)看看最好優(yōu)先算法是如何編寫(xiě)的吧。如圖有如下的狀態(tài)空間：（起始位置是A，目標(biāo)位置是P，字母后的數(shù)字表示節(jié)點(diǎn)的估價(jià)值）。
如圖有如下的狀態(tài)空間：（起始位置是A，目標(biāo)位置是P，字母后的數(shù)字表示節(jié)點(diǎn)的估價(jià)值）
 |
| 圖1 狀態(tài)空間圖 |
搜索過(guò)程中設(shè)置兩個(gè)表：OPEN和CLOSED。OPEN表保存了所有已生成而未考察的節(jié)點(diǎn)，CLOSED表中記錄已訪問(wèn)過(guò)的節(jié)點(diǎn)。算法中有一步是根據(jù)估價(jià)函數(shù)重排OPEN表。這樣循環(huán)中的每一步只考慮OPEN表中狀態(tài)最好的節(jié)點(diǎn)。具體搜索過(guò)程如下：
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，已得到解；
看了具體的過(guò)程，再看看偽程序吧。算法的偽程序如下：
Best_First_Search()
{
Open = [起始節(jié)點(diǎn)];
Closed = [];
while ( Open表非空 )
{
從Open中取得一個(gè)節(jié)點(diǎn)X, 并從OPEN表中刪除.
if (X是目標(biāo)節(jié)點(diǎn))
{
求得路徑PATH;
返回路徑PATH;
}
for (每一個(gè)X的子節(jié)點(diǎn)Y)
{
if( Y不在OPEN表和CLOSE表中 )
{
求Y的估價(jià)值;
并將Y插入OPEN表中; //還沒(méi)有排序
}
else if( Y在OPEN表中 )
{
if( Y的估價(jià)值小于OPEN表的估價(jià)值 )
更新OPEN表中的估價(jià)值;
}
else //Y在CLOSE表中
{
if( Y的估價(jià)值小于CLOSE表的估價(jià)值 )
{
更新CLOSE表中的估價(jià)值;
從CLOSE表中移出節(jié)點(diǎn), 并放入OPEN表中;
}
}
將X節(jié)點(diǎn)插入CLOSE表中;
按照估價(jià)值將OPEN表中的節(jié)點(diǎn)排序;
} //end for
} //end while
} //end func
啊！偽程序出來(lái)了，寫(xiě)一個(gè)源程序應(yīng)該不是問(wèn)題了，依葫蘆畫(huà)瓢就可以。A*算法的程序與此是一樣的，只要注意估價(jià)函數(shù)中的g(n)的h(n)約束條件就可以了。不清楚的可以看看《初識(shí)A*算法》。好了，我們可以進(jìn)入另一個(gè)重要的話題，用A*算法實(shí)現(xiàn)最短路徑的搜索。在此之前你最好認(rèn)真的理解前面的算法。不清楚可以找我。
2、用A*算法實(shí)現(xiàn)最短路徑的搜索
在游戲設(shè)計(jì)中，經(jīng)常要涉及到最短路徑的搜索，現(xiàn)在一個(gè)比較好的方法就是用A*算法進(jìn)行設(shè)計(jì)。他的好處我們就不用管了，反正就是好！
注意下面所說(shuō)的都是以ClassAstar這個(gè)程序?yàn)樗{(lán)本，你可以在這里下載這個(gè)程序。這個(gè)程序是一個(gè)完整的工程。里面帶了一個(gè)EXE文件。可以先看看。
先復(fù)習(xí)一下，A*算法的核心是估價(jià)函數(shù)f(n)，它包括g(n)和h(n)兩部分。g(n)是已經(jīng)走過(guò)的代價(jià)，h(n)是n到目標(biāo)的估計(jì)代價(jià)。在這個(gè)例子中g(shù)(n)表示在狀態(tài)空間從起始節(jié)點(diǎn)到n節(jié)點(diǎn)的 深度，h(n)表示n節(jié)點(diǎn)所在地圖的位置到目標(biāo)位置的直線距離。啊！一個(gè)是狀態(tài)空間，一個(gè)是實(shí)際的地圖，不要搞錯(cuò)了。再詳細(xì)點(diǎn)說(shuō)，有一個(gè)物體A，在地圖上的坐標(biāo)是(xa,ya)，A所要到達(dá)的目標(biāo)b的坐標(biāo)是(xb,yb)。則開(kāi)始搜索時(shí)，設(shè)置一個(gè)起始節(jié)點(diǎn)1，生成八個(gè)子節(jié)點(diǎn)2 - 9 因?yàn)橛邪藗€(gè)方向。如圖：
 |
| 圖2 節(jié)點(diǎn)圖 |
先看搜索主函數(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值，即估價(jià)值
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表中取得一個(gè)估價(jià)值最好的節(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;
}
再看看生成子節(jié)點(diǎn)函數(shù) GenerateSuccessors：
void AstarPathfinder::GenerateSuccessors(NODE *BestNode, int dx, int dy)
{
int x, y;
//依次生成八個(gè)方向的子節(jié)點(diǎn)，簡(jiǎ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);
}
看看最重要的函數(shù)GenerateSucc：
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表中的估價(jià)值和當(dāng)前的估價(jià)值（只要比較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表中的估價(jià)值和當(dāng)前的估價(jià)值（只要比較g值就可以了）
if ( g g ) // if our new g value is Parent = BestNode;
Old->g = g;
Old->f = g + Old->h; //再依次更新Old的所有子節(jié)點(diǎn)的估價(jià)值
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表中，同時(shí)排序。
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;
}
}
哈哈。A*算法我懂了。當(dāng)然，我希望你有這樣的感覺(jué)。不過(guò)我還要再說(shuō)幾句。仔細(xì)看看這個(gè)程序，你會(huì)發(fā)現(xiàn)，這個(gè)程序和我前面說(shuō)的偽程序有一些不同，在GenerateSucc函數(shù)中，當(dāng)子節(jié)點(diǎn)在Closed表中時(shí)，沒(méi)有將子節(jié)點(diǎn)從Closed表中刪除并放入Open表中。而是直接的重新的計(jì)算該節(jié)點(diǎn)的所有子節(jié)點(diǎn)的估價(jià)值（用PropagateDown函數(shù)）。這樣可以快一些。另當(dāng)子節(jié)點(diǎn)在Open表和Closed表中時(shí)，重新的計(jì)算估價(jià)值后，沒(méi)有重新的對(duì)Open表中的節(jié)點(diǎn)排序，我有些想不通，為什么不排呢？會(huì)不會(huì)是一個(gè)小小的BUG。你知道告訴我好嗎？
好了。主要的內(nèi)容都講完了，還是完整仔細(xì)的看看源程序吧。希望我所的對(duì)你有一點(diǎn)幫助，一點(diǎn)點(diǎn)也可以。如果你對(duì)文章中的觀點(diǎn)有異議或有更好的解釋都告訴我。
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
——by Drew
對(duì)sunway程序中的BUG所進(jìn)行的修改
需要注意的是Sunway上面文章“深入A*算法”中引用了一個(gè)A*的游戲程序進(jìn)行講解，并有這個(gè)源碼的下載，不過(guò)它有一個(gè)不小的Bug, 就是新的子節(jié)點(diǎn)放入OPEN表中進(jìn)行了排序，而當(dāng)子節(jié)點(diǎn)在Open表和Closed表中時(shí)，重新計(jì)算估價(jià)值后，沒(méi)有重新的對(duì)Open表中的節(jié)點(diǎn)排序，這個(gè)問(wèn)題會(huì)導(dǎo)致計(jì)算有時(shí)得不到最優(yōu)解，另外在路網(wǎng)權(quán)重懸殊很大時(shí)，搜索范圍不但超過(guò)Dijkstra，甚至搜索全部路網(wǎng), 使效率大大降低。
Drew 對(duì)這個(gè)問(wèn)題進(jìn)行了如下修正，當(dāng)子節(jié)點(diǎn)在Open表和Closed表中時(shí)，重新計(jì)算估價(jià)值后，刪除OPEN表中的老的節(jié)點(diǎn)，將有新估價(jià)值的節(jié)點(diǎn)插入OPEN表中，重新排序，經(jīng)測(cè)試效果良好，修改的代碼如下，紅色部分為Drew添加的代碼.添加進(jìn)程序的相應(yīng)部分即可。
在函數(shù)GenerateSucc（）中
...................................
g=BestNode->g+1; /**//* g(Successor)=g(BestNode)+cost of getting from BestNode to Successor */
TileNumS=TileNum((int)x,(int)y); /**//* identification purposes */
if ((Old=CheckOPEN(TileNumS)) != NULL)
{
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;
if (g < Old->g)
{
Old->Parent=BestNode;
Old->g=g;
Old->f=g+Old->h;
//Drew 在該處添加如下紅色代碼
//Implement by Drew
NODE *q,*p=OPEN->NextNode, *temp=OPEN->NextNode;
while(p!=NULL && p->NodeNum != Old->NodeNum)
{
q=p;
p=p->NextNode;
}
if(p->NodeNum == Old->NodeNum)
{
if(p==OPEN->NextNode)
{
temp = temp->NextNode;
OPEN ->NextNode = temp;
}
else
q->NextNode = p->NextNode;
}
Insert(Old); // Insert Successor on OPEN list wrt f
}
......................................................