A*算法是啟發(fā)式搜索算法，是根據(jù)Dijkstra算法改進而來。

一、定義：是一種在圖形平面上，對于有多個節(jié)點的路徑求出最低通過成本的算法。它屬于圖遍歷和最佳優(yōu)先搜索算法，亦是BFS 的改進。

二、如何更好的理解A*算法？

如下圖所示，S為起始（start）節(jié)點，G為目標（goal）節(jié)點。

（1）節(jié)點之間連線是兩點的路徑長度，如A到E的路徑長度c(A,E) = 9。

（2）節(jié)點旁的h值時當(dāng)前節(jié)點到達目標節(jié)點（G）的預(yù)估值，如h(A)=15, 表示從當(dāng)前點A到達目標點G的估計路徑長度為15，此處h(x)即為啟發(fā)函數(shù)。

（3）從起點S到達當(dāng)前節(jié)點x的路徑長度表示為g(x) 。

（4）從起點S到達目標G并經(jīng)過點x的估計距離長度表示為f(x) = g(x) + h(x)，該公式是A*算法的核心公式。

（5）A*算法通過不斷的選擇估計距離f最小的節(jié)點，逐漸構(gòu)建最短路徑。

邏輯流程

創(chuàng)建兩個集合OPEN集，CLOSED集，算法核心是從OPEN集中選擇最優(yōu)（f值小最優(yōu)，或f相同時，h小的更優(yōu)）的節(jié)點到CLOSED集中，然后將其后繼節(jié)點放入OPEN集中，然后重復(fù)操作選取最優(yōu)節(jié)點，直到到達目標，或者OPEN為空為止。最后再CLOSED集中根據(jù)目標G所包含的前序節(jié)點逆序查找最后到達起點S，這個鏈路的逆序即最優(yōu)路徑，具體流程如下圖。

搜索過程

以下是前面網(wǎng)絡(luò)的搜索過程展開圖。

組合塊中：

（a）灰色為前序節(jié)點

（b）藍色當(dāng)前節(jié)點x

（c）g：起點S到當(dāng)前節(jié)點x的路徑距離。

（d）h：當(dāng)前節(jié)點x到終點G的估計距離

（e）f：起點S途徑x到達終點G的估計距離，即 f = g + h

（f）綠色框為當(dāng)前OPEN集合中的最優(yōu)節(jié)點

（g）紅色框表示當(dāng)前OPEN集合中需要被刪除的節(jié)點

在OPEN、CLOSED中每一行表示一次完整迭代完成時兩集合中的節(jié)點集合。

最后的最優(yōu)路徑是：S->B->F->k->G

注：當(dāng)兩個節(jié)點f相同時，h小的更優(yōu)