非二叉树中的 Alpha–beta 修剪
Alpha–beta pruning in non-binary-tree
C++ 上的经典 Alpha–beta p运行ing 代码是否适用于非二叉树(节点有 3 个或更多子节点),因为此代码的所有示例都与二叉树一起使用,并且当我在 VS 上 运行 这段代码时,真正的答案(纸上)和代码的结果是 different.Is 它正常吗?这是来自互联网的代码:
#include <iostream>
#include <algorithm>
#include <cmath>
#include <climits>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int getHeight(int n) {
return (n == 1) ? 0 : 1 + log2(n / 2);
}
int minmax(int height, int depth, int nodeIndex,
bool maxPayer, int values[], int alpha,
int beta) {
if (depth == height) {
return values[nodeIndex];
}
if (maxPayer) {
int bestValue = INT_MIN;
for (int i = 0; i < height - 1; i++) { //MAYBE THE PROBLEM IS HERE??????
int val = minmax(height, depth + 1, nodeIndex * 2 + i, false, values, alpha, beta);
bestValue = max(bestValue, val);
alpha = max(alpha, bestValue);
if (beta <= alpha)
break;
}
return bestValue;
} else {
int bestValue = INT_MAX;
for (int i = 0; i < height - 1; i++) {
int val = minmax(height, depth + 1, nodeIndex * 2 + i, true, values, alpha, beta);
bestValue = min(bestValue, val);
beta = min(beta, bestValue);
if (beta <= alpha)
break;
}
return bestValue;
}
}
int main() {
int values[] ={9,3,10,20,1,15,2,27,35,4,7,14,2,1,55,0,8,6,0,2,80,47,33,42,14,25,1 }; ////for example, 9,3 and 10 are the children of the same node
int height = getHeight(SIZE(values));
int result = minmax(height, 0, 0, true, values, INT_MIN, INT_MAX);
cout <<"Result : " << result << "\n";
return 0;
}
看起来你在堆结构中定义了一棵树。
如果节点的 children 数是可变的(“3 个或更多”),则不能真正使用此数组结构来表示树。它适用于 complete:
的树
- 每个节点都有 k children 或 none,除了一个节点,它可能有任意数量的 children 在 1 和 k 之间(叶子)。
- 树的所有级别都被完全填满
- 除了最后一层可能不完整,但该层中的所有叶节点都应位于该层的左侧。这个底层最右边的叶子是第一个要点中提到的异常节点的 child。
所以如果你的树遵循这些规则,那么你仍然需要对你的代码进行一些调整,因为它仍然指的是 k 为 2 的情况(二叉树) .
从您代码中的评论来看,您似乎没有为树的根存储值(因为您将 9 称为 child),因此索引 0 处的值是 child 的根,而不是根本身。
- 树高的计算公式为:1 + ⌊logk(n+1)⌋。 n 加 1 是为了弥补缺失的根值。
- 一个节点的children的数量不依赖于高度,而是依赖于k(你应该定义它,可能是一个常数)。所以你的
for
循环应该 运行 k 次。
- child的索引不是
nodeIndex * 2 + i
,而是nodeIndex * k + i
C++ 上的经典 Alpha–beta p运行ing 代码是否适用于非二叉树(节点有 3 个或更多子节点),因为此代码的所有示例都与二叉树一起使用,并且当我在 VS 上 运行 这段代码时,真正的答案(纸上)和代码的结果是 different.Is 它正常吗?这是来自互联网的代码:
#include <iostream>
#include <algorithm>
#include <cmath>
#include <climits>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int getHeight(int n) {
return (n == 1) ? 0 : 1 + log2(n / 2);
}
int minmax(int height, int depth, int nodeIndex,
bool maxPayer, int values[], int alpha,
int beta) {
if (depth == height) {
return values[nodeIndex];
}
if (maxPayer) {
int bestValue = INT_MIN;
for (int i = 0; i < height - 1; i++) { //MAYBE THE PROBLEM IS HERE??????
int val = minmax(height, depth + 1, nodeIndex * 2 + i, false, values, alpha, beta);
bestValue = max(bestValue, val);
alpha = max(alpha, bestValue);
if (beta <= alpha)
break;
}
return bestValue;
} else {
int bestValue = INT_MAX;
for (int i = 0; i < height - 1; i++) {
int val = minmax(height, depth + 1, nodeIndex * 2 + i, true, values, alpha, beta);
bestValue = min(bestValue, val);
beta = min(beta, bestValue);
if (beta <= alpha)
break;
}
return bestValue;
}
}
int main() {
int values[] ={9,3,10,20,1,15,2,27,35,4,7,14,2,1,55,0,8,6,0,2,80,47,33,42,14,25,1 }; ////for example, 9,3 and 10 are the children of the same node
int height = getHeight(SIZE(values));
int result = minmax(height, 0, 0, true, values, INT_MIN, INT_MAX);
cout <<"Result : " << result << "\n";
return 0;
}
看起来你在堆结构中定义了一棵树。
如果节点的 children 数是可变的(“3 个或更多”),则不能真正使用此数组结构来表示树。它适用于 complete:
的树- 每个节点都有 k children 或 none,除了一个节点,它可能有任意数量的 children 在 1 和 k 之间(叶子)。
- 树的所有级别都被完全填满
- 除了最后一层可能不完整,但该层中的所有叶节点都应位于该层的左侧。这个底层最右边的叶子是第一个要点中提到的异常节点的 child。
所以如果你的树遵循这些规则,那么你仍然需要对你的代码进行一些调整,因为它仍然指的是 k 为 2 的情况(二叉树) .
从您代码中的评论来看,您似乎没有为树的根存储值(因为您将 9 称为 child),因此索引 0 处的值是 child 的根,而不是根本身。
- 树高的计算公式为:1 + ⌊logk(n+1)⌋。 n 加 1 是为了弥补缺失的根值。
- 一个节点的children的数量不依赖于高度,而是依赖于k(你应该定义它,可能是一个常数)。所以你的
for
循环应该 运行 k 次。 - child的索引不是
nodeIndex * 2 + i
,而是nodeIndex * k + i