Alpha beta搜索时间复杂度

Question

我理解minimax和alpha-beta修剪的基础知识.在所有文献中,他们谈论最佳情况的时间复杂度是O(b ^(d/2)),其中b =分支因子,d =树的深度,基本情况是所有首选节点都是首先扩大.

在我的"最佳案例"的例子中,我有一个4级的二叉树,所以在16个终端节点中,我需要扩展最多7个节点.这与O(b ^(d/2))有何关系？

我不明白他们是怎么来到O(b ^(d/2)).

拜托,有人可以向我解释一下吗？吃了很多!

Answer 1

O(b ^(d/2))对应于α-β修剪的最佳情况时间复杂度.说明:

如果(平均或常数)分支因子为b,搜索深度为d plies,则评估的叶节点位置的最大数量(当移动顺序为pessimal时)为O(b b ...*b)= O( b ^ d) - 与简单的极小极大搜索相同.如果搜索的移动顺序是最佳的(意味着总是首先搜索最佳移动),则评估的叶节点位置的数量对于奇数深度和O是大约O(b*1*b*1*...*b) (b*1*b*1*...*1)均匀深度,或O(b ^(d/2)).在后一种情况下,在搜索的层是偶数的情况下,有效分支因子被减少到其平方根,或者等效地,搜索可以在相同的计算量下变为两倍深.

b*1*b*1*...的解释是必须研究所有第一个玩家的移动才能找到最好的一个,但是对于每一个,只需要最好的第二个玩家的移动来反驳除第一个之外的所有玩家(和最好的)第一个玩家移动 - alpha-beta确保不需要考虑其他第二个玩家移动.

简而言之,你每两个级别"跳过":

O描述了当参数趋向于特定值或无穷大时函数的限制行为,因此在您的情况下,精确地将O(b ^(d/2))与较小的b和d值进行比较并不真正有意义.