經典算法研究：A*搜索算法原理與實現詳解

A*算法是啟發式搜索的集大成者，廣泛應用於遊戲尋路、機器人規劃、地圖導航。本文從啟發式搜索基礎出發，推導A*估值函數，給出完整流程偽代碼與優先隊列實現要點。

一、 從盲目搜索到啟發式搜索

• DFS/BFS：盲目展開，不區分節點優劣，最壞遍歷整個狀態空間。
• 啟發式搜索：引入評估函數f(n)，優先展開「最有希望」的節點，大幅剪枝。

二、 A* 核心估值函數

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

• g(n)：從起點到節點n的實際代價（通常為路徑長度/深度）。
• h(n)：從n到目標的估計代價（啟發函數）。

A* 最優性充分條件（滿足則保證找到最優解）：

1. 搜索樹中存在起點到終點的最優路徑。
2. 問題域有限。
3. 所有邊代價 > 0。
4. h(n) ≤ h*(n)（可採納性）：估計值不超過真實最小代價。

條件4是設計核心。好的h(n)應盡量接近h*(n)但不超過，兼顧區分度與效率。

三、 A* 搜索流程與優先隊列

標準流程（OPEN/CLOSED 表）

OPEN ← {start}          // 優先隊列，按 f(n) 升序
CLOSED ← ∅
g(start) ← 0
h(start) ← heuristic(start, goal)
f(start) ← h(start)

while OPEN ≠ ∅:
    n ← POP_MIN(OPEN)           // 取 f 最小節點
    if n == goal: return reconstruct_path(n)
    move n from OPEN to CLOSED
    for each neighbor m of n:
        if m in CLOSED: continue
        tentative_g ← g(n) + cost(n, m)
        if m not in OPEN or tentative_g < g(m):
            g(m) ← tentative_g
            h(m) ← heuristic(m, goal)
            f(m) ← g(m) + h(m)
            parent(m) ← n
            if m not in OPEN: PUSH(OPEN, m)
            else: DECREASE_KEY(OPEN, m)
return failure

關鍵數據結構：優先隊列

• 二叉堆：O(log N) 插入/刪除/更新鍵值。
• 斐波那契堆：O(1) 平攤更新鍵值，理論最優但常數大，工程常用二叉堆或配對堆。

四、 與 Dijkstra、BFS、DFS 的關係

五、 常見啟發函數選擇

• 曼哈頓距離：|x1-x2| + |y1-y2|，適合四方向移動網格。
• 歐氏距離：√((x1-x2)²+(y1-y2)²)，適合任意角度移動。
• 切比雪夫距離：max(|x1-x2|, |y1-y2|)，適合八方向移動。

選擇原則：h(n)必須 ≤ 真實最小代價，且盡量大以提高效率。

六、 實戰提示

1. 優先隊列需支援DECREASE_KEY，或採用「懶惰插入」法（允許重複節點，POP時檢查CLOSED）。
2. 記憶體優化：CLOSED可用位圖/哈希表；大地圖採用分塊/層級A*。
3. 動態環境：D* Lite、LPA* 等增量算法更適合。

A* 是啟發式搜索的基石，掌握其估值函數設計與優先隊列實現，即掌握了解決大規模最優路徑問題的鑰匙。