企业官网建设流程全解析

OI-wiki 迭代加深搜索（IDDFS）全解析：原理、复杂度与实战应用

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

迭代加深搜索（Iterative Deepening Depth-First Search，简称 IDDFS）是 OI-wiki 搜索专题中的一种基础而重要的最优解搜索策略。它以深度优先搜索（DFS）为内核，通过逐次放宽深度上限的方式逼近最优解，在保持 DFS 低空间开销的同时，获得类似 BFS 的最优性保证。读完本文，你将掌握迭代加深的定义、与 BFS/DFS 的关系、复杂度分析、标准流程与伪代码，并能够将其延伸应用到 IDA* 算法及埃及分数等经典问题中。

定义

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

它本质上是深度优先搜索，只不过在搜索的同时带上一个深度 $d$，当 $d$ 达到预先设定的深度上限时就返回，一般用于寻找最优解。如果一次搜索没有找到合法的解，就让设定的深度上限加一，重新从根结点开始搜索。

与朴素的 DFS 相比，迭代加深多了一个"深度上限"维度；与 BFS 相比，它又避免了维护大规模队列。可以说，迭代加深是介于 DFS 与 BFS 之间的一种折中策略。

核心思想：为什么不用 BFS？

既然迭代加深是为了找最优解，一个很自然的疑问是：为什么不用 BFS 呢？

答案在于空间复杂度。BFS 的基础是一个队列，队列需要保存当前层所有待扩展的状态，其空间复杂度非常大。当状态数量比较多，或者单个状态本身比较大（例如需要存储整个棋盘、整条路径）时，使用队列的 BFS 就会暴露出明显劣势。

事实上，迭代加深就类似于用 DFS 方式实现的 BFS，它每轮迭代都从根重新出发，只记录当前这一条递归路径上的状态，因此空间复杂度相对较小。两种算法在"按层逼近最优解"这一目标上是等价的，区别仅仅在于实现载体：

关于迭代加深在 OI-wiki 搜索体系中的定位，可结合 搜索算法总览 阅读：搜索即对状态空间进行枚举，通过穷尽所有可能来找到最优解或统计合法解个数，而迭代加深正是"按深度分层枚举"的一种优化手段。

复杂度分析：重复搜索的开销为何可以忽略

迭代加深有一个看似"浪费"的行为——每一轮迭代都要从根结点重新开始搜索，前面几轮的搜索结果似乎全部作废了。为什么这样的算法还能被接受？

关键在于：当搜索树的分支比较多时，每增加一层的搜索复杂度会出现指数级爆炸式增长，这时前面重复进行的部分所带来的复杂度几乎可以忽略。

设分支因子为 $b$，解所在深度为 $d$。第 $i$ 轮迭代（深度上限为 $i$）的展开结点数约为 $b^i$，于是迭代加深总的结点展开量约为

$$ b^0 + b^1 + b^2 + \cdots + b^d = \frac{b^{d+1}-1}{b-1}. $$

当 $b>1$ 时，这个和的渐进复杂度仍为 $O(b^d)$，与一次性 DFS 到深度 $d$ 的展开量同阶。换句话说，最后一轮迭代（真正找到解的那一轮）的展开量占绝对主导，前面所有轮次的重复工作加起来只相当于一个常数因子（约为 $b/(b-1)$ 倍）。当 $b$ 较大时，这个常数因子非常接近 $1$，重复搜索的开销自然可以忽略。

这也就是"迭代加深可以近似看成 BFS"的根本原因：两者在最坏情况下的结点展开量同阶，但迭代加深的空间消耗远小于 BFS。

算法过程与伪代码

迭代加深的完整过程如下：

1. 设定一个较小的深度作为全局变量$\textit{limit}$，然后执行 DFS；
2. 每进入一次 DFS，将当前深度加一，当发现当前深度 $d$大于设定的深度 $\textit{limit}$ 就返回（剪枝）；
3. 如果在搜索途中发现了答案，就可以回溯，同时在回溯的过程中记录路径；
4. 如果没有发现答案，就返回到函数入口，增加设定深度$\textit{limit}$，继续下一轮搜索，重复步骤 1~3。

OI-wiki 给出的伪代码如下：

IDDFS(u,d) if d>limit return else for each edge (u,v) IDDFS(v,d+1) return

