Java教程

αβ剪枝算法初理解

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

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

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

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

 

咱们开始了:

称我方为MAX,对方为MIN,图示如下:

https://jlice-top.oss-cn-beijing.aliyuncs.com/464e4b76002211e99eb2509a4c21c90b.png

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

 

 

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

第一步,圈圈,取最少可以赢多少钱,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节点不管是多少,都把他剪掉。

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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