The Fourth Dimension Space

枯葉北風寒，忽然年以殘，念往昔，語默心酸。二十光陰無一物，韶光賤，寐難安；不畏形影單，道途阻且慢，哪曲折，如渡飛湍。斬浪劈波酬壯志，同把酒，共言歡！ -如夢令

統計

隨筆 - 414
文章 - 13
評論 - 521
引用 - 0

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

CMU CV Group

友情鏈接

n皇后問題精彩分析
RMQ問題的精彩文章
開關燈問題

搜索

閱讀排行榜

評論排行榜

A*算法詳解——by Sunway

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

1、何謂啟發式搜索算法
　　在說它之前先提提狀態空間搜索。狀態空間搜索，如果按專業點的說法就是將問題求解過程表現為從初始狀態到目標狀態尋找這個路徑的過程。通俗點說，就是在解一個問題時，找到一條解題的過程可以從求解的開始到問題的結果（好象并不通俗哦）。由于求解問題的過程中分枝有很多，主要是求解過程中求解條件的不確定性，不完備性造成的，使得求解的路徑很多這就構成了一個圖，我們說這個圖就是狀態空間。問題的求解實際上就是在這個圖中找到一條路徑可以從開始到結果。這個尋找的過程就是狀態空間搜索。
　　常用的狀態空間搜索有深度優先和廣度優先。廣度優先是從初始狀態一層一層向下找，直到找到目標為止。深度優先是按照一定的順序前查找完一個分支，再查找另一個分支，以至找到目標為止。這兩種算法在數據結構書中都有描述，可以參看這些書得到更詳細的解釋。
　　前面說的廣度和深度優先搜索有一個很大的缺陷就是他們都是在一個給定的狀態空間中窮舉。這在狀態空間不大的情況下是很合適的算法，可是當狀態空間十分大，且不預測的情況下就不可取了。他的效率實在太低，甚至不可完成。在這里就要用到啟發式搜索了。
　　啟發式搜索就是在狀態空間中的搜索對每一個搜索的位置進行評估，得到最好的位置，再從這個位置進行搜索直到目標。這樣可以省略大量無畏的搜索路徑，提到了效率。在啟發式搜索中，對位置的估價是十分重要的。采用了不同的估價可以有不同的效果。我們先看看估價是如何表示的。
　　啟發中的估價是用估價函數表示的，如：

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*算法。

2、初識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)的信息，即減小約束條件。但算法的準確性就差了，這里就有一個平衡的問題?？呻y了，這就看你的了！
　　好了我的話也說得差不多了，我想你肯定是一頭的霧水了，其實這是寫給懂A*算法的同志看的。哈哈。你還是找一本人工智能的書仔細看看吧！我這幾百字是不足以將A*算法講清楚的。只是起到拋磚引玉的作用希望大家熱情參與嗎。

在這里我將對A*算法的實際應用進行一定的探討，并且舉一個有關A*算法在最短路徑搜索的例子。值得注意的是這里并不對A*的基本的概念作介紹，如果你還對A*算法不清楚的話，請看姊妹篇《初識A*算法》。
　　這里所舉的例子是參考AMIT主頁中的一個源程序，你可以在AMIT的站點上下載也可以在我的站點上下載。你使用這個源程序時，應該遵守一定的公約。

1、A*算法的程序編寫原理
　　我在《初識A*算法》中說過，A*算法是最好優先算法的一種。只是有一些約束條件而已。我們先來看看最好優先算法是如何編寫的吧。如圖有如下的狀態空間：（起始位置是A，目標位置是P，字母后的數字表示節點的估價值）。
　　如圖有如下的狀態空間：（起始位置是A，目標位置是P，字母后的數字表示節點的估價值）


圖1 狀態空間圖

　　搜索過程中設置兩個表：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*算法實現最短路徑的搜索。在此之前你最好認真的理解前面的算法。不清楚可以找我。

2、用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 因為有八個方向。如圖：


圖2 節點圖

　　先看搜索主函數：

　　

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;

　　}

　　再看看生成子節點函數 GenerateSuccessors：

　　

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

　　{

　　　　int x, y;

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

　　　　// Upper-Left

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