伪代码中的核心是if d > limit这一行：它是深度剪枝的闸门，保证了每一轮搜索都不会越过当前深度上限，从而保证"这一轮没找到解"意味着"深度不超过 limit 的范围内不存在解"，进而推动 limit 单调递增地逼近真实解深度。

可运行的模板实现

将上述伪代码翻译成 C++，可以得到一个通用的迭代加深模板（示意实现，可在此基础上针对具体问题扩展目标判断与路径记录）：

#include <iostream> const int MAX_DEPTH = 100; // 深度上限的最大值 int limit; // 当前轮的深度限制（全局变量） int path[MAX_DEPTH]; // 记录当前路径，回溯时保留答案 bool is_target(int u); // 判断 u 是否为目标状态（按题目实现） void save_answer(int depth); // 保存当前 path[1..depth]（按题目实现） void next_states(int u, int out[]); // 枚举 u 的所有后继状态（按题目实现） bool dfs(int u, int d) { if (d > limit) return false; // 超过深度限制，立即返回 if (is_target(u)) { // 到达目标状态 save_answer(d); return true; } for (int v : next_states(u)) { path[d] = v; if (dfs(v, d + 1)) return true; // 找到答案即可回溯 } return false; } int main() { for (limit = 1; limit <= MAX_DEPTH; ++limit) // 逐轮放宽深度上限 if (dfs(start, 1)) break; return 0; }

模板中for (limit = 1; limit <= MAX_DEPTH; ++limit)体现了迭代加深"逐轮放宽"的外层循环，而dfs内层则以d > limit为剪枝条件，二者缺一不可。

注意事项与适用场景

OI-wiki 明确指出了一条重要的使用准则：

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

据此，可以总结出迭代加深的典型适用特征：

1. 问题要求最优解（如最小步数、最少项数），且解的深度未知或没有明显上界；
2. BFS 在空间上不可行：状态数量大、单个状态体积大，或队列会迅速膨胀（例如每层扩展量极大、甚至理论上无限）；
3. 深度剪枝收益高：DFS 天然适合利用深度进行剪枝，迭代加深把"深度限制"从固定值变成了可递增参数，剪枝力度可控。

反之，如果搜索树分支很小、深度很浅，或者需要频繁判重，BFS 通常是更直接的选择。迭代加深并非要取代 BFS，而是为"空间受限 + 求最优解"这一特定场景提供 DFS 化的替代方案。

此外，迭代加深还有一个实际约束需要留意：它每一轮都从头搜索，虽然渐进复杂度与 BFS 同阶，但常数因子更大。因此，只有当深度剪枝能够显著缩小每轮搜索范围时，它的优势才能真正发挥出来。关于 DFS 分层决策的基本范式（如何把问题分解为"层"、每层记录哪些状态变量），可参考 DFS（搜索算法）；关于 BFS 的队列判重机制，可参考 BFS（搜索算法） 以及图论章节中的 BFS（图论）、DFS（图论）。

从迭代加深到 IDA*：仓库中的延伸应用

迭代加深在 OI-wiki 中最直接、最重要的延伸，就是IDA* 算法（迭代加深 + A*），详见 IDA* 算法。

IDA* 是迭代加深搜索的一种变形：迭代加深在每次 DFS 中限制搜索深度，而 IDA* 则限制单次 DFS 的路径成本。在一次迭代中，算法从起点 $s$ 开始进行 DFS，记录到达当前结点 $x$ 的实际成本 $g(x)$，并利用它到终点的最小成本估计 $h(x)$ 进行剪枝：如果沿着当前路径到达终点的总成本估计

$$ f(x) = g(x) + h(x) $$

超过阈值 $C$，则停止对该分支的搜索。阈值 $C$ 在迭代间动态更新：初始阈值取为起点的总成本估计值 $h(s)$；每轮迭代中，每当因超过阈值而停止，就记录所有尚未访问的后继结点的总成本估计的最小值，迭代结束后将阈值更新为该最小值，继续下一轮搜索。

IDA* 继承了迭代加深的低空间开销，同时又引入了 A* 算法 的估价剪枝，因此具备两个明显优点：不需要判重、不需要排序，利于深度剪枝；空间需求减少。其代价则是重复搜索——即使前后两次搜索相差微小，每次放宽限制都要再次从头搜索。

