私はJavaで8ピースのパズルゲームをやっていて、ランダムな状態から始めて、解決策を見つけるためにDFSを実行する割り当てコマンドを実行しています。
私は Node クラスを持っています。各 Node オブジェクトは、int[][] を使用してどの状態であるか、およびその親ノードが何であるかを認識しています。また、移動できる方向 (左、右、上、下) も認識しています。
goal state: start state (random):
[0 1 2] [1 8 0]
[3 4 5] [3 7 4]
[6 7 8] [2 5 6]
単一のノード (開始ノード) から始めて、プログラムは可能なすべての子ノードのノードを作成します。空白の正方形がどの方向に移動できるかを確認し、すでに別のノードに属している状態に戻らないことを確認します。上記の例では、開始ノードは次のように展開されます。
[1 8 0]
A) [3 7 4]
[2 5 6]
/ \
[1 0 8] [1 8 4]
B) [3 7 4] [3 7 0] C)
[2 5 6] [2 5 6]
/ / / \
... ... [1 8 4] [1 8 4]
D) [3 0 7] [3 7 6] E)
[2 5 6] [2 5 0]
/ / / / \
... ... ... [1 8 4] NO
F) [3 7 6] CHILD
[2 0 5]
/ \
... ...
これを処理する方法は、最初のノードを探索し、そのすべての子をスタックにプッシュすることです。これは、目標状態に到達するかカットオフに到達するまで各ノードをループ拡張する再帰的な方法で発生します (私が提供する数)永遠にループしないようにしてください)
stack = [A]
pop()
stack = []
A -> B
push(B)
stack = [B]
A -> C
push(C)
stack = [C|B]
A -> NO MORE CHILDREN
pop()
stack = [B]
C -> D
push(D)
stack = [D|B]
C -> E
push(E)
stack = [E|D|B|]
C -> NO MORE CHILDREN
pop()
stack = [D|B|]
E -> F
push(F)
stack = [F|D|B]
E -> NO MORE CHILDREN
pup()
stack = [D|B]
私のカットオフが高すぎない限り、コードは正常に機能します。
私は何を間違っていますか？
public void expand(Node parent, int cutoff){
cutoff--;
int[][] currentState = parent.getState();
if(Arrays.deepEquals(currentState, goalState)){
found = true;
goalNode = parent;
}
if(cutoff>0 && !found){
if(parent.up){
Node child = createUPnode();
child.setParent(parent);
stack.push(child);
parent.up = false;
expand(parent, cutoff)
}
else if(parent.right){
Node child = createRIGHTnode();
child.setParent(parent);
stack.push(child);
parent.right = false;
expand(parent, cutoff)
}
else if(parent.down){
Node child = createDOWNnode();
child.setParent(parent);
stack.push(child);
parent.down = false;
expand(parent, cutoff)
}
else if(parent.left){
Node child = createLEFTnode();
child.setParent(parent);
stack.push(child);
parent.left = false;
expand(parent, cutoff)
}
else{
Node nextNode = stack.pop();
expand(nextNode, cutoff);
}
}
else{
System.out.println("CUTOFF REACHED");
}
}