我正在做一個在java中的8件益智遊戲,並做了一個DFS查找解決方案的任務命令,從隨機狀態開始。DFS stackoverflow錯誤
我有一個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");
}
}
謝謝你,我增加了堆棧大小,並擺脫了stackoverflow錯誤,但我覺得它需要很長時間才能解決這個難題,至少我在網上看到的其他8個拼圖可以解決自己10秒,我的算法有什麼問題嗎?或者DFS採取這麼長時間很自然? – Alex 2011-05-03 11:30:15
也許你在網上看到的解決方案使用了一些啓發式的步驟。例如,我不認爲你必須考慮通過執行向下操作來擴展當前節點到達時與Up操作對應的節點。因爲你只是回到父節點,對吧?這是一個簡單的技巧,它已經消除了找到解決方案所需擴展的25%(粗略的,也許是錯誤的估計)。我相信你可以考慮其他這樣的規則來進一步改進搜索。 – phuibers 2011-05-03 11:41:49
還有第三個選項可以消除這個問題。明確堆棧並消除遞歸。而不是遞歸調用,使用堆棧。作爲一個例子,閱讀維基百科(http://en.wikipedia.org/wiki/Tree_traversal#Iterative_Traversal)上描述的迭代樹遞歸示例。我會考慮消除堆棧的最佳選擇。這意味着您可以處理任意複雜的圖形,只能處理可用的內存而不是堆棧的大小。 – 2011-05-03 12:28:08