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摆在前面它就没有剪掉

一直到它的所有儿子都遍历完了我才知道这条路
根本就没有用

所以呢这个就是这个节点的顺序对于这个α-β剪枝
的效果有非常重要的影响

所以我们说 刚才说的是 如果结点摆放的非常完美

就是所有能够剪的支都剪掉了

那么我们的α-β剪枝它的时间复杂度呢

可以将那个指数减半 就是这么一个意思