A* 搜尋：有第六感的 Dijkstra

Dijkstra 太老實

第 14 章的 Dijkstra 從起點往四周擴散，完全不考慮終點在哪。即使終點在東邊，它還是會往西、往南、往北一路擴散——浪費力氣。

A* 加入「方向感」：用一個估計函數 h(n)「猜」當前節點到終點的距離，優先處理「看起來最有希望」的節點。

公式

每個節點維護兩個值：

g(n) = 從起點走到 n 的實際已知最短距離
h(n) = 從 n 到終點的估計距離（heuristic）
f(n) = g(n) + h(n) ← 「估計的總長度」

從 priority queue 取 f(n) 最小的處理——這就是 A*。

當 h(n) = 0 時，A* 退化為 Dijkstra。

一個直覺例子

GPS 從台北到高雄：

Dijkstra：先試新竹、桃園、宜蘭、基隆、台中…全方向擴散
A*：知道高雄在南邊（h(n) = 直線距離），優先試桃園 → 新竹 → 台中…直奔南方

啟發函數的選擇

常見 h(n)：

網格圖、可斜走：歐幾里得距離 √((x1-x2)² + (y1-y2)²)
網格圖、只能上下左右：曼哈頓距離 |x1-x2| + |y1-y2|
真實地圖：直線距離（球面距離）
未知：h(n) = 0 → 退化為 Dijkstra

⚠️關鍵限制：admissible（可接受）

h(n) 不能高估真實距離——必須 ≤ 真正到終點的最短距離。

若 h(n) 高估了，A* 可能會跳過實際最短路徑，結果就不是最佳解。

直線距離永遠 ≤ 實際路徑（不可能比直線更短），所以是 admissible。這就是為什麼導航用直線距離當啟發函數。

Pseudocode

Algorithm AStar(graph, start, goal, h):

openSet ← PriorityQueue()

openSet.push((h(start), start))

g[start] ← 0

while openSet not empty:

current ← openSet.pop()

if current == goal: return reconstructPath()

for neighbor in graph[current]:

tentativeG ← g[current] + edgeWeight(current, neighbor)

if tentativeG < g[neighbor]:

g[neighbor] ← tentativeG

f ← tentativeG + h(neighbor)

openSet.push((f, neighbor))

A* vs Dijkstra vs BFS

演算法	用途	啟發	保證最佳
BFS	無權重最短路	—	✓
Dijkstra	非負權重最短路	—	✓
A*	目標導向最短路	h(n)	✓（h 可接受時）
Greedy Best-First	純啟發貪婪	h(n) only	✗

A* 是 Dijkstra 的目標導向版——當啟發函數準的時候，可以省非常多探索成本。

💡A* 為什麼正確？

A* 取 f(n) = g(n) + h(n) 最小的處理。

g(n) 是實際已知最短
h(n) 是可接受的估計（≤ 實際剩餘）
所以 f(n) ≤ 經過 n 的最短路徑總長

當取出 goal 時，因為 h(goal) = 0，f(goal) = g(goal) = 實際路徑長。所有其他 openSet 的節點 f ≥ g(goal)，不可能找到更短路徑 → 最佳。

經典應用

遊戲 AI：怪物追玩家、Pacman、即時戰略 NPC 移動
GPS / Google Maps：實際導航軟體常用 A* 或變體
拼圖求解：8-puzzle、15-puzzle，h = 錯位棋子數
機器人路徑規劃

📝考試會這樣考

題型一：給網格和起終點，跑 A*。 標出每個節點的 g, h, f 值，列出 openSet 變化和選擇順序。

題型二：什麼是 admissible heuristic？ 答：永遠不高估從 n 到終點的真實距離（h(n) ≤ 真實距離）。

題型三：A* vs Dijkstra 何時用哪個？

有明確終點 + 有合理啟發函數 → A*
要算到所有點的最短距離 → Dijkstra

題型四：h(n) 高估會怎樣？ 答：找到的路徑可能不是最短的（不保證最佳）。

題型五：A* 退化成 Dijkstra 的條件？ 答：h(n) = 0 for all n。沒有方向感、純看實際距離。

這章記住

A* = Dijkstra + 啟發函數 h(n)，f(n) = g(n) + h(n)。
h(n) 必須 admissible（不高估），否則不保證最佳。
h(n) = 0 → 退化為 Dijkstra；h(n) 越準 → A* 越快。
應用：遊戲 AI、GPS、機器人——所有「往特定目標走」的場景。