算法知识图谱总览 / 搜索算法族 / 迭代加深(IDDFS)

迭代加深(IDDFS)

P1intermediatestandardG-A-14
← 上一个 / 组内bidirectional 组内第 3 / 9返回组索引 全局返回总览 下一个 / 组内heuristic-search

What · 是什么

逐步增加DFS深度限制，DFS方式实现BFS效果，空间优

迭代加深搜索（Iterative Deepening Depth-First Search, IDDFS）每次限制搜索深度 d 做一次 DFS，若没找到解就把 d 加一重来。它用 DFS 的方式实现了 BFS 的'逐层搜索'效果：保证第一次找到的解是最优解（步数最少），而空间复杂度只有 O(深度) 而非 BFS 的 O(分支数^深度)。适合状态空间巨大、单个状态又大、且要最优解的搜索问题。

Why · 为什么

直觉 · Intuition

BFS 用队列逐层展开，答案在最深层时队列可能塞满整层节点（指数级）。迭代加深每轮只做一次限深的 DFS，一轮只走一条路径；重复搜索前面层看似浪费，但当分支因子大时，前面层的节点数相比最后层可忽略，'白跑'的代价很小，换来的是空间从指数降到线性。

原理 · Principle

设分支因子 b、目标深度 d。IDDFS 的 DFS 每轮展开约 b^d 个节点（最后一层），前面 d-1 轮合计约 b^{d-1}+b^{d-2}+...+1 < b^d/(b-1)。总工作量约 b^d·b/(b-1)，与 BFS 同阶，但空间 O(d) 远小于 BFS 的 O(b^d)。当分支因子 b 大时 b/(b-1)→1，重复搜索的额外开销趋近于 0。这就是'为什么迭代加深可近似看成 BFS'的原因。若存在解在深度 d 内，第 d 轮必能找到，且因逐层递增必为最短解。

历史 · History

迭代加深概念源于 20 世纪 60-70 年代的 AI 搜索（与 IDA* 同源），被用作内存受限环境下替代 BFS 的标准策略。Korf 在 1985 年系统分析了迭代加深的复杂度（与 BFS 同阶但线性空间），并推广为 IDA*。

How · 实现

伪代码

def IDDFS(root, limit_max):
    for limit in 0..limit_max:
        if DFS(root, depth=0, limit) 找到:
            return 解
    return 无解

def DFS(u, d, limit):
    if 是目标: return True
    if d == limit: return False
    for v in 邻居(u):
        if DFS(v, d+1, limit): return True
    return False

Python 实现

def id_dfs(start, is_goal, neighbors, max_depth=30):
    """迭代加深DFS: 找从start到目标的最短路径
    is_goal(u) 判目标, neighbors(u) 返回邻居
    返回: 路径列表或 None
    """
    path = [start]

    def dfs(u, d, limit):
        if is_goal(u):
            return True
        if d == limit:
            return False
        for v in neighbors(u):
            if v in path:      # 避免环
                continue
            path.append(v)
            if dfs(v, d + 1, limit):
                return True
            path.pop()
        return False

    for limit in range(max_depth + 1):
        if dfs(start, 0, limit):
            return path
    return None


if __name__ == "__main__":
    # 目标在深度3, 分支因子2的树
    tree = {
        'a': ['b', 'c'],
        'b': ['d', 'e'],
        'c': ['f', 'g'],
        'd': ['h', 'i'],
        'e': [], 'f': [], 'g': [], 'h': [], 'i': []
    }
    def neighbors(u): return tree.get(u, [])
    def is_goal(u): return u == 'h'

    path = id_dfs('a', is_goal, neighbors)
    assert path == ['a', 'b', 'd', 'h'], path

    # 目标在根: 深度0
    assert id_dfs('a', lambda u: u == 'a', neighbors) == ['a']
    # 无解
    assert id_dfs('a', lambda u: u == 'zzz', neighbors, max_depth=3) is None

    print("iterative-deepening all tests passed")
PyPy 提示迭代加深的每轮 DFS 都重新从根走，PyPy 下递归调用开销需注意；分支因子大时工作量大。可用 path 列表做显式栈避免 'v in path' 的 O(d) 查找（用 set 或标记数组）。深递归需 sys.setrecursionlimit。
时间复杂度O(b^d)，与 BFS 同阶（b 分支因子, d 目标深度）
空间复杂度O(d) 递归栈，优于 BFS 的 O(b^d)
注意 · 局限分支因子大或深度无上界时仍可能超时；每轮重搜带来常数倍开销；需保证'深度内必有解'才能保证最优性；有环图要防环（路径判重）。

易错点

例题

OJ题号难度考点链接
LuoguP17634埃及分数：深度无上界+无限分支，迭代加深+剪枝经典题https://www.luogu.com.cn/problem/P1763
UVA13434The Rotation Game：旋转游戏，迭代加深+剪枝https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=4089
步骤迷你图（节点 = 算法步骤 · 边 = 流程 · 绿色 = 起始步骤）
上游 · 本知识点依赖（前置/变体/组合/共现）
DFS深度优先搜索变体
下游 · 依赖本知识点
IDA*算法前置依赖

信源

✓ = 已核验 · △ = 未核验