一、A* 算法簡介
A*?algorithm is a popular choice for graph search.?Breadth First Search?is the simplest of the graph search algorithms.?Graph search algorithms, including A*, take a “graph” as input.?
A*?algorithm is a modification of Dijkstra’s Algorithm that is optimized for a single destination.
A* algorithm uses?both?the actual distance from the start and the estimated distance to the goal.
From:?https://www.redblobgames.com/pathfinding/a-star/introduction.html

二、A* 算法的估值更新
A* 算法的估值更新，需要用到 A* 算法的啟發函數 h(x)。
相應地，A* 算法的可表示為：f(x)=g(x)+h(x)，其中：
f(x)：從初始狀態經由當前狀態 x 到目標狀態的估計代價
g(x)：從初始狀態到當前狀態 x 的實際代價
h(x)：從當前狀態 x 到目標狀態的估計代價

注意：
1. 針對 f(x)=g(x)+h(x)，如果 h(x)=0，就是普通的BFS算法；如果 g(x)=0，就是貪心算法。所以 A* 算法就是“BFS+貪心”。
2. 啟發函數 h(x) 決定了A*算法的優劣。啟發函數 h(x) 包括曼哈頓距離、對角線距離（切比雪夫距離）、歐幾里得距離等。啟發函數 h(x) 必須滿足單調性（即估計代價不會超過從當前狀態 x 到目標狀態的的實際代價）。A*算法的主要難點是設計合適的 h(x) 函數，而編碼很容易。
3.?在二維平面上，有3種方法可以近似計算 h(cur)。
下面的 (cur.x, cur.y) 是 cur 點的坐標，(t.x, t.y) 是終點 t 的坐標。
（1）曼哈頓距離
應用場景：只能在四個方向（上，下，左，右）移動。
h(cur)=abs(cur.x–t.x)+abs(cur.y–t.y)
（2）對角線距離
應用場景：可以在八個方向上移動，例如國際象棋的國王的移動。
h(cur)=max(abs(cur.x–t.x), abs(cur.y–t.y))
（3）歐幾里得距離。
應用場景：可以向任何方向移動。
h(cur)=sqrt((cur.x–t.x)^2+(cur.y–t.y)^2)
非平面問題，需要設計合適的 h 函數。
4.?計算 h(x) 時，要忽略路徑中的障礙物。因為 h(x) 是對剩余距離的估算值，而不是實際值，因此? h(x) 為估計代價。
5.?A*算法中，地圖必須是可行的，即不存在無法通過的障礙物或無法到達的區域。同時，需將地圖“網格化”，“網格化”其實就是將連續的問題離散化。
6.?A*算法中，選取下一個格子的標準并不是離終點最近，而是離起點和終點的距離之和最近。

三、A* 算法的步驟
在 A* 算法中，需要使用兩個輔助表來記錄結點。
一個用于記錄可被訪問的結點，稱為 openList 表；一個是記錄已訪問過的結點，稱為 closeList 表。
A* 算法的終止條件是終點在 closeList 表中（找到路徑）或 openList 表為空（找不到路徑）。
-------------------------------------
A* 算法的簡單步驟如下：
1.把起始節點添加到openList；
2.重復如下步驟：
? ?a) 尋找 openList 當中 F 值最低的結點，將其稱為當前結點；
? ?b) 將該結點從 openList 中刪除，并加入 closeList 當中；
? ?c) 對于當前結點相鄰的 8 個結點
? ? ? ?* 如果它不可通過或者已在 closeList 當中，忽略它，反之如下；
? ? ? ?* 如果它不在 openList 當中，將其添加進去。把當前結點作為它的父結點。同時更新它的 F，G 和 H 值。
? ? ? ?* 如果它已經在 openList 當中，通過判斷沿當前結點到它的路徑的 G 值是否更小，若更小，則將當前結點作為它的父結點，同時更新它的 F 和 G 值。否則，不做任何操作。
? ?d) 當目標結點已添加到 closeList 時，路徑已被找到；或者沒有找到目標結點，此時 openList 已為空。這時候，路徑不存在。以上兩種情況結束循環。
3.路徑回歸。從目標結點開始，沿著每一個結點的父結點移動至起始結點，形成的路徑即為所求路徑。


?