Я делаю 8-кусочную игру-головоломку в Java и команды назначения, которые я выполняю 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]
Код работает нормально, пока моя отсечка не слишком высока,если это то, чем я получаю ошибку: java.lang.StackOverflowError
Что я делаю не так?
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");
}
}