当前课程知识点：人工智能 > 第二章 无信息搜索策略 > 2.3.4迭代深入深度搜索性能分析 > 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个结点
所以它的空间复杂度就是一个线性的空间复杂度
那么最优性也是能够保证的
也就是说因为它是一层一层的搜索下来
所以它一定能把最浅层的这个解找回来返回给你
当然这里如果你这里单步代价不相等话
最浅层的解不一定最优，那么有可能你找到的解
不是最优的解
只要你是单步单价相等，那么最浅层的解也就是
最优解
那么它就能够保证找到最优解给你
这个是迭代深入搜索的四个性能指标
所以可以看得出来它是很有优越性的，完备性也
有
空间复制度又是一个线性的，又能保证最优性
时间复杂度也没有比别人更高
所以这个是盲目搜索策略里综合性能指标比较好
的一个搜索策略
-1.1 人工智能概念
-第一章 绪论--1.1 人工智能概念
-1.2 什么是理性智能体
--1.2理性智能体
-第一章 绪论--1.2 什么是理性智能体
-2.1.1问题求解智能体
-第二章 无信息搜索策略--2.1.1问题求解智能体
-2.1.2问题形式化
--Video
-2.1.3 树搜索算法
--Video
-第二章 无信息搜索策略--2.1.2问题形式化
-2.1.4树搜索算法的实现
--Video
-2.2.1搜索策略
--Video
-第二章 无信息搜索策略--2.1.3树搜索算法
-2.2.2宽度优先搜索
--Video
-2.2.3一致代价搜索
--Video
-第二章 无信息搜索策略--2.1.4树搜索算法的实现
-2.3.1深度优先搜索
--Video
-2.3.2有限深度搜索
--Video
-2.3.3迭代深入搜索
--Video
-第二章 无信息搜索策略--2.2.2宽度优先搜索
-2.3.4迭代深入深度搜索性能分析
--Video
-2.4无信息搜索策略小结
--Video
-第二章 无信息搜索策略--2.2.3一致代价搜索
-第二章 无信息搜索策略--2.3.1深度优先搜索
-第二章 无信息搜索策略--2.3.2有限深度搜索
-第二章 无信息搜索策略--2.3.3迭代深入搜索
-第二章 无信息搜索策略--2.3.4迭代深入深度搜索性能分析
-第二章 无信息搜索策略--2.4无信息搜索策略小结
-3.1贪婪搜索算法
--Video
-3.2.1A星搜索算法
--Video
-第三章 有信息搜索策略--3.2.1A星搜索算法
-3.2.2A星搜索算法的最优性
--Video
-3.2.3可采纳的启发式函数
--Video
-第三章 有信息搜索策略--3.2.2A星搜索算法的最优性
-3.3爬山搜索算法
--Video
-3.4模拟退火搜索算法
--Video
-第三章 有信息搜索策略--3.2.3可采纳的启发式函数
-3.5遗传算法
--Video
-第三章 有信息搜索策略--3.3爬山搜索算法
-第三章 有信息搜索策略--3.5遗传算法
-4.1.1什么是约束满足问题
--Video
-第四章 约束满足问题--4.1.1什么是约束满足问
-4.1.2约束满足问题的标准搜索形式化
--Video
-4.2.1回溯搜索算法
--Video
-第四章 约束满足问题--4.1.2约束满足问题的标准搜索形式化
-4.2.2回溯搜索的变量赋值顺序策略
--Video
-4.2.3回溯搜索的前向检查及约束传播
--Video
-第四章 约束满足问题--4.2.1回溯搜索算法
-4.2.4 AC-3弧相容算法
--Video
-4.3约束满足问题的局部搜索方法
--Video
-第四章 约束满足问题--4.2.2回溯搜索的变量赋值顺序策略
-第四章 约束满足问题--4.2.3回溯搜索的前向检
-第四章 约束满足问题--4.3约束满足问题的局部搜索方法
-5.1博弈及极小极大值概念
--Video
-5.2极小极大值决策算法
--Video
-第五章 对抗搜索--5.2极小极大值决策算法
-5.3.1剪枝的概念
--Video
-5.3.2 alpha-beta算法
--Video
-5.3.3 alpha-beta剪枝示例
--Video
-5.4 不完美的实时决策
--Video
-第五章 对抗搜索--5.3.3 alpha-beta剪枝示例
-第五章 对抗搜索--5.4 不完美的实时决策
-6.1不确定性量化
--Video
-第六章 不确定性推理--6.1不确定性量化
-6.2使用完全联合分布进行推理
--Video
-6.3贝叶斯规则及其应用
--Video
-6.4贝叶斯网络推理
--Video
-第六章 不确定性推理--6.2使用完全联合分布进行推理
-6.5隐马尔可夫模型
--Video
-6.6卡尔曼滤波器
--6.6
-第六章 不确定性推理--6.4贝叶斯网络推理
-第六章 不确定性推理--6.3贝叶斯规则及其应用
-第六章 不确定性推理--6.6卡尔曼滤波器
-结课测试
