A*是一種路徑搜索算法，比如為游戲中的角色規(guī)劃行動(dòng)路徑。

1. 輸入

A* 算法的輸入是，起點(diǎn)（初始狀態(tài)）和終點(diǎn)（目標(biāo)狀態(tài)），以及兩點(diǎn)間所有可能的路徑，以及涉及到的中間節(jié)點(diǎn)（中間狀態(tài)），每?jī)蓚€(gè)節(jié)點(diǎn)間的路徑的代價(jià)。

一般還需要某種啟發(fā)函數(shù)，即從任意節(jié)點(diǎn)到終點(diǎn)的近似代價(jià)，啟發(fā)函數(shù)能夠非?？焖俚墓浪愠鲈摯鷥r(jià)值。

2. 輸出

輸出是從起點(diǎn)到終點(diǎn)的最優(yōu)路徑，即代價(jià)最小。同時(shí)，好的啟發(fā)函數(shù)將使得這一搜索運(yùn)算盡可能高效，即搜索盡量少的節(jié)點(diǎn)/可能的路徑。

3. 公式

f(n)=g(n)+h(n)

f(n) 是從初始狀態(tài)經(jīng)由狀態(tài)n到目標(biāo)狀態(tài)的代價(jià)估計(jì)

g(n) 是在狀態(tài)空間中從初始狀態(tài)到狀態(tài)n的實(shí)際代價(jià)

h(n) 是從狀態(tài)n到目標(biāo)狀態(tài)的最佳路徑的估計(jì)代價(jià)

4. 搜索算法

A*算法是從起點(diǎn)開(kāi)始，檢查所有可能的擴(kuò)展點(diǎn)（它的相鄰點(diǎn)），對(duì)每個(gè)點(diǎn)計(jì)算g+h得到f，在所有可能的擴(kuò)展點(diǎn)中，選擇f最小的那個(gè)點(diǎn)進(jìn)行擴(kuò)展，即計(jì)算該點(diǎn)的所有可能擴(kuò)展點(diǎn)的f值，并將這些新的擴(kuò)展點(diǎn)添加到擴(kuò)展點(diǎn)列表（open list）。當(dāng)然，忽略已經(jīng)在列表中的點(diǎn)、已經(jīng)考察過(guò)的點(diǎn)。

不斷從open list中選擇f值最小的點(diǎn)進(jìn)行擴(kuò)展，直到到達(dá)目標(biāo)點(diǎn)（成功找到最優(yōu)路徑），或者節(jié)點(diǎn)用完，路徑搜索失敗。

算法步驟：

1）  把起點(diǎn)加入 open list 。
2）  重復(fù)如下過(guò)程：
    a.     遍歷 open list ，查找 F 值最小的節(jié)點(diǎn)，把它作為當(dāng)前要處理的節(jié)點(diǎn)。
    b.     把這個(gè)節(jié)點(diǎn)移到 close list（已經(jīng)考察過(guò)的節(jié)點(diǎn)列表） 。
    c.     對(duì)當(dāng)前節(jié)點(diǎn)的所有鄰近節(jié)點(diǎn)
        ◆     如果它是不可抵達(dá)的或者它在 close list 中，忽略它。否則，做如下操作。
        ◆     如果它不在 open list 中，把它加入 open list ，并且把當(dāng)前方格設(shè)置為它的父親，
              記錄該方格的 F ， G 和 H 值。
        ◆     如果它已經(jīng)在 open list 中，檢查這條路徑 ( 即經(jīng)由當(dāng)前節(jié)點(diǎn)到達(dá)它那里 ) 是否更好，
              用 G 值作參考。更小的 G 值表示這是更好的路徑。如果是這樣，把它的父親設(shè)置為
              當(dāng)前方格，并重新計(jì)算它的 G 和 F 值。如果你的 open list 是按 F 值排序的話，
              改變后你可能需要重新排序。
    d.     停止，當(dāng)你
        ◆     把終點(diǎn)加入到了 open list 中，此時(shí)路徑已經(jīng)找到了，或者
        ◆     查找終點(diǎn)失敗，并且 open list 是空的，此時(shí)沒(méi)有路徑。
3）  保存路徑。從終點(diǎn)開(kāi)始，每個(gè)方格沿著父節(jié)點(diǎn)移動(dòng)直至起點(diǎn)，這就是你的路徑。

參考

A* 算法步驟的詳細(xì)說(shuō)明請(qǐng)參考 A*尋路算法，它包含圖文案例清楚的解釋了A*算法計(jì)算步驟的一些細(xì)節(jié)，本文不再詳細(xì)展開(kāi)。

5. 為什么A能夠快速找到最優(yōu)路徑*

看一下上面參考文檔中的案例圖，最終搜索完成時(shí)，藍(lán)色邊框是close list中的節(jié)點(diǎn)，綠色邊框是open list中的節(jié)點(diǎn)，每個(gè)方格中三個(gè)數(shù)字，左上是f（=g+h），左下是g（已經(jīng)過(guò)路徑的代價(jià)），右下是h（估計(jì)未經(jīng)過(guò)路徑的代價(jià)）。藍(lán)色方格始終沿著f值最小的方向搜索前進(jìn)，避免了對(duì)一些不好的路徑（f值較大）的搜索。（圖片來(lái)自A*尋路算法）

6. 啟發(fā)式函數(shù)

現(xiàn)在我們可以理解，A*算法中啟發(fā)函數(shù)是最重要的，它有幾種情況：

1) h(n) = 0
一種極端情況，如果h(n)是0，則只有g(shù)(n)起作用，此時(shí)A*演變成Dijkstra算法，這保證能找到最短路徑。但效率不高，因?yàn)榈貌坏絾l(fā)。

2) h(n) < 真實(shí)代價(jià)
如果h(n)經(jīng)常都比從n移動(dòng)到目標(biāo)的實(shí)際代價(jià)?。ɑ蛘呦嗟龋瑒tA*保證能找到一條最短路徑。h(n)越小，A*擴(kuò)展的結(jié)點(diǎn)越多，運(yùn)行就得越慢。越接近Dijkstra算法。

3) h(n) = 真實(shí)代價(jià)
如果h(n)精確地等于從n移動(dòng)到目標(biāo)的代價(jià)，則A*將會(huì)僅僅尋找最佳路徑而不擴(kuò)展別的任何結(jié)點(diǎn)，這會(huì)運(yùn)行得非?？?。盡管這不可能在所有情況下發(fā)生，你仍可以在一些特殊情況下讓它們精確地相等（譯者：指讓h(n)精確地等于實(shí)際值）。只要提供完美的信息，A*會(huì)運(yùn)行得很完美，認(rèn)識(shí)這一點(diǎn)很好。

4) h(n) > 真實(shí)代價(jià)
如果h(n)有時(shí)比從n移動(dòng)到目標(biāo)的實(shí)際代價(jià)高，則A*不能保證找到一條最短路徑，但它運(yùn)行得更快。

5) h(n) >> 真實(shí)代價(jià)
另一種極端情況，如果h(n)比g(n)大很多，則只有h(n)起作用，A*演變成BFS算法。

7. 更多討論

關(guān)于啟發(fā)函數(shù)h、Dijkstra算法、BFS（最佳優(yōu)先搜索）算法、路徑規(guī)劃情況下啟發(fā)函數(shù)的選擇、算法實(shí)現(xiàn)時(shí)List的數(shù)據(jù)結(jié)構(gòu)、算法變種等等更多問(wèn)題，請(qǐng)參考：A*算法