轉自http://www.programfan.com/blog/article.asp?id=18471

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

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

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

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

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

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

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

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

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

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

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

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