当前课程知识点：人工智能 > 第二章 无信息搜索策略 > 2.2.1搜索策略 > Video
我们看到这个树搜索方法，它里面非常重要的一
个部分就是这个搜索策略
也就是说应该如何来选择待拓展的结点进行拓展
这个非常非常重要，决定了这个搜索算法的效率
也就是说如果你选择了一条路，这条路上都没有
解，你可能都回不来
或者说你能够有一种很好的搜索策略
优先探索的是这样一条路，这条路上有一个最优
解
你能够迅速的找到，那么就可以节约很多的时间
所以呢这个搜索策略指的就是这个结点拓展顺序
的选择
也就是说在实现的时候这个fringe表应该如何排序
这个就是搜索策略
那么一个搜索策略或者一种不同的搜索算法
搜索策略决定的不同的搜索算法可以由四个方面
来评估它的性能好坏
第一个方面就是完备性
完备性的概念就是我这个问题是有解的，你能不
能找到解
也就是说有解的时候一定能够找到解
这就是完备性的定义
如果有解的时候有可能找不到解 就不具备完备性
那么第二个方面就是时间的复杂性
时间复杂性直观上就是这个算法要运行多长时间
才能把这个解找出来
那么我们如何分析搜索策略、搜索算法的时间复
杂性的时候呢
分析的是它整个搜索过程产生了多少个结点
也就是说这个搜索树里面产生了多少个结点才找
到解
因为一找到这个解就不再产生新的结点
那么其实上产生的结点个数就决定了要花多长时
间来找到这个解
所以用产生的结点个数来评估搜索策略的一个方
面的指标
另外一个方面就是我们的空间复杂性
空间复杂性指的是到底要占据多大的内存
要在数学上严格定义它就是整个搜索过程中
存储在内存里的最大结点个数
比如说 有的时候产生出来的结点用完了可能会丢
出去
但是整个搜索过程里面 存储在内存里面的最多 多
少个结点个数
用这个来评估空间复杂度
也就是说需要存储的结点个数很多
你的计算机满足不了，那么这个算法是没有办法
运行
最后一个度量指标就是最优性
所谓的最优性就是这个算法能不能找到一个代价
最小的解
代价我们前面讲了，问题的形式化里面就有路径
的代价
我们在树搜索框架里面也看到
在产生新的结点的时候我们都要计算从初始状态
到达这个状态它的代价是多少
所以呢找到解的时候 这个解的代价你也是知道的
在这个状态空间里面可能有很多的解
你能不能找到一个最好的解，也就是代价最小的
解
也就是它执行的动作最少，步骤最少
能不能找到这么一个解
能找到，则这个搜索算法（搜索策略）就具有最
优性，否则就不具备最优性
我们的时间和空间复杂度呢
我们要计算
也就是说我们要去评估它到底产生多少个结点个
数
到底存储多少个结点个数
这个数量是根据下面三个量来表达的
第一个量就是b，这个b的意思就是分支数
分支数的意思就是
大家看到这个是一棵搜索树
这个树的话就像我们自然界的树一样
分支数就是指分出去多少个支
那么这棵搜索树有的分支点可能分出三个儿子结
点
有的分支结点可能分出一个，像g就分出一个
但是这里的b这个参数（变量）指的就是
这棵搜索树最大的分支个数
像这棵搜索树最大的分支个数就是2
有的分支是分出1支有的分出2支
所以最大分支数是2，所以b=2
然后还有一个量就是d
d是用来表达最优解（最小代价解）所在的深度
一般来说如果我们认为每一步的单步代价都相同
的话
那么最优解就是在最浅层
也就是说最浅层的，最优的这个解
所在的层数，所在的深度
假设a、d、f、j是几个解
那么这里d这个解是最优，最浅层的这个解
所以在这里d=2
这个b是branch这个单词的首字母
这个d是depth单词的首字母
那么这个m是用来表示整个状态空间的最大深度
状态空间如果是无穷，那么这个深度可能是无穷
大
所以这个m有可能是无穷大的
所以后面我们在分析不同搜索策略的性能指标时
在谈到他们的时间和空间复杂度的时候
我们会用b、d、m这三个量
来表达它们的空间和时间复杂度
所以我们首先来看一下盲目搜索策略
那么盲目搜索策略 什么叫盲目
或者说无信息的搜索策略
也就是说这种搜索策略仅仅是运用了问题定义中
的信息
它没有其他信息，只是通过问题的形式化获得了
一些信息
用这些信息来进行搜索，进行排队
那么这种盲目搜索策略我们要讲到
宽度优先搜索、一致代价搜索、深度优先搜索、
深度优先搜索、迭代深度搜索（迭代深入搜索）
这五种盲目搜索策略
-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卡尔曼滤波器
-结课测试
