7.1 迭代加深搜尋#

概念說明#

搜尋樹時，兩種經典遍歷各有短板：廣度優先（BFS）保證找到最淺解，但需儲存整層節點，空間 \(O(b^d)\) （ \(b\) 為分支因子、 \(d\) 為解深度），深層樹直接爆記憶體；深度優先（DFS）只需 \(O(d)\) 空間，卻可能沿一條死胡同挖到天荒地老，找到的解也未必最淺。

迭代加深搜尋（Iterative Deepening DFS, IDDFS）把兩者縫合：以深度限制 \(0, 1, 2, \dots\) 逐輪執行 DFS，每輪只在限制內下探。結果：找到的解與 BFS 同樣淺（保證最優，當各步成本相同時），空間仍是 DFS 的 \(O(d)\) ，時間 \(O(b^d)\) 。

乍看「重複搜尋上層」很浪費，實則不然。算總節點數：第 \(k\) 輪產生約 \(b^k\) 個節點，全系列為

對 \(b = 10\) ，重複開銷僅約 11%——因為樹的絕大多數節點都在最後一層，前面幾輪的重做只是零頭。這是「指數結構下重複計算很便宜」的經典範例（7.2 節將看到相反情形）。

IDDFS 是遊戲 AI 的標配：西洋棋引擎每給定時間片，就從深度 1 開始逐層加深，時間到就用最後完成的深度——兼具逐步改善的「隨時可中斷」性質。搭配備忘錄（記住已評估局面）還能進一步加速。變形：IDA* 把深度限制換成 \(f = g + h\) 的成本限制，用於帶啟發式函數的問題（如 15-puzzle）。

生活類比#

找遙控器：先搜客廳桌上一層（所有順手處），沒有就 systematic 地搜每個房間的第一層抽屜，再下一層……每次範圍加深一層。雖然客廳被搜了又搜，但「淺處先找完」的保證讓你通常很快命中。

演算法步驟#

1. for depth = 0, 1, 2, ...：
2. 執行限制深度為 depth 的 DFS（dls(node, depth)）：
   • 若 node 為目標，回傳成功。
   • 若 depth == 0，回傳截斷。
   • 對每個子節點遞迴 dls(child, depth - 1)。
3. 成功即回傳路徑；整輪皆截斷且無目標，加深一輪。
4. 若樹有窮而未設上限，必找到解（最壞情形是目標不存在且樹無限）。

Python 範例#

# 以鄰接字典表示樹/圖
tree = {
    'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F', 'G'],
    'D': ['H', 'I'], 'E': ['J'], 'F': ['K'], 'G': [], 'H': [],
    'I': [], 'J': ['L'], 'K': [], 'L': [],
}

def dls(node, target, depth, path):
    """限制深度 DFS，回傳路徑或 None"""
    if node == target:
        return path
    if depth == 0:
        return None
    for ch in tree.get(node, []):
        r = dls(ch, target, depth - 1, path + [ch])
        if r is not None:
            return r
    return None

def iddfs(root, target, max_depth=10):
    calls = 0
    for depth in range(max_depth + 1):
        r = dls(root, target, depth, [root])
        if r is not None:
            return r, depth, calls
    return None, None, calls

path, depth, _ = iddfs('A', 'K')
print(f"找到 {path}（深度 {depth}）")

# 統計重複開銷
def count_nodes(node, depth):
    if depth == 0:
        return 1
    return 1 + sum(count_nodes(c, depth - 1) for c in tree.get(node, []))

total = sum(count_nodes('A', d) for d in range(5))   # 解在深度 4
print(f"各輪節點總數 {total}，單輪最深 {count_nodes('A', 4)}，"
      f"重複開銷比 {total / count_nodes('A', 4):.2f}")

複雜度與收斂性分析#

時間 \(O(b^d)\) 、空間 \(O(d)\) ，完整率與最優性與 BFS 相同。與 BFS 比空間優勢巨大（ \(b = 10, d = 8\) 時 BFS 需存約億級節點，IDDFS 只存 8 個）。重複開銷因子 \(b/(b-1)\) ， \(b\) 越大越無害； \(b = 2\) 時因子為 2，仍可接受。帶邊權的圖需改用一致成本搜尋（UCS）或 IDA* 才能保證最優。注意：在有環圖上需記錄當前路徑的訪問集合避免無限循環。

練習#

1. 將 iddfs 改為回傳所有深度為 \(d\) 的節點數統計，驗證重複開銷因子趨近 \(b/(b-1)\) 。
2. 實作 IDA* 解 8-puzzle（啟發式用曼哈頓距離），與純 IDDFS 比較擴展節點數。
3. 在有環圖（加一條 'L' → 'B' 的邊）上測試你的 IDDFS，加入環偵測後驗證正確性。