在前面的文章中，原力君跟大家一起分享了無人車根據地圖信息設定導航路線的基本思路，並且最後發現這個問題可以轉化為一個經典的問題：帶權有向圖的最短路徑搜索問題。實際工程中，通常選擇一種在遊戲領域廣泛應用的路徑搜索算法---A*算法（也叫A星算法）。本文將會用一個簡單的路徑搜索的例子來解釋A*算法的求解過程。
最短路徑搜索的前提：
1）有一個地圖（有向或者無向的），地圖用一個一個的小格子（可以抽象為點）構成，地圖中包含障礙物信息（即哪些點是可以通過的，哪些點是不可以通過的）
2）設定起始點、目標點。
3）建立地圖上點與點之間的關係，即需要提前設定地圖中每個點移動到它周邊8個方向的鄰居點位置時需要經過的距離、需要消耗的資源、或者是某一個代價值。這個在路徑搜索的時候要用到。
4）計算每個地圖點到目標點的理想距離，即不考慮障礙物、不可經過的點等，假設地圖上所有點都是可以通過的。僅僅利用橫向移動或者縱向移動，一直到目標點所經過的距離
我們有個地圖格子，格子中有個綠色的起始點（記為A），紅色的終止點（記為B），藍色的障礙物。有人想從A點移動到B點，而且要避開中間的藍色區域，如下圖：
圖片來自文獻[1]
我們可能一眼就能看出來有很多條路徑可以連通A點和B點。但是，如果要找到最短路徑，可能需要仔細去數每條路徑經過的格子數，最後找到通過格子數最少的那條路徑。這種方法實際上非常暴力。這個例子中格子數比較少，這種粗暴的方法是可用的；但是，當格子數變得非常大，比如變成10000*10000個，人眼也無能為力了。
雖然這樣做可以找到最短路徑，但是消耗的計算資源非常大，而且非常慢。如果什麼問題都去遍歷一遍，那優化算法就沒有存在的意義了。優化算法的意義就在於，用最短的時間、最少的計算資源，結算出最優的結果。
因此，我們需要藉助計算機算法來找到最短路徑。那麼，問題來了：
1）算法不會遍歷所有的點
2）算法需要找到最短路徑
3）算法需要避開障礙物
A*算法的基本思路就是每次只關注一個點（記為當前點，用C表示），然後根據下面幾條做決策：
1）計算或者讀取周邊的鄰居點到目標的理想距離，記為H。H的作用，相當於是告訴算法要一直想著目標在哪裡，不要迷失了方向。
2）計算或者讀取當前點移動到周邊的鄰居點經過的距離，記為G。G點的作用是告訴算法，不要覺得當前點距離目標點很近就完事兒了，你也得考慮你從起始點到現在，一共走了多遠的距離了。G可以避免算法走彎路。
圖片來自文獻[2]
3）計算可行路徑（當前點-鄰居點-目標點）的理想距離，記為F。當前點到鄰居點的距離，是確定的，而鄰居點到目標點，只能用理想距離來評估。所以，F可以為G和H的加和。
4）找到可以讓F最小的那個鄰居點，並把這個鄰居點作為關注點，記錄上一個關注點，將其與當前關注點連接起來（編程時，用指針指向它即可）。選擇最小的F，可以在一定程度上保證我們可以找到相對較短的那條路徑。但是由於算法的侷限性，A*沒法保證找到的路徑是最短的，只能說在一定程度上是最短的。
5）重複步驟1)到步驟4）的計算過程，直到找到目標點為之。根據所有關注點的連接關係，得到整條最短路徑。
再回到例子，假設每個格子的邊長是10，則對角線長為14（也可以邊長1，則對角線為1.414，小數計算會降低程序運行的速度，所以我們用整數，不影響搜索結果）。
準備工作：
1）準備一個Open表格，用來存放算法已經提取的點（當前點的鄰居點，鄰居點的鄰居點，以此類推）
2）準備一個Close表格，用來存放算法已經關注過的點（如果當前關注點是A，則將A放到Close表中；下一次根據F值移動到A的右邊，則將A的右邊點放入Close表；以此類推，只要是關注點 C曾經佔用過的點，都要放到Close表中；同時，如果放入Close表的點也在Open表中，則將其從Open表中刪除）
3）關注過得點用藍色的框框高亮顯示
首先關注起始點A（綠色格子），將A放入Close表。它的周邊鄰居點一共有8個：左上，上，右上，右，右下，下，左下，左。將這8個點放入到Open表中。
當前點（用C表示）從A移動到上下左右四個方向時，移動距離為10；移動到左上、右上、左下、右下四個方向時，移動距離為14. 因此，可以計算C點在A處時，其8個鄰居點的G,H,F值了。將F, G, H分別寫在格子的左上角、左下角、右下角，如下圖所示。
圖片來自[1]
從圖中可以看到，綠色格子的右邊格子F值最小，因此關注點C移動到A點右邊的格子處，並且將A右邊的格子點放入Close表中，同時將其從Open表中刪除。
查看當前關注點C的鄰居點：左上，上，下，左下，共4個點。左邊點是起始點，已經在Close表中，右邊三個點是牆，所以都忽略掉，不參與計算。C在A的位置時，這4個點在已經在Open表中了，所以沒有新點加入Open表中。
根據C的位置，重新計算C的4個可用鄰居點的G,H,F值。發現4個點的新G值都比原來的大，所以當前的關注點並不是最好的點。算法不需要更新4個點的F,G,H值。
檢查C的4個鄰居點，找到F最小的那個點。我們發現上、下兩個點的F值是一樣的，所以隨機選擇下面那個點作為新的關注點（這個處理方式，可能會導致最終計算出來的路徑不是真正的最短，只是相對較短），並將其放入到Close表中，同時將其從Open表中刪除。
圖片來自[1]
檢查當前關注點C的鄰居點：左，左下，下，共3個點。左下和下兩個點是新點，需要加入到Open表中。根據C的位置，重新計算C的3個可用鄰居點的G,H,F值。檢查C的3個鄰居點，找到F最小的那個點。我們發現C左邊那個點的F值最小，所以將關注點C移動到左邊那個點，並將其放入到Close表中。
檢查當前關注點C的鄰居點：左，左下，下，右下，共3個點。左下是新點，需要加入到Open表中……，就這樣迭代執行，用F值最小作為牽引，最後得到下面表格所示的算法執行結果圖。
問題來了：最短路徑就是藍色框框代表的格子嗎？在起始點哪裡，藍色框框轉了一個圈圈，這不是繞遠路了嗎？
A*算法使用了一個父節點的概念來從這些藍色框框（也就是Close表所包含的所有框框）中提取最短路徑。算法在關注一個點時，其周邊鄰居點都有一個屬性變量，這個變量可以告訴算法它是誰的鄰居，或者說它的父節點是誰。
前面說了，G值代表了從起始點到這個點的移動距離。某個鄰居點的G值，是根據當前關注點的G值來計算的。某個鄰居點，可能是多個關注點的鄰居點，所以它的G值可能會被計算很多遍。
哪個關注點能夠讓這個鄰居點的G值最小，這個關注點就是這個鄰居點的父節點。這個很現實，假設起始點是個富翁，誰讓某個點離富翁最近，誰就是這個點的親人。真是個唯利是圖的點！
重新看這張圖，圖中用一個圈圈加線條指向來表達父子節點的關係。直線指向誰，誰就是這個格子的父節點。
我們再來看這張圖，起始點右下角的點是關注點，它啟動了左下和下面兩個新點，讓他們有了G值（沒有啟動是他們的G值是無窮大），所以他們就唯利是圖，認了當前關注點為父親，線條都指向關注點。但是，關注點左邊的點，也就是起始點下面的點，它的G值比關注點給他的G值要小，所以它不願意改變父親，覺得起始點更親，所以它的父節點是起始點。
以此類推，雖然藍色框框圍著起始點轉了一圈，但是算法並沒有改變起始點右下角那個格子的父節點。
最後，從紅色終止點格子開始，根據指示其父節點的線條指向，就可以回溯到起始點，回溯過程經過的格子點，就是最短路徑（見圖中紅色原點所示）。
好了，到目前為止，A*算法的求解過程已經基本清楚了，主要總結為以下幾條：
1）把起始點添加到Close表，將其鄰居點加入到Open表。
2）重複以下幾個步驟：
2.1 ) 尋找Open表中F值最低的格子，設為關注點C。
2.2) 存放C到Close表；
2.3) 對相鄰的8個點，如果它不可通過或者已經在Close表中，略過它。反之， 如果它不在Open表中，把它添加進去。把當前關注點作為這一格的父節點。記錄這一格的F,G,和H值；如果它已經在Open表中，用G值為參考檢查新的路徑是否更好。更低的G值意味著更好的路徑。如果是這樣，就把這一格的父節點改成當前格，並且重新計算這一格的G和F值。
2.4) 滿足下列條件是停止搜索：把目標點添加進了Open表，找到了路徑；或沒有找到目標點，Open表已空了，路徑不存在。
3）保存路徑。從目標點開始，沿著每一點的父節點移動直到回到起始點。這就是最短路徑。
[1] A* Path finding for Beginners. https://www.gamedev.net/articles/programming/artificial-intelligence/a-pathfinding-for-beginners-r2003/
[2] 無人駕駛汽車系統入門（十六）——最短路徑搜索之A*算法 . https://blog.csdn.net/AdamShan/article/details/79945175
[3] a*自動尋路算法詳解. https://blog.csdn.net/jialeheyeshu/article/details/53105810
[4] 我見過的最容易讀懂的 a*算法(A*尋路初探). https://blog.csdn.net/windcao/article/details/1533879
閱讀更多 原力源 的文章
