我了解 minimax 和 alpha-beta 修剪的基础知识。在所有文献中，他们谈到最佳情况的时间复杂度是 O(b^(d/2))，其中 b = 分支因子，d = 树的深度，基本情况是所有首选节点都首先展开。
在我的“最佳情况”示例中，我有一个 4 级的二叉树，所以在 16 个终端节点中，我最多需要扩展 7 个节点。这与 O(b^(d/2)) 有什么关系？
我不明白他们是如何得出 O(b^(d/2)) 的。
问问题
14247 次
1 回答
20
O(b^(d/2)) 对应于 alpha-beta 剪枝的最佳情况时间复杂度。说明：
使用 b 的（平均或恒定）分支因子和 d 层的搜索深度，评估的叶节点位置的最大数量（当移动排序最小时）为 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*... 的解释是，必须研究所有第一个玩家的动作以找到最好的，但对于每个，只需要最好的第二个玩家的动作来反驳除第一个之外的所有（和最好的）先手移动——阿尔法-贝塔确保不需要考虑其他的第二手移动。
简单地说，你“跳过”每两个级别：
O 描述了当参数趋于特定值或无穷大时函数的限制行为，因此在您的情况下，将 O(b^(d/2)) 与 b 和 d 的小值进行精确比较并没有真正意义。
于 2013-05-02T01:35:31.593 回答