αβ剪枝算法初理解

本文主要是介绍αβ剪枝算法初理解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

个人认为：αβ剪枝就是为了减少子节点比较，目的就是为了取最稳妥的，能绝对到手的美元。（其实懂了你就可以知道，这是可以赢的概率）

第一步 “比较” ，理解它本身是一个树结构，这棵树是一层最大值，一层最小值，以此类推。最大值一层就是取子节点最大值。最小值一层就是取子节点最小值。

第二步 “剪枝” ，在第一步的基础上理解，左节点已经确认取值范围后，是否还需要继续判断右节点，如果不需要判断右节点，那么就剪枝。

咱们开始了：

称我方为MAX，对方为MIN，图示如下：

比如以此树先理解第一步，每个节点都需要比较大小：

 最后这一排数字是什么？它就意味着能得到的美元金额

第一步，圈圈，取最少可以赢多少钱，3美元和17美元，那么最少赢3美元

第二步，圈圈，取最少可以赢多少钱，2美元和12美元，那么最少赢2美元

 第三步，方块，取最多可以赢多少钱，3美元和2美元，那么最多可以赢3美元

第四步，方块，取最多赢多少钱，下限已经是3美元了，就不看2美元了，取3美元

依次类推，按这种每个节点都比较大小的算法，最终得到的结果就是：

剪枝：

首先必须牢记一下：β 是上限；α  是下限；

第一步：o代表最少赢3美元，p代表赢17美元，但是H是最小节点，那么就意味着不能贪心，需要取最小值，设置H的上限为3     

第二步：那么H是D的子节点，那么D是最大节点，意味着要贪心一点，需要取最大值，但是现在咱们只有3美元，只好先把D下限设置为3。

第三步：首先D的下限已经是3了，所以I的下限也必须为3，（因为I如果确定小于3，那么D节点必然会取3做为最大值）。然后，I的左侧倒推值是2，设置I的上限是2。此时，I的α下限是3，β上限是2，那么R节点不管是多少都不用看了。

换句话说就是，你出I扑克将有几率赢得2美元或者12美元。出H扑克你已经知道能赢3美元，稳妥起见为了规避只赢2美元，那么12美元就不冒险去赌这个概率了。所以，R节点不管是多少，都把他剪掉。

这篇关于αβ剪枝算法初理解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！