Ошибка DFS StackOverflow

Question

Я занимаюсь игрой головоломки на 8 частей в Java, и команды задания, которые я делаю DFS, чтобы найти решение, начиная с случайного состояния.

У меня есть класс узлов, каждый объект узла знает, какое состояние он использует 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");
  }
}

Answer 1

Пост «Что такое ошибка переполнения стека?» Содержит много информации о том, что может вызвать StackOverflowerRor в Java. Наиболее распространенной причиной для такого рода ошибок является плохой рекурсивный вызов (вызывая бесконечную петлю). Похоже, вы уже охраняли это, введя ценность для ваших рекурсивных вызовов expand().

Но даже с этим разделителем размер стека может быть маленьким, чтобы обрабатывать рекурсивные вызовы. Я считаю, что у вас есть два варианта:

1) Используйте «достаточно маленькое» значение для вашего отсечения (это на самом деле работает, как вы уже писали), но это ограничивает глубину вашего поиска.

2) Увеличьте размер стека JVM. Вы можете сделать это, добавив флаг -Xss1024k как аргумент виртуальной машины. Для получения дополнительной информации о том, как увеличить размер стека, прочитайте Ошибка переполнения стека Java - как увеличить размер стека в Eclipse?

Answer 2

Это просто внедрить DFS или BFS, используя Dequeue, без какого -либо рекурсии, просто петля, чтение от головы Dequeue и создание новых решений для хвоста (BFS). Чтобы использовать DSF, добавьте детей в голову.

Я думаю, вы должны использовать Ширина-Па поиска, чтобы найти самый короткий Возможное решение, верно?

Если Вы уверены о глубине первого поиска (что не имеет смысла, я думаю) вы можете покончить с рекурсией и просто использовать dequeue Вы создали (не стек вызовов). Рекализующие звонки не нужны. Просто цикл: запустите каждый цикл, вытащив узел, генерируйте его детей и толкните их на голову Dequeue, затем начните все сначала. Если dequeue пусто, нет решения ...

В большинстве случаев лучше проверить, было ли создано сгенерированное решение до Добавление их к концу очереди, чтобы уменьшить использование памяти. Используя простые коллекции, хэшсет, вероятно, быстрее, чем деревья- не забудьте реализовать Node.equals() а также Node.hashCode() правильно.

Я полагаю, что обычный LinkedList был бы наиболее эффективным Dequeue В этом случае - но почему бы не проверить себя.