A*算法

A_算法與Dijkstra算法的框架是完全一樣的，**A_算法就是有啟發(fā)性的Dijkstra算法**

代價函數(shù)：g(n) 表示的是從開始節(jié)點到當(dāng)前n節(jié)點的代價累加

啟發(fā)函數(shù)：h(n) 表示當(dāng)前節(jié)點到目標(biāo)節(jié)點估計所花的代價

優(yōu)先級隊列：維護(hù)的是 代價函數(shù)+啟發(fā)函數(shù)的 節(jié)點從小到大排序 f(n)=g(n)+h(n)

每次彈出的節(jié)點就是最小的f(n)值的節(jié)點。

A*算法偽代碼

維護(hù)一個優(yōu)先級隊列，存儲所有被擴(kuò)展的節(jié)點，且節(jié)點按f()值的大小自動按從小到大排列。

-所以節(jié)點的啟發(fā)值h(n)是為被定義的，是不知道的，到具體的節(jié)點再計算

-優(yōu)先級隊列首先為空，以起始節(jié)點Xs進(jìn)行初始化

-起始節(jié)點g(Xs)=0，并且初始化其它節(jié)點的代價為無窮大

-循環(huán)：

    1、如果隊列是空的，返回false，跳出循環(huán)

    2、**彈出優(yōu)先級隊列中f(n)最小的節(jié)點n** [唯一與djikstra不同的地方]

    3、標(biāo)記節(jié)點n為被擴(kuò)展節(jié)點

    4、如果節(jié)點n為目標(biāo)節(jié)點，返回true,跳出循環(huán)

    5、找到n節(jié)點周圍可以擴(kuò)展的所以節(jié)點（沒被擴(kuò)展過）m

        6、進(jìn)行判斷 如果g(m)為無窮大（說明其它節(jié)點也沒發(fā)現(xiàn)過m）,

            7、則計算 真正的g(m)=g(n)+Cnm，然后將m節(jié)點加入到優(yōu)先級隊列中

        8、進(jìn)行判斷 如果g(m)不為無窮大，有值了(說明其它節(jié)點發(fā)現(xiàn)過m，m已經(jīng)在優(yōu)先級隊列中)

            9、再次進(jìn)行判斷 如果之前發(fā)現(xiàn)m時計算的g(m)比g(n)+Cnm大的話

                10、更新g(m)=g(n)+Cnm。

    11、重復(fù)循環(huán)至步驟1

-結(jié)束循環(huán)

A* 算法步驟示例

下面是一個A_算法的演示圖，每個邊有個預(yù)先設(shè)置的代價g，每個節(jié)點有提前估計好的啟發(fā)f

以這個圖將A_ 算法運行的步驟進(jìn)行一個示例：

1、首先初始化隊列，將起始節(jié)點放入優(yōu)先級隊列中

2、彈出起始節(jié)點

可擴(kuò)展的節(jié)點僅有a節(jié)點，計算f(a)=g(a)+h(a)=1+5=6

3、將擴(kuò)展的節(jié)點放入優(yōu)先級隊列

4、彈出f最小節(jié)點，擴(kuò)展周圍節(jié)點

彈出a節(jié)點，a節(jié)點周圍可以擴(kuò)展的節(jié)點為 b\d\e 。并且根據(jù)g與h值計算f值

5、根據(jù)f值大小，壓入隊列中

d節(jié)點的f(d)=6最小，它在最下方。

6、彈出f值最小節(jié)點 ，擴(kuò)展周圍節(jié)點

彈出d節(jié)點，可擴(kuò)展節(jié)點為G節(jié)點，計算f(G)=6

7、將最新擴(kuò)展的節(jié)點加入優(yōu)先級隊列中，并進(jìn)行排序

G最小，排到最底下

8、彈出f值最小節(jié)點

彈出的節(jié)點是目標(biāo)節(jié)點G，算法結(jié)束

A*算法分析

A_算法的結(jié)果是不是最優(yōu)的？

例如這個圖，安裝A_算法的邏輯找到的路徑是 S直接到G ，這樣的代價是5。但是經(jīng)過A節(jié)點的代價是4，所以經(jīng)過A節(jié)點的路徑是最優(yōu)的。

問題就是某個節(jié)點估計的啟發(fā)值是不合理的。

如果A_算法想保有最優(yōu)性，_*需要估計的啟發(fā)值要小于等于實際的啟發(fā)值。__

啟發(fā)函數(shù)設(shè)計

設(shè)計的啟發(fā)函數(shù)為可接受的要滿足：需要估計的啟發(fā)值要小于等于實際的啟發(fā)值

如果滿足上述條件，A_算法的最終結(jié)果就是最優(yōu)的

A_算法使用的時候重點就是如何設(shè)計可接受的啟發(fā)函數(shù)

例如用歐式距離作為啟發(fā)函數(shù)，則就是可接受的

用manhattan距離，則就不一定是可接受的

A*應(yīng)用的更好方式

如果我們想用更高的啟發(fā)估計，相當(dāng)于A*算法在向貪心算法演變。

相當(dāng)于雖然不是最優(yōu)的結(jié)果，但是可以帶來速度上的提升。

這樣的操作就是 權(quán)重A_（Weighted A_）

f = g + ah ;a>1 , 越大找到目標(biāo)的速度越快。

犧牲最優(yōu)性獲取搜索速度

Weighted A* 也有一些升級

例如：

•AntTime A*

•ARA*

•D*