剪枝算法算法
2023-09-11 05:06:37
作者：情到深处人孤独i
我有一个头痛理解为什么正在打印的α-β剪枝的结果上一节课例如某些节点，所以我用Java实现的彼得·诺维格版的α+β修剪。
有了这样的树：
最大
/ | \
分分分
/ / | / | \ / | \
3月12日8 2 3 9 14 1 8
本教科书说，应扩大唯一的终端节点是
3，12，8，2，14，1
在这个顺序。
我的算法打印：
参观叶子值3
参观叶与值12
参观叶与价值2
参观叶与价值3
参观叶与值14
参观叶与值1
参观叶与价值8
根值3
根是极大极小根正确的值。我已经调试了几个小时，似乎无法找到故障。难道我忽略的东西或者是教科书不正确的？
包字母a;
进口的java.util.ArrayList;
类节点{
布尔isMin;
布尔isMax;
布尔isTerminal;
int值;
INT深度;
ArrayList的＆LT;节点＆GT;孩子=新的ArrayList＆LT;节点＆GT;（）;
}
公共类字母a {
静态节点alphaBetaSearch（节点状态）{
state.value = MAX_VALUE（州，-99999,99999）;
的System.out.println（state.value）;
返回null;
}
静态INT MAX_VALUE（节点状态，INTα，INT测试版）{
如果（state.isTerminal）{
的System.out.println（拜访叶与价值+ state.value）;
返回state.value;
}
state.value = -99999;
对于（节点一：state.children）{
state.value = Math.max（state.value，MIN_VALUE（A，α，β））;
如果（state.value＆GT; =测试版）{
返回state.value;
}
阿尔法= Math.max（α，state.value）;
}
返回state.value;
}
静态INT MIN_VALUE（节点状态，INTα，INT测试版）{
如果（state.isTerminal）
返回state.value;
state.value = 99999;
对于（节点一：state.children）{
state.value = Math.min（state.value，MAX_VALUE（A，α，β））;
如果（state.value＆GT; =测试版）{
返回state.value;
}
公测= Math.min（测试版，state.value）;
}
返回state.value;
}
公共静态无效的主要（字串[] args）{
节点T1 =新节点（）;
// t1.value = 4;
t1.value = 3;
t1.depth = 2;
t1.isTerminal =真;
节点T2 =新节点（）;
// t2.value = 8;
t2.value = 12;
t2.depth = 2;
t2.isTerminal =真;
节点T3 =新节点（）;
// t3.value = 7;
t3.value = 8;
t3.depth = 2;
t3.isTerminal =真;
节点分1 =新节点（）;
min1.isTerminal = FALSE;
min1.depth = 1;
min1.children.add（T1）;
min1.children.add（T2）;
min1.children.add（T3）;
节点T4 =新节点（）;
// t4.value = 5;
t4.value = 2;
t4.depth = 2;
t4.isTerminal =真;
节点T5 =新节点（）;
//t5.value = 2;
t5.value = 3;
t5.depth = 2;
t5.isTerminal =真;
节点T6 =新节点（）;
// t6.value = 1;
t6.value = 9;
t6.depth = 2;
t6.isTerminal =真;
节点MIN2 =新节点（）;
min2.isMin =真;
min2.isTerminal = FALSE;
min2.depth = 1;
min2.children.add（T4）;
min2.children.add（T5）;
min2.children.add（T6）;
节点T7 =新节点（）;
// t7.value = 1;
t7.value = 14;
t7.depth = 2;
t7.isTerminal =真;
节点T8 =新节点（）;
// t8.value = 6;
t8.value = 1;
t8.depth = 2;
t8.isTerminal =真;
端T9 =新节点（）;
// t9.value = 0;
t9.value = 8;
t9.depth = 2;
t9.isTerminal =真;
节点MIN3 =新节点（）;
min3.isMin =真;
min3.isTerminal = FALSE;
min3.depth = 1;
min3.children.add（T7）;
min3.children.add（T8）;
min3.children.add（T9）;
节点MAX1 =新节点（）;
max1.isMax = TRUE;
max1.isTerminal = FALSE;
max1.depth = 0;
max1.children.add（分1）;
max1.children.add（MIN2）;
max1.children.add（MIN3）;
alphaBetaSearch（MAX1）;
}
}
解决方案
您有两条线路：
如果（state.value> =测试版）{
其中的一个行应该有字母而不是测试版。
I was having a headache understanding why certain nodes on a lesson example were being printed as a result of alpha-beta pruning, so I implemented Peter Norvig's version of alpha beta pruning in Java.
With a tree like this:
max
/ | \
min min min
/ / | / | \ / | \
3 12 8 2 3 9 14 1 8
The textbook says that the only terminal nodes that should be expanded are
3, 12, 8, 2, 14, 1
in that order.
My algorithm prints:
visited leaf with value 3
visited leaf with value 12
visited leaf with value 2
visited leaf with value 3
visited leaf with value 14
visited leaf with value 1
visited leaf with value 8
Root value 3
The root is the correct value for the minimax root. I've debugged for a couple of hours and can't seem to find fault. Have I overlooked something or is the textbook incorrect?
package alphabeta;
import java.util.ArrayList;
class Node {
boolean isMin;
boolean isMax;
boolean isTerminal;
int value;
int depth;
ArrayList <Node> children = new ArrayList <Node>();
}
public class AlphaBeta {
static Node alphaBetaSearch(Node state){
state.value = max_value(state,-99999,99999);
System.out.println(state.value);
return null;
}
static int max_value(Node state, int alpha, int beta){
if (state.isTerminal){
System.out.println("visited leaf with value " + state.value);
return state.value;
}
state.value = -99999;
for (Node a: state.children){
state.value = Math.max(state.value , min_value(a, alpha, beta));
if (state.value >= beta){
return state.value;
}
alpha = Math.max(alpha, state.value);
}
return state.value;
}
static int min_value(Node state, int alpha, int beta){
if (state.isTerminal)
return state.value;
state.value = 99999;
for (Node a: state.children){
state.value = Math.min(state.value, max_value(a, alpha, beta));
if (state.value >= beta){
return state.value;
}
beta = Math.min(beta, state.value);
}
return state.value;
}
public static void main(String[] args) {
Node t1 = new Node();
// t1.value = 4;
t1.value = 3;
t1.depth =2;
t1.isTerminal = true;
Node t2 = new Node();
// t2.value = 8;
t2.value = 12;
t2.depth=2;
t2.isTerminal= true;
Node t3 = new Node();
// t3.value = 7;
t3.value = 8;
t3.depth=2;
t3.isTerminal= true;
Node min1 = new Node();
min1.isTerminal=false;
min1.depth=1;
min1.children.add(t1);
min1.children.add(t2);
min1.children.add(t3);
Node t4 = new Node();
// t4.value = 5;
t4.value = 2;
t4.depth =2;
t4.isTerminal = true;
Node t5 = new Node();
//t5.value = 2;
t5.value =3;
t5.depth=2;
t5.isTerminal= true;
Node t6 = new Node();
// t6.value = 1;
t6.value=9;
t6.depth=2;
t6.isTerminal= true;
Node min2 = new Node();
min2.isMin=true;
min2.isTerminal=false;
min2.depth=1;
min2.children.add(t4);
min2.children.add(t5);
min2.children.add(t6);
Node t7 = new Node();
// t7.value = 1;
t7.value=14;
t7.depth =2;
t7.isTerminal = true;
Node t8 = new Node();
// t8.value = 6;
t8.value=1;
t8.depth=2;
t8.isTerminal= true;
Node t9 = new Node();
// t9.value = 0;
t9.value=8;
t9.depth=2;
t9.isTerminal= true;
Node min3 = new Node();
min3.isMin=true;
min3.isTerminal=false;
min3.depth=1;
min3.children.add(t7);
min3.children.add(t8);
min3.children.add(t9);
Node max1 = new Node();
max1.isMax=true;
max1.isTerminal=false;
max1.depth=0;
max1.children.add(min1);
max1.children.add(min2);
max1.children.add(min3);
alphaBetaSearch (max1);
}
}
解决方案
You have two lines:
if (state.value >= beta){
One of those lines should have alpha instead of beta.
相关推荐
猜您喜欢
精彩图集
