迭代加深搜索
定义
迭代加深是一种 每次限制搜索深度的 深度优先搜索．
解释
迭代加深搜索的本质还是深度优先搜索，只不过在搜索的同时带上了一个深度 𝑑d
，当 𝑑d 达到设定的深度时就返回，一般用于找最优解．如果一次搜索没有找到合法的解，就让设定的深度加一，重新从根开始．
既然是为了找最优解，为什么不用 BFS 呢？我们知道 BFS 的基础是一个队列，队列的空间复杂度很大，当状态比较多或者单个状态比较大时，使用队列的 BFS 就显出了劣势．事实上，迭代加深就类似于用 DFS 方式实现的 BFS，它的空间复杂度相对较小．
当搜索树的分支比较多时，每增加一层的搜索复杂度会出现指数级爆炸式增长，这时前面重复进行的部分所带来的复杂度几乎可以忽略，这也就是为什么迭代加深是可以近似看成 BFS 的．
过程
首先设定一个较小的深度作为全局变量，进行 DFS．每进入一次 DFS，将当前深度加一，当发现 𝑑d 大于设定的深度 𝑙𝑖𝑚𝑖𝑡limit 就返回．如果在搜索的途中发现了答案就可以回溯，同时在回溯的过程中可以记录路径．如果没有发现答案，就返回到函数入口，增加设定深度，继续搜索．
实现（伪代码）
---|---
## 注意事项
在大多数的题目中，广度优先搜索还是比较方便的，而且容易判重．当发现广度优先搜索在空间上不够优秀，而且要找最优解的问题时，就应该考虑迭代加深．
* * *
> __本页面最近更新： 2026/1/7 08:56:54，[更新历史](https://github.com/OI-wiki/OI-wiki/commits/master/docs/search/iterative.md)
> __发现错误？想一起完善？[在 GitHub 上编辑此页！](https://oi-wiki.org/edit-landing/?ref=/search/iterative.md "edit.link.title")
> __本页面贡献者：[Ir1d](https://github.com/Ir1d), [H-J-Granger](https://github.com/H-J-Granger), [StudyingFather](https://github.com/StudyingFather), [countercurrent-time](https://github.com/countercurrent-time), [NachtgeistW](https://github.com/NachtgeistW), [Enter-tainer](https://github.com/Enter-tainer), [AngelKitty](https://github.com/AngelKitty), [CCXXXI](https://github.com/CCXXXI), [cjsoft](https://github.com/cjsoft), [diauweb](https://github.com/diauweb), [Early0v0](https://github.com/Early0v0), [ezoixx130](https://github.com/ezoixx130), [GekkaSaori](https://github.com/GekkaSaori), [Konano](https://github.com/Konano), [LovelyBuggies](https://github.com/LovelyBuggies), [Makkiy](https://github.com/Makkiy), [mgt](mailto:i@margatroid.xyz), [minghu6](https://github.com/minghu6), [P-Y-Y](https://github.com/P-Y-Y), [PotassiumWings](https://github.com/PotassiumWings), [SamZhangQingChuan](https://github.com/SamZhangQingChuan), [sshwy](https://github.com/sshwy), [Suyun514](mailto:suyun514@qq.com), [weiyong1024](https://github.com/weiyong1024), [wjy-yy](https://github.com/wjy-yy), [GavinZhengOI](https://github.com/GavinZhengOI), [Gesrua](https://github.com/Gesrua), [iamtwz](https://github.com/iamtwz), [ksyx](https://github.com/ksyx), [kxccc](https://github.com/kxccc), [lychees](https://github.com/lychees), [Peanut-Tang](https://github.com/Peanut-Tang), [SukkaW](https://github.com/SukkaW), [Tiphereth-A](https://github.com/Tiphereth-A)
> __本页面的全部内容在**[CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/deed.zh) 和 [SATA](https://github.com/zTrix/sata-license)** 协议之条款下提供，附加条款亦可能应用