一、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.路徑回歸。從目標結點開始,沿著每一個結點的父結點移動至起始結點,形成的路徑即為所求路徑。
?