经典例题：埃及分数

迭代加深 / IDA* 的一个经典应用是埃及分数问题：在古埃及，人们使用互不相同的单位分数（即 $1/a$，$a\in\mathbf{N}_+$）的和表示一切有理数。例如 $\dfrac{2}{3}=\dfrac{1}{2}+\dfrac{1}{6}$，但不允许 $\dfrac{2}{3}=\dfrac{1}{3}+\dfrac{1}{3}$（加数不能相同）。对于一个分数 $\dfrac{a}{b}$，规定：加数少的表示方法比加数多的好；加数个数相同时，最小的分数越大越好。例如 $\dfrac{19}{45}=\dfrac{1}{5}+\dfrac{1}{6}+\dfrac{1}{18}$ 是最佳方案。

这道题如果用回溯法求解，解答树会非常"恐怖"——深度没有明显上界，加数选择理论上无限，用 BFS 甚至连一层都扩展不完。这正是迭代加深的用武之地：从小到大枚举深度上限 $C$，每次搜索只考虑深度不超过 $C$ 的结点，只要解的深度有限，就一定能在有限时间内枚举到。

OI-wiki 在 IDA* 算法 页面给出了详细的解题思路与优化，其要点包括：

1. 深度上限用于剪枝：按分母递增顺序扩展，若前 $i$ 个分数之和为 $\dfrac{c}{d}$、第 $i$ 个分数为 $\dfrac{1}{e}$，则接下来至少还需要 $$ h = \left(\dfrac{a}{b}-\dfrac{c}{d}\right)/\left(\dfrac{1}{e+1}\right) $$ 个分数，总和才能达到 $\dfrac{a}{b}$。这里"至少"意味着估计是"乐观的"——和 A* 一样，好的估价函数必须不能高估实际成本。
2. 限制枚举起点：下一个分母至少为 $\left(\dfrac{a}{b}-\dfrac{c}{d}\right)^{-1}$，可改进枚举 $e$ 的起点。
3. 限制枚举上界：将路径成本限制变形为 $$ e \le \left(\dfrac{a}{b}-\dfrac{c}{d}\right)^{-1}(C-g) - 1, $$ 从而不必枚举所有后续分母，只需枚举到这个上界。
4. 最后两项直接解方程：搜索到最后两个分数时，通过求解二元二次方程组 $\begin{cases}x+y=kp,\xy=kq\end{cases}$ 判断是否可行，而非继续搜索。
5. 动态收紧上界：每次得到一组答案，都将分母上界调整到当前答案中最大分母减一。

仓库中提供了该题的完整参考实现 idastar_1.cpp，其核心结构与上述思路一一对应：

• 全局变量max_e（分母枚举上界，初始为1e7）、ans（最终答案）、current（当前搜索路径）；
• 递归函数dfs(int d, long long a, long long b, int e)中，a/b表示剩余待表示的分数 $\dfrac{a}{b}-\dfrac{c}{d}$，d表示剩余深度（对应 $C-g$），e是上一个分母；
• 当d == 2时，直接枚举 $k$（从4 * b / (a * a) + 1开始）求解二次方程，并检查判别式是否为完全平方数、解是否为整数（(a * k - t) % 2 != 0的检查保证 $x$ 为整数）；
• 找到答案后立即执行max_e = y - 1，实现"动态收紧上界"；
• 主函数solve(a, b)首先处理 $\dfrac{a}{b}$ 能直接写成单个单位分数（b % a == 0）的特殊情况，然后从lim = 2起逐轮加深，直到lim = 100。

上述代码与仓库中的测试数据 idastar_1.in、idastar_1.ans 配套，可用于验证实现的正确性。从源码结构看，这正是"迭代加深提供外层深度循环、估价剪枝提供内层搜索加速"这一思想的工程化落地。

关联页面

迭代加深在 OI-wiki 搜索体系中处于承上启下的位置，建议按以下顺序系统学习：

• 搜索算法总览：搜索专题入口与习题清单；
• DFS（搜索算法）：迭代加深的递归基础；
• BFS（搜索算法）：理解迭代加深为何能在空间上优于 BFS；
• A* 算法：IDDFS 加上估价函数后形成 IDA* 的前置知识；
• IDA* 算法：迭代加深的直接延伸，含埃及分数完整例题。

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki