α-β搜索法_解决人工智能问题中的方法

α-β搜索法

解决人工智能问题中的方法

下棋程序关键之一使如何减少计算机要考虑的棋步。约翰麦卡锡发明了α-β搜索法，使计算机“明白”并不是所有情况都得考虑，有效减少了计算量。

基本思想：根据倒推值的计算方法，或中取大，与中取小，在扩展和计算过程中，能剪掉不必要的分枝，提高效率。

定义：

α值：有或后继的节点，取当前子节点中的最大倒推值为其下界，称为α值。节点倒推值＞=α；

β值：有与后继的节点，取当前子节点中的最小倒推值为其上界，称为β值。节点倒推值＜=β；

α-β 剪枝：

（1） β剪枝：节点x的α值不能降低其父节点的β值，x以下的分支可停止搜索，且x的倒推值为α；

（2） α 剪枝：节点x的β值不能升高其父节点的α值，x以下的分支可停止搜索，且x的倒推值为β ；

参考资料

最新修订时间：2023-10-09 11:25

条目作者

概述

参考资料