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

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

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

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

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

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

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

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

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

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

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

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

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