A*算法可以說是一種非常古老的算法，本身的思路可以說非常簡單，不過要設計一個好的A*算法卻並不容易。

問題定義

假設無人駕駛汽車要從 A 點(綠色方塊)移動到 B 點(紅色方塊)，但是這兩點之間被一堵牆(藍色方塊)隔開，如下圖所示。

你可能應該已經注意到了，我們把搜索的區域劃分成了正方形的格子，它的狀態就是walkable和unwalkable，通過計算出從A到B需要走過哪些方格，就找到了一條可通行的路徑。每個方格都可以成為一個節點，很多A*的文章都在討論節點，為什麼不直接描述為方格呢？因為我們有可能把搜索區域劃為為其他多變形而不是正方形，例如可以是六邊形，矩形，甚至可以是任意多變形。而節點可以放在任意多邊形裡面，可以放在多變形的中心，也可以放在多邊形的邊上。

開始搜索(Starting the Search)

問題定義好之後下一步要做的便是查找最短路徑。在 A* 中，我們從起點開始，檢查其相鄰的方格，然後向四周擴展，直至找到目標。具體過程如下:

1、把起點 A 加入到Open表中。Open表記錄了所有已經知道但是尚未探索的道路。

2、檢查與起點 A 相鄰的方格，把其中可走的 (walkable) 或可到達的 (reachable) 節點加入到 Open表中，把起點 A 設置為這些節點的父節點 (parent node 或 parent square) 。當我們在追蹤路徑時，這些父節點的內容是很重要的。

3、把 A 從 Open表中移除，加入到 Close表中，Close表中的每個節點都是已經走過的路。

如下圖所示，深綠色的方格為起點，它的外框是亮藍色，表示該方格被加入到了Close表 。與它相鄰的黑色方格是需要被檢查的，他們的外框是亮綠色。每個黑方格都有一個灰色的指針指向他們的父節點。

下一步，我們需要從Open表中選一個與起點 A 相鄰的方格，然後重複上述的搜索過程。但是到底選擇哪個方格好呢？答案是具有最小 F 值的那個。

路徑排序(Path Sorting)

路徑排序的關鍵是下面啟發函數，這也是A*算法的精髓所在：

F = G + H

這裡：

G=從起點 A 移動到指定節點的移動代價。

H = 從指定的節點到達終點 B 的估算成本。

在本例中，假設橫向和縱向的移動代價為 10 ，對角線的移動代價為 14 ，之所以使用這些數據，是因為實際的對角線移動距離是水平和垂直距離的平方根(近似的 1.414 倍的橫向或縱向移動代價)。

既然我們是沿著到達指定方格的路徑來計算 G 值，那麼計算出該方格的 G 值的方法就是找出其父親的 G 值，然後按父親是直線方向還是斜線方向加上 10 或 14 。

有很多方法可以估算 H 值。這裡我們使用 Manhattan 方法，計算從當前方格橫向或縱向移動到達目標所經過的方格數，忽略對角移動，然後把總數乘以 10 。之所以叫做 Manhattan 方法，是因為這很像統計從一個地點到另一個地點所穿過的街區數，而你不能斜向穿過街區。

把 G 和 H 相加便得到 F 。我們第一步的結果如下圖所示。每個方格都標上了 F ， G ， H 的值(左上角是 F ，左下角是 G ，右下角是 H)。

繼續搜索(Continuing the Search)

我們從Open表中選擇 F 值最小的節點，然後對所選擇的節點作如下操作：

4、把它從Open表中取出，放到 Close表中。

5、檢查所有與它相鄰的節點，忽略在 Close表中或是不可走 (unwalkable) 的節點，如果方格不在Open表中，則把它們加入到Open表中。同時把正在搜索的節點設置為新加入的節點的父親。

6、如果某個相鄰的節點已經在Open表中，則檢查這條路徑是否更優，也就是說經由當前節點到達那個方格是否具有更小的 G 值。如果沒有，不做任何操作；如果 G 值更小，則把那個節點的父親設為當前節點，然後重新計算那個方格的 F 值和 G 值。

Ok ，讓我們看看它是怎麼工作的。在我們最初的 9 個方格中，還有 8 個在 Open表中，起點被放入了Close表中。在這些方格中，起點右邊的格子的 F 值 40 最小，因此我們選擇這個方格作為下一個要處理的方格。它的外框用藍線打亮。

