經典算法研究：啟發式搜索算法通論——從最優優先到A*的理論基石

啟發式搜索是人工智能領域求解大規模狀態空間問題的核心技術。本文從通用圖搜索算法（GRAPHSEARCH）出發，推導最優優先搜索、A*算法、可採納性/一致性條件、啟發函數設計原理，並分析啟發式對分支因子與效率的影響。

一、 通用圖搜索算法 GRAPHSEARCH

GRAPHSEARCH
1  OPEN ← {s}, CLOSED ← ∅
2  while OPEN ≠ ∅:
3      n ← 從 OPEN 取出節點 (策略決定)
4      if n 是目標: return 回溯路徑
5      CLOSED ← CLOSED ∪ {n}
6      M ← 展開 n 的後繼節點
7      將 M 中不在 CLOSED 的節點加入 OPEN
8      按策略重排 OPEN
9  return 失敗

策略差異：

• BFS：新節點加入 OPEN 尾部（FIFO）。
• DFS：新節點加入 OPEN 頭部（LIFO）。
• 最優優先：按啟發函數f̂(n)升序重排。
• A*：按f̂(n) = ĝ(n) + ĥ(n)升序重排。

二、 A* 算法標準流程

A*
1  OPEN ← {s}, CLOSED ← ∅
2  ĝ(s) ← 0, ĥ(s) ← h(s), f̂(s) ← ĥ(s)
3  while OPEN ≠ ∅:
4      n ← 取 f̂ 最小節點
5      if n 目標: return 重構路徑
6      移 n 至 CLOSED
7      for each m ∈ 後繼(n):
8          if m ∈ CLOSED: continue
9          ĝ_new ← ĝ(n) + cost(n,m)
10         if m ∉ OPEN 或 ĝ_new < ĝ(m):
11             ĝ(m) ← ĝ_new; ĥ(m) ← h(m); f̂(m) ← ĝ(m)+ĥ(m)
12             父指標指向 n
13             if m ∉ OPEN: 加入 OPEN
14             else: 更新 OPEN 中鍵值
15  return 失敗

三、 關鍵理論：可採納性與一致性

• g(n)：起點到n的真實最小代價。
• h(n)：n到目標的真實最小代價。
• f(n) = g(n) + h(n)：經過n的最優路徑代價。
• ĝ(n)：算法發現的到n的最小代價（≤ g(n)）。
• ĥ(n)：h(n)的估計值。

可採納性

ĥ(n) ≤ h(n)（估計不超過真實值）。
定理：若ĥ可採納，A*保證找到最優解。

一致性（單調性）

ĥ(n) ≤ cost(n,m) + ĥ(m) 對任意鄰接m成立。
等價於：沿任意路徑f̂值單調不減。
定理：一致性 ⇒ 可採納性；一致性下，每個節點只需展開一次（無需CLOSED重新展開），效率更高。

四、 啟發函數設計指南

1. 問題放松：移除約束條件求解簡化問題（如八數碼忽略空格限制 → 曼哈頓距離）。
2. 模式數據庫：預計算子問題最優解存表查詢。
3. 組合啟發：h(n) = max(h₁,h₂,...,hₖ)，取最大仍可採納且更強。
4. 學習啟發：ABSOLVER 自動合成啟發函數（1993年突破八數碼/魔方）。

五、 啟發式對分支因子的壓縮效應

無技巧搜索需展開bᵈ節點（b分支因子，d深度）。
啟發式將有效分支因子從b降至b* < b。
定義：若h₁導致的有效分支因子小於h₂，則h₁ ≺ h₂（h₁更優）。
良好啟發函數能指數級縮減搜索樹，使原本不可解問題在多項式時間內求解。

六、 經典問題：n-puzzle 啟發函數

• h₁：錯位數碼個數（可採納，弱）。
• h₂：曼哈頓距離和（可採納，強）。
• h₃：線性衝突 + 曼哈頓（可採納，更強）。

實測：h₂比h₁快數量級；h₃更快。展示「可採納且更強 ⇒ 效率更高」原則。

掌握 GRAPHSEARCH 框架、可採納/一致性理論、啟發函數設計三大支柱，即掌握了啟發式搜索的理論核心與工程指南。