A*（念做：A Star）演算法是一種很常用的路徑查詢和圖形遍歷演算法。它有較好的效能和準確度。

本文在講解演算法的同時也會提供Python語言的程式碼實現，並會藉助matplotlib庫動態的展示演算法的運算過程。

演算法介紹

A*演算法最初發表於1968年，由Stanford研究院的Peter Hart， Nils Nilsson以及Bertram Raphael發表。它可以被認為是Dijkstra演算法的擴充套件。

由於藉助啟發函式的引導，A*演算法通常擁有更好的效能。

廣度優先搜尋

為了更好的理解A*演算法，我們首先從廣度優先（Breadth First）演算法講起。

正如其名稱所示，廣度優先搜尋以廣度做為優先順序進行搜尋。

從起點開始，首先遍歷起點周圍鄰近的點，然後再遍歷已經遍歷過的點鄰近的點，逐步的向外擴散，直到找到終點。

這種演算法就像洪水（Flood fill）一樣向外擴張，演算法的過程如下圖所示：

在上面這幅動態圖中，演算法遍歷了圖中所有的點，這通常沒有必要。對於有明確終點的問題來說，一旦到達終點便可以提前終止演算法，下面這幅圖對比了這種情況：

在執行演算法的過程中，每個點需要記錄達到該點的前一個點的位置 – 可以稱之為父節點。這樣做之後，一旦到達終點，便可以從終點開始，反過來順著父節點的順序找到起點，由此就構成了一條路徑。

Dijkstra演算法

Dijkstra演算法是由計算機科學家Edsger W。 Dijkstra［1］在1956年提出的。

Dijkstra演算法用來尋找圖形中節點之間的最短路徑。

考慮這樣一種場景，在一些情況下，圖形中相鄰節點之間的移動代價並不相等。例如，遊戲中的一幅圖，既有平地也有山脈，那麼遊戲中的角色在平地和山脈中移動的速度通常是不相等的。

在Dijkstra演算法中，需要計算每一個節點距離起點的總移動代價。同時，還需要一個優先佇列結構。對於所有待遍歷的節點，放入優先佇列中會按照代價進行排序。

在演算法執行的過程中，每次都從優先佇列中選出代價最小的作為下一個遍歷的節點。直到到達終點為止。

下面對比了不考慮節點移動代價差異的廣度優先搜尋與考慮移動代價的Dijkstra演算法的運算結果：

當圖形為網格圖，並且每個節點之間的移動代價是相等的，那麼Dijkstra演算法將和廣度優先演算法變得一樣。

最佳優先搜尋

在一些情況下，如果我們可以預先計算出每個節點到終點的距離，則我們可以利用這個資訊更快的到達終點。

其原理也很簡單。與Dijkstra演算法類似，我們也使用一個優先佇列，但此時以每個節點到達終點的距離作為優先順序，每次始終選取到終點移動代價最小（離終點最近）的節點作為下一個遍歷的節點。這種演算法稱之為最佳優先（Best First）演算法。

這樣做可以大大加快路徑的搜尋速度，如下圖所示：

但這種演算法會不會有什麼缺點呢？答案是肯定的。

因為，如果起點和終點之間存在障礙物，則最佳優先演算法找到的很可能不是最短路徑，下圖描述了這種情況。

A*演算法

對比了上面幾種演算法，最後終於可以講解本文的重點：A*演算法了。

下面的描述我們將看到，A*演算法實際上是綜合上面這些演算法的特點於一身的。

A*演算法透過下面這個函式來計算每個節點的優先順序。

f（n）=g（n）+h（n）

其中：

f（n）f（n） 是節點n的綜合優先順序。當我們選擇下一個要遍歷的節點時，我們總會選取綜合優先順序最高（值最小）的節點。

g（n）g（n） 是節點n距離起點的代價。

h（n）h（n） 是節點n距離終點的預計代價，這也就是A*演算法的啟發函式。關於啟發函式我們在下面詳細講解。

A*演算法在運算過程中，每次從優先佇列中選取f（n）f（n）值最小（優先順序最高）的節點作為下一個待遍歷的節點。

另外，A*演算法使用兩個集合來表示待遍歷的節點，與已經遍歷過的節點，這通常稱之為和。

完整的A*演算法描述如下：

啟發函式

上面已經提到，啟發函式會影響A*演算法的行為。

在極端情況下，當啟發函式h（n）始終為0，則將由g（n）決定節點的優先順序，此時演算法就退化成了Dijkstra演算法。

如果h（n）始終小於等於節點n到終點的代價，則A*演算法保證一定能夠找到最短路徑。但是當h（n）h（n）的值越小，演算法將遍歷越多的節點，也就導致演算法越慢。

如果h（n）完全等於節點n到終點的代價，則A*演算法將找到最佳路徑，並且速度很快。可惜的是，並非所有場景下都能做到這一點。因為在沒有達到終點之前，我們很難確切算出距離終點還有多遠。

如果h（n）的值比節點n到終點的代價要大，則A*演算法不能保證找到最短路徑，不過此時會很快。

在另外一個極端情況下，如果h（n）相較於g（n）大很多，則此時只有h（n）產生效果，這也就變成了最佳優先搜尋。

由上面這些資訊我們可以知道，透過調節啟發函式我們可以控制演算法的速度和精確度。因為在一些情況，我們可能未必需要最短路徑，而是希望能夠儘快找到一個路徑即可。這也是A*演算法比較靈活的地方。

對於網格形式的圖，有以下這些啟發函式可以使用：

如果圖形中只允許朝上下左右四個方向移動，則可以使用曼哈頓距離（Manhattan distance）。

如果圖形中允許朝八個方向移動，則可以使用對角距離。

如果圖形中允許朝任何方向移動，則可以使用歐幾里得距離（Euclidean distance）。

關於距離

曼哈頓距離

如果圖形中只允許朝上下左右四個方向移動，則啟發函式可以使用曼哈頓距離，它的計算方法如下圖所示：

計算曼哈頓距離的函式如下，這裡的D是指兩個相鄰節點之間的移動代價，通常是一個固定的常數。

對角距離

如果圖形中允許斜著朝鄰近的節點移動，則啟發函式可以使用對角距離。它的計算方法如下：

計算對角距離的函式如下，這裡的D2指的是兩個斜著相鄰節點之間的移動代價。如果所有節點都正方形，則其值就是√2*D。

歐幾里得距離

如果圖形中允許朝任意方向移動，則可以使用歐幾里得距離。

歐幾里得距離是指兩個節點之間的直線距離，因此其計算方法也是我們比較熟悉的：

其函式表示如下：

演算法實現

雖然前面介紹了很多內容，但實際上A*演算法並不複雜，實現起來也比較簡單。

下面我們給出一個Python語言的程式碼示例。

之所以使用Python語言是因為我們可以藉助matplotlib庫很方便的將結果展示出來。在理解了演算法之後，透過其他語言實現也並非難事。

演算法的原始碼可以到我的github上下載：paulQuei/a-star-algorithm［2］。

我們的演算法演示的是在一個二維的網格圖形上從起點找尋終點的求解過程。

座標點與地圖

首先，我們建立一個非常簡單的類來描述圖中的點，相關程式碼如下：

接著，我們實現一個描述地圖結構的類。為了簡化演算法的描述：