A演算法簡介(AAlgorithmBrief).doc

A* 演算法簡介 (A* Algorithm Brief)
2004/12/20 09:44
A* (A-Star) 演算法是在Game中通常用來解決最短路徑(Shortest Path)問題的一種演算法. 相對於另一個知名的 Dijkstra 演算法來說, Dijkstra演算法雖然可以保證找到一條最短的路徑, 但不如A* 演算法這樣簡捷快速. 同時, Dijkstra的搜尋深度在某些情形下也容易顯得不適用. A* 演算法便是為了這些情形而出現的, 可以算是 Dijkstra演算法的一種改良.

底下用幾張圖來表現Dijkstra演算法與A* 演算法的不同:

Dijkstra 演算法
A* 演算法
無障礙

有障礙

(圖片取自 Amit's Thoughts on Path-Finding and A-Star)

從以上的比較圖可以看出, A* 演算法的搜尋深度雖然不如 Dijkstra演算法, 但其結果仍然是很令人滿意的. 為什麼A* 演算法可以達到這樣的結果呢? 這是因為A* 演算法採用了一套特殊的啟發式評價(Heuristic Estimate)公式將許多明顯為壞的路徑排除考慮, 進而快速計算出一條滿意的路徑.

公式如下:

f(n) = g(n) + h(n)

g(n): 從啟始點到目前節點的距離
h(n) 預測目前節點到結束點的距離(此為 A* 演算法的主要評價公式)
f(n): 目前結點的評價分數

其中, h(n) 主導著A* 演算法的表現方式. 有以下幾種情形:
1. h(n)=0: A* 演算法這時等同 Dijkstra演算法, 並且保證能找到最短路徑
2. h(n)<目前節點到結束點的距離: A* 演算法保證找到最短路徑, h(n)越小, 搜尋深度越深
3. h(n)=目前節點到結束點的距離: A* 演算法僅會尋找最佳路徑, 並且能快速找到結果
4. h(n)>目前節點到結束點的距離: 不保證能找到最短路徑, 但計算比較快
5. h(n)與g(n)高度相關: A* 演算法此時成為 BFS (Best-First Search)

A* 演算法的虛擬碼如下:
Add START to OPEN list
while OPEN not empty
get node n from OPEN that has the lowest f(n)
if n is GOAL then return path
move n to CLOSED
for each n' = CanMove(n, direction)
g(n') = g(n) + 1
calculate h(n')
if n' in OPEN list and new n' is not better, continue
if n' in CLOSED list and new n' is not better, continue
remove any n' from OPEN and CLOSED
add n as n's parent
add n' to OPEN
end for
end while

if we get to here, then there is No Solution

以上虛擬碼適用於一般遊戲中方格圖(Grid Map)的情形. 當要在真實地圖的路網(Road Map)上使用A* 演算法時, g(n)與h(n)的計算方式便會有所不同.

相關參考資料:

網頁:
Amit's Thoughts on Path-Finding and A-Star
Creating an A* algorithm Robot for QUT SoKoBan

維基百科:
Shortest Path Problem
A* Search Algorithm
Dijkstra Algorithm

書籍:
Core Techniques and Algorithms in Game Programming (英文)
大師談遊戲程式設計：核心技術與演算法 (中文)