Video在线视频

那么我们可以看得出来 这个迭代深入搜索

好像这些浅层的结点都进行了重复的搜索 重复的
产生

感觉好像会浪费很多的时间

那么我们来比较一下这个深度有限搜索

和迭代深入搜索产生的结点到底差别有多大

那么假设我们的最优解在第d层

也就是最浅层的解就在第d层

那么假设你事先知道最浅层的解就在第d层

那么你用一次深度有限搜索把深度限制设成d

就可以恰到好处的把这个解找出来

那么这种情况下我们的深度有限搜索产生的结点
个数就是

第0层 b的0次方个结点，第1层b的1次方

第2层b的2次方,一直到第d层第b的d次方

这么多个结点个数

那么对于我们的迭代深入搜索

我们知道我们的for循环是执行了d加1次

也就是说它要从深度限制设为零开始不断地循环
下去

不断地调用我们的深度有限搜索 进行搜索

一直到深度限制设为d的时候 这个深度有限搜索

才能把这个最浅层的解找出来，这个for循环才能
结束

所以总共的for循环要执行d+1次

那么执行d+1次我们可以看得到

从第零层，一直到深度限制设为到第d层

我们的第零层的结点全部要进行搜索

所以它总共重复搜索了d+1次

那么对一第一层的结点呢？

当深度限制设为1，一直到深度限制设为d

这d次循环它都要拓展第一层的结点

所以它总共重复拓展（产生）了d次

对于第二层的结点

它从深度限制为2 一直到深度限制为d

它总共重复拓展了d-1次

所以我们可以看得出来，像我们深度限制为0的时
候

我们第零层的结点拓展了一次

然后深度限制为一的时候第零层的结点拓展了两
次

第一层的结点拓展了一次

深度限制为二的时候，第零层的结点已经拓展了
三次

然后第一层的结点拓展了两次

然后第二层的结点拓展了一次

深度限制为三的时候，我们第零层的结点已经拓
展了四次

然后第一层拓展了三次

第二层拓展了两次，第三层拓展了一次

所以可以看得出来，第零层就是重复拓展了d+1次

第一层重复拓展了d次

依此类推到d-2层它重复拓展了三次

d-1层重复拓展了两次，第d层只拓展了1次

所以他迭代深入搜索产生的结点个数是这么一个
式子

那么这两个之间的差别到底有多大呢

其实上并不会相差很大

因为它重复次数多的是浅层的结点

而这个浅层的结点个数是比较少的

看一个具体的实例来比较一下迭代深入搜索

是不是在时间的消耗上会比深度有限搜索多很多
呢？

或者到底是一个怎么样的超出比率呢

也就是说对于一个分支数b=10

最优解所在深度等于5的这么一个问题的规模

我们的深度有限搜索产生的结点个数是这么一个
情况，就是

b的0次方、b的1次方、b的2次方、b的3次方、b
的4次方、b的5次方

那么加起来就是等于这么一个数量

我们的迭代深入搜索它是

5+1就是6， 6*1，然后这里就是5*10

这是4*100 这是3*1000 这个是2*10000 然后这是
1*100000

然后加起来就是等于这么一个数量级

那么我们来看一下它比它超出了多少呢

我们算一下这个比率，这个超出比率是11%

所以这个并不会多出一个数量级，也没有翻倍

只是多了一个11%的一个时间上的消耗

但是它带来的好处就是

由于使用的是迭代深入搜索

它能够保证找到一个最优解

因为它宏观上是一层一层加深的

并且虽然它额外的让这些浅层的结点重复的进行
搜索

但是它可以大大地节省存储空间

相比于宽度优先搜索

它（宽度优先搜索）虽然不重复搜索浅层的结点

但是它（宽度优先搜索）把这些结点全部存储在
那里

使得空间复杂度非常的高

那么我们迭代深入搜索通过重复搜索浅层的结点

来实现不断的释放空间的目的，从而达到一个线
性存储空间的性能

所以这个是它的一个好处

那么来看一下迭代深入搜索的性质（属性）

就是它的四个性能度量指标

首先看到它的完备性

有解它是不是能保证找到解

那么我们前面也讲过它是有这个能力的

因为在宏观上面它是一层一层往下搜索的

通过深度限制来限制它一直一直往下搜索

所以它肯定是不允许它那哪条路一直走下去不回
来

所以它只要这个有解，那么这个解肯定在某一层

它随着限制的加深它一定会搜索到这一层

把这个解找出来，所以它能保证完备性

那么时间复杂度的话，他就是这么一个复杂度

就是它的最高数量级也就是b的d次方

比你的宽度优先搜索还要更低一点

那么我们在看一下它的空间复杂度

因为我们知道它的实现主体是深度有限搜索

也就是说它每一次实现是由深度有限搜索来实现
的

所以它任何时候只储存一条路径上的结点

只要它一旦发现哪条路径，它就会抛出去

所以浅层的结点才会重复搜索

那么它存储的最大结点的时候呢

就是当for循环设为d的时候

也就是这个最浅层的解所在的这一层的时候

那么它存储的就是从第零层到第d层的这个一个

深度为d的这么一条路径上的结点个数

那么就是b乘d个结点

所以它的空间复杂度就是一个线性的空间复杂度

那么最优性也是能够保证的

也就是说因为它是一层一层的搜索下来

所以它一定能把最浅层的这个解找回来返回给你

当然这里如果你这里单步代价不相等话

最浅层的解不一定最优，那么有可能你找到的解
不是最优的解

只要你是单步单价相等，那么最浅层的解也就是
最优解

那么它就能够保证找到最优解给你

这个是迭代深入搜索的四个性能指标

所以可以看得出来它是很有优越性的，完备性也
有

空间复制度又是一个线性的，又能保证最优性

时间复杂度也没有比别人更高

所以这个是盲目搜索策略里综合性能指标比较好
的一个搜索策略