当前课程知识点：人工智能 > 第五章 对抗搜索 > 5.3.3 alpha-beta剪枝示例 > Video
接下来看一下这个例子
就是我们看一下在Max-value函数中发生剪枝的一
个示例
那么大家看一下就像这里一样
那么这里的话比如说我们的搜索已经进行到了这
一步
那么这一步的话这个max结点在这里
它的父亲结点就是min 然后这三个结点就是终止状
态的
所以呢这里面的这个选择结点
也就是说有分支的结点就是像 这种结点 这种结点
那么这些结点是没有分支的
那么大家看一下像这种max结点的话
那么它三个儿子2、5、3 那么它取最大值等于5的
那么对于min来讲呢 那么它发现有一条路径它可以
得五分
也就是说它可以得5分就是因为这个儿子给了它5
分
所以这个时候我们的β就等于5
也就是说到目前为止它找到了一条路
可以 也就是min找到了一条路 最好的路
这个值可以给它5分 所以β等于5
然后它就开始去看 min看它的第二条路
然后它就开始去看 min看它的第二条路
第二条路呢
那么要去算max的分值
所以它去计算第二个儿子的分值的时候调用的肯
定是这个Max-value
因为第二个儿子是这个max结点嘛
所以我们来看一下针对这个结点调用Max-value的
时候就会发生剪枝
大家看一下哈 这个max结点函数调用的时候
大家都知道它要去遍历它的这个儿子
所以它首先看到第一个儿子等于6
所以这个时候我们的v是等于6的是吧 没有错吧 这
个max结点等于6
那么它就会第二条语句就会去判断一下
这个6是不是比我们的β要更什么 要更大是不是啊
也就是说这个6呢会比我们的β要更大
那么这个意味着什么啊 因为这个max是取它儿子
结点里面的最大值
那么你已经有一个儿子给了我6
那么也就意味着什么啊 意味着这个max将来的值
肯定是大于等于6的
那么这个大于等于6 那么对于min来讲
那么也就意味着我选这个儿子将来的分比我选这
个儿子更差
那么他压根就不会走这条路的
所以呢这个max分支就可以全部剪掉
也就是说剩下的这些指针呢 我压根就
剩下的这两个儿子呢压根就不用去访问 直接给它
擦掉 剪掉
直接把6返回去作为这个max结点的分值
因为这个6不起作用所以这个准不准确没有关系
它只是起到一个剪枝的作用 所以把这两个分支都
剪掉了
所以这个就是在Max-value中发生剪枝的一个例子
所以呢在考虑剪枝的时候你要从它的父亲结点这
一层去理解这个Max-value的剪枝
那么这个是这个Max-value的剪枝
那么我们来看一下这个β的更新它是什么意思
也就是说它在这里的时候呢
它对于min来讲 它第一个儿子它发现是5
那么第二个儿子返回来是6 那么6比5更大
所以它这个β没有更新的 那么再看第三个儿子
那么第三个儿子的话 那么大家看到这里
也就是说第三个儿子max结点它是3、4、4里面取
4
那么第三个儿子得到4
它发现第三个儿子的值比我原来存储的β=5要更小
那么就更好，所以我这个时候β就发生了更新了
所以β就等于四 这个是在这一层
就是为什么β的更新是在Min-value里面进行更新
也就是说它在计算Min-value的时候
它看一下它哪个儿子这个值比我的β要更小 它就更
新这个β
那么这个Max-value发生剪枝是在max调用的时候
它发生剪枝
他考虑的是它的父亲结点不会走我这个路
所以是这个意义上发生剪枝的
那么同样的道理我们来看一下Min-value函数中发
生剪枝的一个简单的例子
同样的道理我们这个时候我们的根结点是我们的
max结点
那么这个是一个min结点 这个是终止结点2、5、3
那么我们的min结点是取它的儿子结点里面的最小
值
所以这个min结点的分值是等于2的
那么等于二之后 这个max结点就知道我走这条路
可以得到两分
也就是说它到目前为止我的最好的选择就等于二
所以α等于2了它就记录下来了 第一个儿子
也就是说这是从max这一层来考虑这个α我已经算
出来第一个儿子等于2
所以它就α就等于2
然后呢他就开始搜索第二个儿子 去调用第二个儿
子
第二个儿子是这个 就调用这个Min-value这个函数
它在计算第二个儿子的时候 因为第二个儿子是
Min-value嘛
所以他就要去调用这个Min-value
这个时候我们来看一下Min-value
调用Min-value函数的时候它是怎样发生剪枝的
首先看到这个Min-value它计算它的第一个儿子的
分值等于1
那么这个时候这个v呢 这个Min-value呢
v呢就暂时是1了 那么这个1 它首先看一下这个1是
不是比我的α要更小
那么它一看这个1 比我的α更小就发生剪枝了 为什
么
因为我这个是一个min结点 min结点它是取它的儿
子的最小值
那么现在已经有一个儿子已经等于1了
那么意味着这个min结点将来的分值肯定是小于等
于1的
那么小于等于1 这个min结点小于等于1
那么它的这个max 它的父亲这个max
他已经有一天更好的路 2 它绝对不会去走这条路
这条路的分值会给它一条小于等于1的分值
所以呢这个条路压根对于我这个max的分值没有影
响
所以这条路就可以剪掉 整个这个分支就可以剪掉
所以它其他的儿子压根就不考虑了
就把这个1就返回去了
所以这个时候就发生了这个剪枝
这个就是min结点的剪枝
也就是在Min-value函数中发生的剪枝
就是把这个min结点就剪掉了
也就是说这个分支它的父亲是不会去考虑的
所以你要从这个角度去想 为什么在Min-value中发
生剪枝要和α进行比较
就这个意思 因为它的父亲是一个max结点
他不会走这条路 然后再看
对于这个max结点来讲它调用的是max函数
那max函数我们知道他要更新这个α
那么更新α 它首先第一条路α等于二
第二条路都发生剪枝了 比它更差 它肯定不会更新
然后再看第三条路 那么第三条路的话大家看到它
的儿子是这个min
同样的道理去调用这个Min-value来计算
那么第一个儿子是3 所以它就临时等于3
3 不会发生剪枝 因为3比2大不是比它小
然后4也比2大 不会发生剪枝 但是它比当前这个v
要更大
因为我们的min结点是取最小的
然后呢再看这个4 所以最后呢这个是我们的这个
min结点取3、4、4里面的最小值 就等于3
那么等于3之后呢 返回去给这个max
也就是说它父亲结点要算的它
那么这个max返回去给它 它就发现它这个儿子可
以给它3分
而原来我的α才两分 所以它马上就更新这个α
就让α等于3 这个是对max结点来讲的
这个所以更新α呢是在Max-value里面更新的
因为它是在它的儿子里面 每一个儿子意味着一种
选择
它记录最好的选择 最好的路 它的分值
所以是这么一个意思 这个就是α-β剪枝算法
所以大家可以看得到这个α-β剪枝算法它其实是可
以节约很多的这个时间的
也就是它可以 如果在你这个分值排序 这个树的排
序排的非常完美的时候
它几乎可以减掉一半的结点 一半的搜索空间
所以呢这个是它的这个好处
所以我们最后来看一下这个α-β剪枝的这个属性 也
就是说它的这个性质
也就是说我们的α-β剪枝不会影响最后的计算结果
所以说它不会影响最后的决策的
因为我们前面也看到过 把这个要剪掉的这两个分
支
不管它是多少值x、y 都不会影响最后我的那个值
那么这个就是这个α-β剪枝它的这个效果呢
非常的这个 依赖于这个结点的顺序
如果你结点顺序摆放的好 它就能提高这个剪枝效
果
如果摆放的不好就不能提高
那么当这儿节点拓展有完美顺序是
就是意思就是说 所有能够剪掉的都能够剪掉的时
候呢
它的这个时间复杂度可以降低到这个
就是可以把这个指数 可以搜索的层次加深一倍
也就是说它的时间复杂度 可以这个指数呢减半
所以呢就你往前搜索往前看的步数可以增加一倍
将增加一倍
这个就是α-β剪枝的属性
那么这个为什么这个结点的顺序能够提高剪枝的
效果呢
那大家看到这个例子
来说明一下这个为什么这个结点的摆放顺序对这
个α-β的剪枝效果有影响
大家看到这里 首先这里的话 我们看到这里 就是说
这个是一个max结点 它有三个儿子 三个分支可以
选择
那么第一个儿子min结点给它了3分
那么这个时候 它的这个对max结点他已经记录下
来这个α就等于3了
也就是说它有一种选择 最好的选择 到当前为止就
是3分
然后呢它就开始计算它的第二个儿子的分值
那么第二个儿子呢首先这个min结点 它的第一个分
支给了它两分
那么就意味着第二个儿子的分值肯定是小于等于2
的
因为第二个儿子它是一个min结点嘛
他已经有一个儿子给了它两分
那么它要取最小值 它的分值肯定是小于等于2
那么一小于等于2的话 那么我们一看
我这个max的话 他已经有一条路可以给它3分
那么这条路的话给它的分数是小于等于2的
也就是说比我这个3分要更差
那么他肯定是不会 也就是说这个结点 这个分支的
值
到底是1分还是0.5分对它来说一点关系都没有
因为它不会选择这个分支 也就是说它一定是选择
这个分支的
也就是说它肯定不会选择这个分支因为他有一个
更好的选择
所以呢这个分支呢他就可以剪掉了
所以这两个就剪掉了 所以这个其他的它的值就是
无关紧要 我只要知道这个分支更差就行了
所以就剪掉了 然后再看第三个
第三个的话呢 大家看到这里 它的第三个儿子在这
里
第三个儿子呢 它首先第一个儿子给它14分 那么你
肯定不能发生剪枝
也就是说只能是说这个儿子的分值是小于等于14
那会不会比我这个3更大呢 那不一定的
那么再看第二个儿子 5 只能说它是小于等于5了
那也不一定会比我3大 然后再看第三个儿子是2
这个时候这个min结点取最小值等于2
那么这个我才知道原来这个分支只能得两分
也就是说才知道我应该选择这个分支
也就是说我的max得3分
那么所以说呢这个儿子就没有发生剪枝
但是如果你把这个2 这个结点摆在最左边来
也就是说这个2 摆到这里来 我就可以发生剪枝 和
它一样
如果我先遍历这个这个儿子 也就是说这个儿子摆
到最左边来
先搜索它 先计算它
那么第一个儿子一进来 等于2 那么我就立马知道
这个min结点最后给我的分支是小于等于2的
那么我肯定不会选择这条路了 这个max
因为这个儿子小于等于2 所以它就可以把这两个分
支给剪掉
但是由于你把14、5摆在前面它就没有剪掉
一直到它的所有儿子都遍历完了我才知道这条路
根本就没有用
所以呢这个就是这个节点的顺序对于这个α-β剪枝
的效果有非常重要的影响
所以我们说 刚才说的是 如果结点摆放的非常完美
就是所有能够剪的支都剪掉了
那么我们的α-β剪枝它的时间复杂度呢
可以将那个指数减半 就是这么一个意思
-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卡尔曼滤波器
-结课测试
