轉(zhuǎn)自http://www.programfan.com/blog/article.asp?id=18471

A*高效搜索算法 2006/09/11 rickone

了解了基本搜索算法，下面就來看A*，神奇的A*。

A*是一種啟發(fā)式搜索，一種有序搜索，它之所以特殊完全是在它的估價函數(shù)上，如果我要求的是從初始結(jié)點到目的結(jié)點的一個最短路徑（或加權(quán)代價）的可行解，那對于一個還不是目標結(jié)點的結(jié)點，我對它的評價就要從兩個方面評價：第一，離目標結(jié)點有多近，越近越好；第二，離起始結(jié)點有多遠，越近越好。記號[a,b]是表示結(jié)點a到結(jié)點b的實際最短路徑代價。設(shè)起始結(jié)點為S，當(dāng)前結(jié)點為n，目標結(jié)點為G，于是n的實際代價應(yīng)該是f*(n)=g*(n)+h*(n)，其中g(shù)*(n)=[S,n],h*(n)=[n,G]，對于是g*(n)是比較容易得到的，在搜索的過程中我們可以按搜索的順序?qū)λM行累積計算，當(dāng)然按BFS和DFS的不同，我們對它的估價g(n)可以滿足g(n)>=g*(n)，大多可以是相等的。但是對于h*(n)我們卻了解得非常少，目標結(jié)點正是要搜索的目的，我們是不知道在哪，就更不知道從n到目標結(jié)點的路徑代價，但是或多或少我們還是可以估計的，記估價函數(shù)f(n)=g(n)+h(n)。

我們說如果在一般的圖搜索算法中應(yīng)用了上面的估價函數(shù)對OPEN表進行排序的，就稱A算法。在A算法之上，如果加上一個條件，對于所有的結(jié)點x，都有h(x)<=h*(x)，那就稱為A*算法。如果取h(n)=0同樣是A*算法，這樣它就退化成了有序算法。

A*算法是否成功，也就是說是否在效率上勝過蠻力搜索算法，就在于h(n)的選取，它不能大于實際的h*(n)，要保守一點，但越接近h*(n)給我們的啟發(fā)性就越大，是一個難把握的東西。

A*算法流程：
首先將起始結(jié)點S放入OPEN表，CLOSE表置空，算法開始時：
1、如果OPEN表不為空，從表頭取一個結(jié)點n，如果為空算法失敗
2、n是目標解嗎？是，找到一個解（繼續(xù)尋找，或終止算法）；不是到3
3、將n的所有后繼結(jié)點展開，就是從n可以直接關(guān)聯(lián)的結(jié)點（子結(jié)點），如果不在CLOSE表中，就將它們放入OPEN表，并把S放入CLOSE表，同時計算每一個后繼結(jié)點的估價值f(n)，將OPEN表按f(x)排序，最小的放在表頭，重復(fù)算法到1

最短路徑問題，Dijkstra算法與A*
A*是求這樣一個和最短路徑有關(guān)的問題，那單純的最短路徑問題當(dāng)然可以用A*來算，對于g(n)就是[S,n]，在搜索過程中計算，而h(n)我想不出很好的辦法，對于一個抽象的圖搜索，很難找到很好的h(n)，因為h(n)和具體的問題有關(guān)。只好是h(n)=0，退為有序搜索，舉一個小小的例子：

與結(jié)點寫在一起的數(shù)值表示那個結(jié)點的價值f(n)，當(dāng)OPEN表為空時CLOSE表中將求得從V0到其它所有結(jié)點的最短路徑。考慮到算法性能，外循環(huán)中每次從OPEN表取一個元素，共取了n次（共n個結(jié)點），每次展開一個結(jié)點的后續(xù)結(jié)點時，需O(n)次，同時再對OPEN表做一次排序，OPEN表大小是O(n)量級的，若用快排就是O(nlogn)，乘以外循環(huán)總的復(fù)雜度是O(n^2logn)，如果每次不是對OPEN表進行排序，因為總是不斷地有新的結(jié)點添加進來，所以不用進行排序，而是每次從OPEN表中求一個最小的，那只需要O(n)的復(fù)雜度，所以總的復(fù)雜度為O(n*n)，這相當(dāng)于Dijkstra算法。在這個算法基礎(chǔ)之上稍加改進就是Dijkstra算法。OPEN表中常出現(xiàn)這樣的表項：(Vk,fk1)(Vk,fk2)(Vk,fk3)，而從算法上看，只有fk最小的一個才有用，于是可以將它們合并，整個OPEN表表示當(dāng)前的從V0到其它各點的最短路徑，定長為n，且初始時為V0可直接到達的權(quán)值（不能到達為INFINITY），于是就成了Dijkstra算法。

另外一個問題就是八數(shù)碼難題，一個A*的好例子。
問題描述為有這樣一個3*3方陣格子：

格子上有1-8八個數(shù)字外加一個空格，每次只能把與空格相臨的一個數(shù)字移到空格內(nèi)，移動一次算作一步，給出初始狀態(tài)和目標狀態(tài)，求如何以最少的步數(shù)完成移動？

設(shè)計A*算法時，g(n)就取當(dāng)前已移動的步數(shù)，h(n)取各個數(shù)字到目標狀態(tài)中對應(yīng)數(shù)字的位置的最短距離之和，這樣選取的原因是，對于每一次移動，只能使一個數(shù)字改變一個相臨位置，所以h(n)步是至少需要的，所以滿足h(n)<=h*(n)。

A*的成功之處就是在選擇好的h(n)，如果實在沒辦法令它為0也是可以求得問題的解的。