【搜索】【模板】 IDDFS

IDDFS

使用场景

1. 使用 dfs 由于状态量太大会 TLE, bfs 会 MLE。
2. 答案必须很小，一般在 20 以内。

算法原理

1. 设置 dfs 的搜索深度限制 \(dep\)，dfs 穷举 \(dep\) 层的答案。
2. 若在 \(dep\) 层找到满足条件的情形，则 \(dep\) 则为答案，否则 \(dep \leftarrow dep + 1\), 继续搜索。

优点与缺点

1. 优点：每次严格搜索第 \(dep\) 层的状态，从而使总状态量有限，避免 TLE 和 MLE；
2. 缺点：每次都要从搜索树的根节点开始，即前 \(dep - 1\) 层的状态都是重复的，但是我们宁愿重复走，也不愿意继续往下拓宽一层。

IDDFS 的剪枝技巧

1. 可行性剪枝——通常围绕贪心设计；
2. 调整搜索顺序；
3. 排除重复状态；