对于深度d比较大的情况，深度优先搜索需要很长的运行时间，而且还可能得不到解答。一种比较好的问题求解方法是对搜索树的深度进行控制，即有界深度优先搜索方法。有界深度优先搜索过程总体上按深度优先搜索方法进行，但对搜索深度需要给出一个深度限制dm，当深度达到dm时，如果还没有找到解答，就停止对该分支的搜索，转到另外一个分支进行搜索。
对于有界深度搜索策略，有下面几点需要说明：
（1）在有界深度搜索算法中，深度限制dm是一个很重要的参数。当问题有解，且解的路径长度小于或等于dm时，搜索过程一定能够找到解，但是和深度优先搜索一样，这并不能保证最先找到的是最优解，即这时有界深度搜索是完备的，但不是最优的。但是当dm取得太小，解的路径长度大于dm时，则搜索过程就找不到解，即这时搜索过程甚至是不完备的。
（2）深度限制dm不能太大。当dm太大时，搜索过程会产生过多的无用节点，既浪费了计算机资源，又降低了搜索效率。有界深度搜索的时间和空间复杂度和深度优先搜索类似，空间是线性复杂度，为0（bdm），时间是指数复杂度，为O（bdm）。
（3）有界深度搜索的主要问题是深度限制值dm的选取。该值也被称为状态空间的直径，如果该值设置得比较合适，则会得到比较有效的有界深度搜索。但是对于很多问题，我们并不知道该值到底为多少，直到该问题求解完成，才可以确定出深度限制dm。为了解决上述问题，可采用如下的改进方法：先任意给定一个较小的数作为dm，然后按有界深度算法搜索，若在此深度限制内找到了解，则算法结束；如在此限制内没有找到问题的解，则增大深度限制dm，继续搜索。这就是迭代加深搜索的基本思想。
迭代加深搜索是一种回避选择最优深度限制问题的策略，它是试图尝试所有可能的深度限制：首先深度为0，然后深度为1，然后为2，如此一直进行下去。如果初始深度为0，则该算法只生成根节点，并检测它。如果根节点不是目标，则深度加1，通过典型的深度优先搜索算法，生成深度为1的树。同样，当深度限制为m时，树的深度也为m。
迭代加深搜索看起来会很浪费资源，因为很多节点都可能要扩展多次。然而，对于很多问题，这种多次的扩展负担实际上很小。可以想象，如果一棵树的分支系数很大，几乎所有的节点都在最底层上，则对于上面各层节点扩展多次对整个系统来说影响不是很大。我们知道，搜索深度为h时，由深度优先搜索方法生成的节点数为：
由迭代加深搜索过程中的失败搜索所产生的节点数量的总和为
该算法的最后一次搜索在深度d 找到了成功节点，则该次搜索的平均时间复杂度为典型的深度有限搜索：b （bd+d）/2（b -1）。则总的平均时间复杂度为
则迭代深度搜索和深度优先搜索的时间复杂度的比率为
对于比较大的d，上式可简化为
迭代深度搜索和宽度优先搜索的时间复杂度的比率为
对于一个分支系数b=10的深度目标，迭代深度搜索比深度优先搜索增加20%左右的节点，而只比宽度优先搜索增加了11%左右的额外节点。而且，分支系数越大，重复搜索所产生的额外节点比率越少。因此，迭代加深搜索和深度优先搜索方法以及宽度优先搜索方法相比并没有增加很多的时间复杂度。即迭代加深搜索的时间复杂度为O（bd），空间复杂度为O（bd），它既满足深度优先搜索的线性存储要求，同时又能保证发现最小深度的目标。
算法5.3 迭代加深搜索算法
Procedure Iterative Deepening
Begin(www.xing528.com)
（1）设置当前深度限制＝1。
（2）把初始节点压入栈，并设置战顶指针。
（3）While棋不空并且深度在给定的深度限制之内
Begin
弹出栈顶元素；
IF栈顶元素＝goal，返回并结束；
Else以任意的顺序把楼顶元素的子女压入栈中；
End
End while
（4）深度限制加1，并返回2。
End.
宽度优先搜索、深度优先搜索和迭代加深搜索都可以用于生成和测试算法中。然而，宽度优先搜索需要指数级数量的空间，深度优先搜索的空间复杂度和最大搜索深度呈线性关系。迭代加深搜索对一棵深度受控的树采用深度优先的搜索。它结合了宽度优先和深度优先搜索的优点。和宽度优先搜索一样，它是最优的，也是完备的。但对空间要求和深度优先搜索一样适中。表5-3给出了宽度优先搜索、深度优先搜索、有界深度搜索和迭代加深搜索简单的比较。
表5-3 搜索策略的比较
注： b 是分支系数， d 是解答的深度， m 搜索树的最大深度，l是深度限制。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
