迭代深入深度优先搜索

3.4.5 迭代深入深度优先搜索

迭代深入搜索（或迭代深入深度优先搜索）是一个用来寻找最合适的深度限制的通用策略，它经常和深度优先搜索结合使用。它的做法是不断地增大深度限制——首先为0，接着为1，然后为2，依此类推——直到找到目标节点。当深度限制达到d，即最浅的目标节点的深度时，就能找到目标节点。图3.14给出了这个算法。迭代深入搜索算法结合了深度优先搜索和广度优先搜索的优点。它的空间需求和深度优先搜索一样小，为 O(bd)。它和广度优先搜索一样当分支因子有限时是完备的，当路径耗散是节点深度的非递增函数时则是最优的。图3.15表示了在一个二叉搜索树上ITERATIVE-DEEPENING-SEARCH函数4次迭代的情况，在第4次迭代时找到了解。

图 3.14 迭代深入搜索算法，它反复应用逐渐增加限制值的深度有限搜索。找到解，或者深度有限搜索返回 failure （失败）说明找不到解时，则算法终止

迭代深入搜索也许看起来比较浪费，因为有些状态被多次生成。但事实上其代价不是很大。原因是在一棵每层的分支因子都有相同（或者近似相同）的搜索树中，绝大多数的节点都在底层，所以上层的节点生成多次影响不是很大。在迭代深入搜索中，底层（深度 d）节点只被生成一次，倒数第二层的节点被生成两次，依此类推，一直到根节点的子节点，它被生成d次。因此，生成节点的总次数为

N(IDS)=(d)b+(d−1)b2+…+(1)bd，

它的时间复杂度是O(bd)。我们可以与广度优先搜索生成节点的次数比较一下：

N(BFS)=b+b2+…+bd＋ (bd+1−b)

注意广度优先搜索生成了一些第d+1层的节点，然而迭代深入搜索不会如此。结果是尽管迭代深入搜索重复生成了一些状态，但是它确实还是比广度优先搜索更快。例如，如果b = 10，d = 5，它们生成节点的次数分别为：

N(IDS)=50+400+3 000+20 000+100 000=123 450

N(BFS) = 10+100+1 000+10 000 ＋ 100 000+999 990 = 1 111 110

一般来讲，当搜索空间很大而且解的深度未知时，迭代深入搜索是一个首选的无信息搜索方法。

图3.15 迭代深入搜索在一棵二叉树上的4次迭代

迭代深入搜索和广度优先搜索是类似的，在每次迭代进行到下一层之前要把整个当前层的新节点全都探索过。发展类似于代价一致搜索的迭代搜索看来是值得的，在继承代价一致搜索的最优化保证的同时避免了大量的内存需求。主要思想是用不断增加的路径耗散限制代替不断增加的深度限制。按照这种思想产生的算法被称为迭代延长搜索，将在习题3.11中探索。不幸的是，与代价一致搜索相比，事实上迭代延长将导致实在的额外开销。