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 - 但爲什麼不測試自己。