跳转至

# 迭代加深搜索

## 定义

迭代加深是一种 每次限制搜索深度的 深度优先搜索．

## 解释

迭代加深搜索的本质还是深度优先搜索，只不过在搜索的同时带上了一个深度 𝑑 d，当 𝑑 d 达到设定的深度时就返回，一般用于找最优解．如果一次搜索没有找到合法的解，就让设定的深度加一，重新从根开始．

既然是为了找最优解，为什么不用 BFS 呢？我们知道 BFS 的基础是一个队列，队列的空间复杂度很大，当状态比较多或者单个状态比较大时，使用队列的 BFS 就显出了劣势．事实上，迭代加深就类似于用 DFS 方式实现的 BFS，它的空间复杂度相对较小．

当搜索树的分支比较多时，每增加一层的搜索复杂度会出现指数级爆炸式增长，这时前面重复进行的部分所带来的复杂度几乎可以忽略，这也就是为什么迭代加深是可以近似看成 BFS 的．

## 过程

首先设定一个较小的深度作为全局变量，进行 DFS．每进入一次 DFS，将当前深度加一，当发现 𝑑 d 大于设定的深度 𝑙 𝑖 𝑚 𝑖 𝑡 limit 就返回．如果在搜索的途中发现了答案就可以回溯，同时在回溯的过程中可以记录路径．如果没有发现答案，就返回到函数入口，增加设定深度，继续搜索．

实现（伪代码）

    1
    2
    3
    4
    5
    6
    7
    IDDFS(u,d)
        if d>limit
            return
        else
            for each edge (u,v)
                IDDFS(v,d+1)
    return

## 注意事项

在大多数的题目中，广度优先搜索还是比较方便的，而且容易判重．当发现广度优先搜索在空间上不够优秀，而且要找最优解的问题时，就应该考虑迭代加深．

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：Ir1d, H-J-Granger, StudyingFather, countercurrent-time, NachtgeistW, Enter-tainer, AngelKitty, CCXXXI, cjsoft, diauweb, Early0v0, ezoixx130, GekkaSaori, Konano, LovelyBuggies, Makkiy, mgt, minghu6, P-Y-Y, PotassiumWings, SamZhangQingChuan, sshwy, Suyun514, weiyong1024, wjy-yy, GavinZhengOI, Gesrua, iamtwz, ksyx, kxccc, lychees, Peanut-Tang, SukkaW, Tiphereth-A
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用