当前课程知识点：人工智能 > 第二章 无信息搜索策略 > 2.1.3 树搜索算法 > Video
那么我们讲过问题形式化之后呢
给智能体智能体通过搜索算法去找到从当前状态
到达目标状态的一个动作序列
这么一个过程是一个搜索过程
这么一个过程我们可以形成一颗搜索树
也就是说所谓的树搜索算法就是我们让他从初始
状态出发不断的拓展
通过动作或者说是后续函数不断的拓展当前状态
产生一些后续状态
这样的一种探索搜索状态空间的一种方案，就会
形成一颗树
那么形成这么一颗树的一种搜索方案就叫做树搜
索算法
那么树搜索方案的基本思想就是通过产生已经探
索到的状态的后续状态的方法
来离线的进行状态空间的模拟搜索
那么大家可以看到这里面有几个基本的要素
一个就是，它是通过拓展已经产生的状态的后续
状态的方法
来进行状态空间的搜索
然后他还说了这里是离线
也就是说我们这里讲的搜索算法
这一部分这一章所讲的搜索算法都是离线
所谓离线就是它在问题形式化之后进行求解的这
个过程
它是与外部环境断开的，它不再接受外部环境的
感知
它只是根据当前感知得到的当前状态，然后根据
问题的形式化
去搜索这个到达目标状态的这么一个行动序列
那么搜索的这个过程是与环境脱离开来的
不再接受外部环境的感知
我们看到树搜索方法的框架，或者说它的思想、
它的伪代码是这样子的
它的输入是问题的形式化以及一个搜索策略
等一下我们会讲到这个搜索策略是什么概念
它返回的是这个问题的解也就是一个动作序列
或者是它觉得这个问题没解它返回一个失败
一开始它用问题形式化产生的初始状态来初始化
搜索树
我们这种方法为什么叫做树搜索方法
也就是说它的整个搜索过程会形成一个树结构
也就是一开始就是初始结点作为这颗搜索树的根
结点
然后作为它的根结点产生一个初始结点
然后就开始进行搜索循环
首先它看一下整个搜索树里面有没有结点还没有
拓展、还没有搜索、还没有探索
如果没有，又没有找到解，如果找到解肯定在某
个地方返回去了
也就是说又没找到解，又发现没有待拓展结点，
没有待探索结点
那就意味着整个空间他都探索完毕又没找到解
它就返回失败，就告知你这个问题没有解
否则的话呢，它就根据搜索策略去选择一个还没
有拓展的叶子结点进行拓展
所以这里的搜索策略的意思就是
如何在这么多还没有拓展的叶子结点里面去选择
一个优先进行拓展
所以这里的策略指的就是这种选择方案
那么把这个选出来准备进行拓展的结点选出来之
后呢
首先判断这个结点是不是目标状态
也就是说他是不是一个目标状态产生的节点，是
不是包含一个目标状态
也就是说是不是到达了目标结点
如果是的话那就证明它找到了解
所以它就把这个解返回去
也就是说这个解当然我们指的是这个动作序列
从初始状态到达这个目标状态整个的过程返回给
你
否则的话他把这个挑选出来的结点进行拓展
也就是说这个选出来的结点不是目标结点就对它
进行拓展
怎么拓展呢？
也就是说利用我们的动作、后续函数来产生一些
新的状态，产生新的后续结点
然后把这些新的产生出来的后续结点加到这颗搜
索树里面
也就是说这些新产生的后续结点作为叶子结点
那么当前这个结点就变成这些结点的父亲结点
所以整个搜索过程就形成了一颗搜索树
所以这是一个通用的一般的树搜索的伪代码
所以呢这里不同的搜索算法关键就在于搜索策略
也就是说我们应该怎么样来选择优先探索哪一些
结点
就相当于我们在整个搜索空间里面，应该先选择
哪一条路进行试探
那么这里面就会导致不同的效率不同的效果
那么比如说像我们的罗马尼亚问题的树搜索过程
首先智能体在Arad这个城镇
根据地图Arad可以到达Sibiu、Timisoara、Zerind
那么它通过对初始结点、这个待拓展结点
也就是说这个节点目前还没有拓展，也就是说这
是一个待拓展结点
进行拓展，也就是说它可以开到图中三个地方
来形成三个新的后续结点
所以他就能形成三个新的后续结点
那么这个结点已经变灰了，意思就是这个结点已
经拓展过了
已经走过了知道它不是目标状态
现在产生了三个新的状态，这三个状态是待拓展
结点
那么我们刚才看到了在这些待拓展结点里面
你要根据我们的搜索策略来选择一个进行拓展
那么假设我们的搜索策略选择它来进行拓展
那么在选择它进行拓展之前呢我们先判断一下它
是不是目标状态
那么发现它不是目标状态，那么对它进行拓展
也就是说发现它可以到达Arad等四个地方
形成四个新的状态形成四个新的结点
现在我们的这个结点就已经拓展过了，也就是我
们知道它不是目标状态，已经探索过了
现在呢有六个叶子结点
也就是这个六个叶子结点就是我们的待拓展结点
那么这六个叶子结点我们应该优先选择哪个进行
探索呢，进行拓展呢
这也是我们的搜索策略决定的
那么假设对Arad进行探索，它又可以生成新的后
续状态
那么整个这个过程就形成了一颗搜索树
-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卡尔曼滤波器
-结课测试
