当前课程知识点：人工智能 > 第二章 无信息搜索策略 > 2.2.3一致代价搜索 > Video
那么我们来讲一致代价搜索策略这种盲目搜索策
略
那么这种盲目搜素策略，是优先拓展具有最小代
价的待拓展结点
也就是说它的fringe是根据结点代价进行排序的
也就是从初始结点到达这个结点的路径代价小的
排在前面，优先进行拓展
那么如果是单步代价相等的时候
也就是说它每一次做一个动作代价都相等的时候
那么这种排序策略（搜索策略）和我们的宽度优
先搜索策略是一样的
也就是说浅层结点的代价要比深层结点的代价要
低
所以浅层结点肯定排在前面
所以就和宽度优先搜索是一样的
那么当单步代价不相等的时候
比如说真空吸尘器向左移动产生一个结点
向左移动的代价我定义它是二
向右移动我定义它的代价是一，产生一个结点
那么这两个结点的代价就不一样
尽管它们在同一层 有可能和宽度优先搜索的顺序
是不一样的
或者说它再往下走有可能第二层结点的代价比第
三层结点的代价还要更大
那么它可能就和宽度优先搜索的顺序是不一样的
那么这种按照代价排序的搜索策略的四个指标是
怎样的呢
首先看到完备性
一致代价搜索在有解的时候能不能保证找到解呢
一般情况下认为它是有完备性的
也就是说只要你的单步代价不是无穷小 不等于零
也就是说随着搜索的进行
随着结点深度慢慢的加深
那么这个结点的代价是会越来越大的
因为它每一步的代价都是一个正数
那么累加下去，结点的代价会慢慢增加
我们的解总有排在最前面的时候
所以总会有轮到它的时候，所以就保证能找到一
个解
但是如果存在单步代价等于零的这么一个搜索树
的话
那么有可能有有无穷个结点的代价都比这个解的
代价小
所以总轮不到这个解出来
所以这种情况下就没有完备性
但是在实际当中单步代价都是大于等于一个正数
的值
所以认为它是具有完备性的
那么来看一下一致代价搜索的时间复杂度
那么一致代价搜索是按照代价排序进行拓展的
所以它是取决于单步代价
也就是说随着搜索的进行，哪些结点会拓展出来
完全取决于这个单步代价，所以这里只能估计出
一个很宽松的上限值
那么我们假设最优解的代价是c*
那么最优解所在的深度最大上限值就是这么一个
值
也就是c*/ε 这里的ε指的是最小单步代价值
c*/ε也就意味着从初始状态到最优解每一步都是最
小值
所以这个估计的就是最优解所在的深度的最大上
限值
这个ceiling表示向上取整
那么在这种极端情况下
也就意味着在找到c*这个最优解之前
所有比他代价更小的结点都拓展出来了
而所有比它代价更小的结点都会位于这个深度的
上方
为什么呢?因为我们估计的都是一个最深的深度
就是认为每一步的单步代价都是最小值
那么其它结点，它单步代价只可能比这个
所以任何比c*更小代价的结点一定是位于这个深
度的上方
那么在极端情况下，在搜索到c*这一层的时候
比c*更小的结点个数最多就是b的ceiling（c*/ε）次
方
想这个估计的就是所有单步代价都是ε
所以在搜索到这一层的时候
它就是搜索了b的d次方这个一个数量级的结点个
数
这个就是我们的一致代价搜索的时间复杂度
这个时间复杂度给出的是一个非常宽松的上限值
那么它的空间复杂度和我们的宽度优先搜索是一
样的
也就是说在找到解之前它不能抛弃任何一个结点
因为它不知道哪一个结点下面有解
所以他要保存所有产生的结点
所以它的空间复杂度和时间复杂度是一样的
也是指数级的
那么我们再看它有没有最优性
也就是说它找到的这个解是不是最优解
这个它是能够保证的
因为我们fringe表里的结点是按照代价排序的
那么当然代价小的解是排在前面的
那么优先找到代价小的解，把它返回去
所以它能够保证最优性
所以这个是我们的一致代价搜索策略
那么这个的话和我们的宽度优先搜索比较相似
它就适用于单步代价不相等的情况下
当然如果单步代价非常小的话这两个复杂度也是
非常高的
-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卡尔曼滤波器
-结课测试
