浅谈迭代加深

本篇随笔简单讲解一下算法竞赛中搜索算法中的迭代加深DFS。

为什么需要迭代加深

先来上发讲解图：

在学习迭代加深深搜之前，我们先简单回顾一下深搜。深搜的本质是对图的深度优先遍历。也就是“先往深了走，走完了没找到就换条路继续走”。对于那种无法一眼看出来是图论的问题，我们需要先把问题给定的条件抽象为一棵“搜索树”，然后在抽象出来的搜索树上进行深搜，解决问题。

假设上图就是我们针对某一个问题所抽象出来的搜索树。我们给定答案节点是4号节点。

那么，根据深搜的定义，我们进行算法的顺序是1-2-5-10-11-6-12-13-3-7-14-15-16-17-8-4-9.

我们发现，直到最后两步才找到4.

效率貌似很慢的样子。

为什么呢？

这是深搜本身的性质决定的，它的搜索顺序就是这样，这个算法不能“千变万化”，根据你问题的答案位置调整顺序，迭代加深也不行（你在想peach）。

如果你说，为什么不用广搜？

刚刚已经说过了，你设计的算法是成型投产的，你不可能针对一组数据，脑算出它的答案地点，然后再重新写程序吧？

所以，当我们设计出一款深搜程序，又不想因为被出题人特殊构造数据卡掉的时候，也许我们需要迭代加深。

迭代加深的过程，就是每次对搜索的深度进行一个限制，如果在当前限定下搜不到答案，就把深度限制增加，然后重新进行一次搜索。

比如，对于刚刚的搜索树。

假如限制是1，不行。

限制是2，搜到，结束。

假设答案是9号点的话，就再限制3，搜到，结束。

但是要提及的是，我们的搜索方式并不是扩展，而是迭代。

也就是说，限制是1，我们搜了1号点，没搜到答案。

限制换成2的时候，我们就需要重新从1号点开搜，因为如果变成在原有基础上扩展的话，就变成广搜了。虽然没必要，但是对不起，人家算法就是这么设计的，你学就得了。

所以，我们看得出来，这是一个低效率的算法，他的时间复杂度是呈指数级增长的。所以，它的试用条件是：

当搜索树非常深，但是我们能确定答案一定在浅层节点时，就可以使用迭代加深DFS。