首先，我們把它從 Open表移到Close表中，然後我們檢查與它相鄰的方格。它右邊的方格是牆壁，忽略之。它左邊的方格是起點，在 Close表中，我們也忽略。其他 4 個相鄰的方格均在Open表中，我們需要檢查經由這個方格到達那裡的路徑是否更好。讓我們看看上面的方格。它現在的 G 值為 14 。如果我們經由當前方格到達那裡， G 值將會為 20(其中 10 為到達當前方格的 G 值，此外還要加上從當前方格縱向移動到上面方格的 G 值 10) 。顯然 20 比 14 大，因此這不是最優的路徑。

當把 4 個已經在Open表中的相鄰方格都檢查後，沒有發現經由當前方格的更好路徑，因此我們不做任何改變。現在我們已經檢查了當前方格的所有相鄰的方格，並也對他們作了處理，是時候選擇下一個待處理的方格了。

再次遍歷我們的Open表，現在它只有 7 個方格了，我們需要選擇 F 值最小的那個。有趣的是，這次有兩個方格的 F 值都 54，選哪個呢？沒什麼關係。從速度上考慮，選擇最後加入 Open表的方格更快。這導致了在尋路過程中，當靠近目標時，優先使用新找到的方格的偏好。

我們選擇起點右下方的方格，如下圖所示。

這次，當我們檢查相鄰的方格時，我們發現它右邊的方格是牆，忽略之。上面的也一樣。

我們把牆下面的一格也忽略掉。為什麼？因為如果不穿越牆角的話，你不能直接從當前方格移動到那個方格。你需要先往下走，然後再移動到那個方格，這樣來繞過牆角。

這樣還剩下 5 個相鄰的方格。當前方格下面的 2 個方格還沒有加入Open表，所以把它們加入，同時把當前方格設為他們的父親。在剩下的3 個方格中，有 2 個已經在 Close表中 ( 一個是起點，一個是當前方格上面的方格，外框被加亮的 ) ，忽略它們。最後一個方格，也就是當前方格左邊的方格，我們檢查經由當前方格到達那裡是否具有更小的 G 值。沒有。因此我們準備從Open表中選擇下一個待處理的方格。

不斷重複這個過程，直到把終點也加入到了Open表中，此時如下圖所示。

注意，在起點下面 2 格的方格的父親已經與前面不同了。之前它的 G 值是 28 並且指向它右上方的方格。現在它的 G 值為 20 ，並且指向它正上方的方格。這在尋路過程中的某處發生，使用新路徑時 G 值經過檢查並且變得更低，因此父節點被重新設置， G 和 F 值被重新計算。

那麼我們怎麼樣去確定實際路徑呢？很簡單，從終點開始，按著箭頭向父節點移動，這樣你就被帶回到了起點，這就是你的路徑。如下圖所示。從起點 A 移動到終點 B 就是簡單從路徑上的一個方格的中心移動到另一個方格的中心，直至目標。就是這麼簡單！

A*算法總結(Summary of the A* Method)

Ok ，現在你已經看完了整個的介紹，現在我們把所有步驟放在一起：

1、把起點加入Open表 。

2、 重複如下過程：

a) 遍歷Open表，查找 F 值最小的節點，把它作為當前要處理的節點。

b) 把當前節點移到Close表 。

c) 對當前方格的 8 個相鄰方格的每一個方格？

◆ 如果它是不可抵達的或者它在Close表中，忽略它。否則，做如下操作。

◆ 如果它不在Open表中，把它加入Open表，並且把當前方格設置為它的父親，記錄該方格的 F ， G 和 H 值。

◆ 如果它已經在Open表中，檢查這條路徑 ( 即經由當前方格到達它那裡 ) 是否更好，用 G 值作參考。更小的 G 值表示這是更好的路徑。如果是這樣，把它的父親設置為當前方格，並重新計算它的 G 和 F 值。如果你的Open表是按 F 值排序的話，改變後你可能需要重新排序。

d) 停止條件

◆ 把終點加入到了Open表中，此時路徑已經找到了。

◆ 查找終點失敗，並且Open表是空的，此時沒有找到可行的路徑。

3、保存路徑。從終點開始，每個方格沿著父節點移動直至起點，這就是待查找的路徑。

閱讀更多 半杯茶的小酒杯 的文章

關鍵字: 人工智能 初學者 算法