DFS stackoverflow错误

Question

我正在做一个在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] 
       /  \ 
      ...   ... 

我处理这是我探索的第一个节点，推动它的所有孩子一个堆栈的方式，这种情况发生在一个递归的方法，循环扩展各个节点，直到达到目标状态或达到截止（编号i提供，以避免无休止的循环下去）

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

的后'What is a stack overflow error?'包含哪些物质可能会导致在Java中的StackOverflowError大量的信息。这种错误最常见的原因是递归调用不正确（导致无限循环）。看起来你已经通过为你的递归调用expand()引入临界值来防止这种情况发生。

但即使使用此分隔符，堆栈大小可能很小以处理递归调用。我相信你有两个选择：

1）使用您的截止一个“足够小”的值（这实际工作，因为你已经写了），但是这限制了你的搜索深度。

2）增加JVM的堆栈大小。您可以通过添加标志-Xss1024k作为VM参数来执行此操作。有关如何增加堆栈大小的更多信息，请参阅Java stack overflow error - how to increase the stack size in Eclipse?

Answer 2

使用Dequeue（无任何递归）实现DFS或BFS非常简单，只需循环，从出列头开始读取并生成新尾解决方案（ BFS）。要使用DSF，请将孩子添加到头部。

我认为你应该使用一个广度 - 第一搜索来查找最短可能的解决办法，对不对？

如果一下你对这个深度优先搜索某些（这没有什么意义，我认为），你可以用递归做掉，只是使用dequeue已创建（而不是调用堆栈）。不需要回调电话。只是循环：通过弹出一个节点开始每个循环，产生它的子并推动他们在出队的头上，然后重新开始。如果dequeue是空的有没有办法解决？

在大多数情况下，最好检查生成的解决方案是否已生成，然后将它们添加到队列末尾以减少内存使用量。使用普通集合，HashSet可能比TreeSet更快 - 请记得正确实施Node.equals()和Node.hashCode()。

我想在这种情况下，一个普通的LinkedList将是最有效的Dequeue - 但为什么不测试自己。