A* 路徑搜索算法

假設地圖中存在起點和終點，路徑搜索算法可以用於搜索起點到終點的路徑。在機器人路徑規劃，或者遊戲中都需要用到路徑搜索算法。本文介紹一種經典的 A* 算法，和 Dijkstra 算法相比，A* 採用啟發式的搜索策略，能夠更快地搜索出最短路徑。

1.前言

圖中的起點和終點

給定一個包含起點 (白色圓點) 和終點 (黑色圓點) 的圖，有很多條路徑可以從起點到達終點，但是很多不是最短路徑。如上圖所示，黑色虛線為最短路徑，紅色虛線不是。

Dijkstra 算法是其中一種求解起點到終點最短路徑的算法，在用於無權重圖時，Dijkstra 算法就是寬度優先 (BFS) 的方法。A* 對 Dijkstra 進行了優化，引入啟發式的搜索策略，可以更快地搜索出最短路徑。

2.Dijkstra算法

假設起點是 s，終點是 e，Dijkstra 算法的主要包括下面的流程。

• 步驟一：用一個集合 F 保存已經訪問過的節點，初始時 F 只包含起點 s。用一個數組 D 保存起點 s 到其餘所有節點的最短路徑。在開始時，D 的數值用下面的公式計算。

初始距離數組 D

• 步驟二：找到一個不在 F 中，並且 D[u] 最小的節點 u。D[u] 就是起點 s 到節點 u 的最短距離，把 u 加入 F。
• 步驟三：用節點 u 更新數組 D 中的最短距離，如下面的公式。

更新距離數組 D

• 步驟四：如果 F 中已經包含終點 e，則最短路徑已找到，否則繼續執行步驟二。

Dijkstra 算法可以用於有權重 (即節點之間的距離是不同的) 和無權重 (節點間距離一樣) 的圖，如果用於無權重的圖，Dijkstra 算法就是 BFS 算法。

下圖展示了用 Dijkstra 算法搜索無權重圖最短路徑的過程，橙色表示算法搜索過的區域，顏色由淺到深，表示搜索的深度 (先後順序)。淺橙色表示最先搜索到的節點，而深橙色表示最後搜索到的節點。

Dijkstra 算法搜索過程

3.A* 算法

A* 算法加入了啟發式的搜索策略，在搜索時間上通常優於 Dijkstra 算法。A* 使用了一個估計值 F 代表某一個節點到終點的估計距離，計算公式如下：

A* 算法估計值 F 計算公式

另外 A* 包含兩個列表，open list 和 close list，open list 保存了等待探索的節點，而 close list 表示已經探索過的節點。

A* 算法的流程如下：

• 步驟一：把起點 s 放入到 open list 裡面。
• 步驟二：檢查 open list，如果終點 e 在 open list 裡面，則路徑搜索完成。如果 open list 為空，則說明不存在路徑。
• 步驟三：在 open list 裡面選擇估計值 F 最小的節點 u，作為當前節點，然後加入 close list 裡面。
• 步驟四：取得所有節點 u 可以直接到達的節點 v，然後更新 open list。更新規則：如果 v 在 close list 裡，則不處理；如果 v 不在 open list 裡面，則把 v 加入 open list，其對應 F 值為 G(u)+distance(u,v)+H(v)；如果 v 在 open list 裡面，則檢查 v 是否有更小的 F 值 (如果有更小 F 值，就更新 v 的 F 值)；
• 重複步驟二到步驟四，直到終止。

下面是 A* 搜索最短路徑的示例，每一個節點中左邊的數字表示 G(n) 即真實距離，右邊的數字表示 H(n) 即啟發函數計算的距離。F 值就是 G(n)+H(n)，在下面的例子中 H(n) 用曼哈頓距離計算 (在下面的例子中等於沒有障礙物時，n 到終點 e 的最短距離)。

A* 算法的例子

4.A* 啟發函數的選擇與區別

如果不設置啟發函數，則 A* 就是 Dijkstra 算法，這時可以找到最短路徑。

如果啟發函數 H(n) 的值一定小於等於 n 到終點的實際距離，則 A* 可以保證找到最短路徑。

如果 H(n) 的值等於 n 到終點的實際距離，則 A* 會直接找到最短路徑，而不用擴展搜索額外的節點，此時運行是最快的。

如果 H(n) 的值有可能大於 n 到終點的實際距離，則 A* 算法不一定可以找到最短路徑，但是運行速度會比較快。

5.參考文獻

Amit’s A* Pages 地址： http://theory.stanford.edu/~amitp/GameProgramming/