編碼 · 演算法
A* 搜尋演算法教學：原理、程式碼與時間複雜度
簡答
A* 搜尋結合已付出的成本 g(n) 與剩餘成本的估計 h(n)，找出從起點到單一目標節點的最短路徑。它總是展開 f(n) = g(n) + h(n) 最小的節點。只要啟發函式不會高估真實的剩餘成本，A* 就保證回傳最佳路徑，而好的啟發函式能讓它探索的節點遠少於 Dijkstra 演算法。
A* 解決什麼問題
Dijkstra 演算法會朝各個方向以距離遞增的一圈圈範圍展開節點，連遠離目標的方向也不例外。當你知道目標在哪裡時，這些都是白費的工夫。A* 加入了啟發函式，也就是對剩餘距離的估計，讓搜尋被拉向目標。它是遊戲、機器人和地圖中尋路的標準演算法。
A* 由 Peter Hart、Nils Nilsson 和 Bertram Raphael 於 1968 年在「A Formal Basis for the Heuristic Determination of Minimum Cost Paths」中提出。
用白話說明原理
| 符號 | 意義 |
|---|---|
| g(n) | 從起點到 n 的已知最佳路徑成本。 |
| h(n) | 從 n 到目標的成本的啟發式估計。 |
| f(n) = g(n) + h(n) | 經過 n 的最便宜完整路徑的估計成本。開放集合依 f 排序。 |
- 將起點放入優先佇列（開放集合），g = 0，f = h(start)。
- 彈出 f 最小的節點。如果它是目標，就重建路徑並停止。
- 對每個鄰居，計算暫定的 g = g(current) + 邊成本。如果比鄰居目前已知的 g 更好，就記錄下來、設定父節點，並以 f = g + h 把鄰居推入佇列。
- 如果開放集合變空，就代表沒有路徑。
若所有節點的 h(n) = 0，A* 就完全等同於 Dijkstra 演算法。若啟發函式完美，它會沿著最佳路徑直線前進。
選擇啟發函式
如果啟發函式不會高估真實的剩餘成本，它就是可容許的（admissible）。如果對每條邊 n → m 都滿足 h(n) <= cost(n, m) + h(m)，它就是一致的（consistent，或稱單調）。一致的啟發函式一定也是可容許的，而且每個節點只需展開一次。
| 移動方式 | 啟發函式 | 公式 |
|---|---|---|
| 網格上 4 個方向，成本為 1 | 曼哈頓距離 | abs(dx) + abs(dy) |
| 8 個方向，斜向成本為 1 | 切比雪夫距離 | max(abs(dx), abs(dy)) |
| 8 個方向，斜向成本為 √2 | 八分位距離（octile distance） | max(dx, dy) + (sqrt(2) - 1) * min(dx, dy)，其中 dx、dy 取絕對值 |
| 任意方向，直線移動 | 歐幾里得距離 | sqrt(dx * dx + dy * dy) |
網格上的 Python 實作
下面的網格有 5 列 7 欄；# 代表第 5 欄的牆。格子以 (row, column) 表示。可以向上、下、左、右移動，成本為 1，所以曼哈頓距離是可容許且一致的。
import heapq
def a_star(grid, start, goal):
rows, cols = len(grid), len(grid[0])
h = lambda p: abs(p[0] - goal[0]) + abs(p[1] - goal[1])
g = {start: 0}
parent = {start: None}
open_heap = [(h(start), start)]
while open_heap:
f, cur = heapq.heappop(open_heap)
if cur == goal:
path = []
while cur is not None:
path.append(cur)
cur = parent[cur]
return path[::-1]
if f > g[cur] + h(cur):
continue # outdated entry
r, c = cur
for nb in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nb[0] < rows and 0 <= nb[1] < cols and grid[nb[0]][nb[1]] != "#":
ng = g[cur] + 1
if ng < g.get(nb, float("inf")):
g[nb] = ng
parent[nb] = cur
heapq.heappush(open_heap, (ng + h(nb), nb))
return None
grid = [".......",
".....#.",
".....#.",
".....#.",
"......."]
path = a_star(grid, (2, 3), (2, 6))
print(len(path) - 1, path)
# 7 [(2, 3), (2, 4), (1, 4), (0, 4), (0, 5), (0, 6), (1, 6), (2, 6)]逐步範例
在上面的網格中，起點 (2, 3) 沿直線到目標 (2, 6) 只有 3 步，所以第一個 f 是 0 + 3 = 3。牆擋住了這條直線，真正的最短路徑有 7 步。A* 分階段發現這件事：它先展開 f 最小的所有格子，用完之後再展開下一個最小的 f。
| f 值 | 展開的格子（依序） | 發生了什麼 |
|---|---|---|
| 3 | (2, 3), (2, 4) | 直接朝目標前進，直到遇到牆。 |
| 5 | (1, 3), (1, 4), (2, 2), (3, 3), (3, 4) | 往旁邊或後退一步要多付 2；仍被擋住。 |
| 7 | (0, 3), (0, 4), (0, 5), (0, 6), (1, 2), (1, 6), (2, 1), (2, 6) | 繞過牆的上方；目標在 f = 7 時被彈出。 |
A* 在 32 個可通行格子中展開了 15 個。Dijkstra 演算法（即 h = 0 的 A*）則會展開全部 32 個，因為每個可通行格子離起點都不超過 7 步。在大型開闊的地圖上，節省的幅度會大得多。
時間與空間複雜度
| 項目 | 成本 | 原因 |
|---|---|---|
| 最差時間 | O((V + E) log V) | 與 Dijkstra 相同：像 h = 0 這種無用的啟發函式提供不了任何引導。 |
| 一般時間 | 遠少於 Dijkstra | 完全取決於啟發函式的品質；完美的 h 只會展開路徑上的節點。 |
| 空間 | O(V) | 開放堆積、g 值與父節點。在超大地圖上，記憶體往往才是真正的限制。 |
節省記憶體的變化版本包括 IDA*（迭代加深 A*），它只保留目前的路徑，代價是會重複拜訪節點。
何時使用 A* 與實際應用
- 當只有一個目標，而且有便宜又可容許的剩餘成本估計（例如地圖上的幾何距離）時，請使用 A*。
- 需要到許多或所有節點的距離，或找不到有用的啟發函式時，請用 Dijkstra。無權重圖且啟發函式幫助不大時，請用 BFS。
- 電玩遊戲：在格狀地圖和導航網格（navigation mesh）上移動單位。
- 機器人與路線規劃，常結合預先計算的地標或階層結構。
- 解謎：8 數字謎題與 15 數字謎題，以方塊的曼哈頓距離作為啟發函式。
常見問題
A* 一定是最佳的嗎？
當啟發函式是可容許的（也就是不會高估剩餘成本）時，A* 會回傳最佳路徑。若啟發函式高估，它可能回傳較長的路徑。
A* 和 Dijkstra 演算法有什麼差別？
Dijkstra 依已付出的成本 g(n) 排序節點。A* 則依 g(n) + h(n) 排序，其中 h 估計到目標的剩餘成本。h = 0 的 A* 就是 Dijkstra。
在網格上該用哪種啟發函式？
4 個方向的移動用曼哈頓距離；8 個方向的移動依斜向成本用切比雪夫或八分位距離；可自由移動則用歐幾里得距離。
什麼是貪婪最佳優先搜尋？
它只依 h(n) 排序節點，忽略已付出的成本。通常很快，但不保證找到最短路徑。