BFS函數的正確性？

問題是使用bfs函數來構建/找到peg solitare遊戲的解決方案。給你一個包含開始狀態的節點，從這個狀態開始，節點擴展到更多的狀態（它的子節點）。一旦找到包含目標狀態的節點，函數應該停止。BFS函數的正確性？

public void search(){ 
    bfs.add(StartGoal); 
while(!bfs.isEmpty()) { 
    node = bfs.poll(); 
    if(node.isGoal()){System.out.println("success"); return;} 
    node.expand(); 
    for(MyNode m : node.childs){ 
     if(!m.isGoal()){ 
      m.setVisited(); 
      bfs.add(m);}} 
     node.setVisited(); 
    }

展開函數，根據下一個可能的棋盤狀態啓動childs鏈表並創建子節點。

public void expand(){ 
    if(childs != null) return;//already expanded do nothing 
    else{ 
    childs= new LinkedList<MyNode>(); 
    for(BoardState b: state.nextStates()) 
     childs.add(new MyNode(this, b));} 
}

我跑了代碼，並改進了好幾次。一旦隊列達到300萬以上，由於空間不足而崩潰。我的問題是：這最終會起作用嗎？代碼是否正確？

這是我的第一篇文章，很抱歉，如果我吮吸格式化問題很好。謝謝。

來源

2014-02-23 user3341794

您的代碼不正確。我看到兩個重大錯誤，或者是一個有兩個重大後果的大錯誤，還有一個小錯誤。可能還有其他一些我看不到的bug，還有其他一些改進的東西。第一個錯誤是

if(!m.isGoal()){ 
     m.setVisited(); 
     bfs.add(m);}}

您特別不會將目標狀態添加到隊列中。

第二個錯誤是你永遠不會測試一個節點是否被訪問過。這可能是相同的錯誤作爲第一位的，因爲它看起來像他們可能是可以解決的有相同的修訂：

if (!m.isVisited()) {

第三個錯誤是，你只標註處理其第一個孩子後訪問節點。如果沒有子節點，則永遠不會標記已訪問的節點，並且如果節點可以將其自己作爲子節點，則可以在擴展父節點之前將該子節點添加到隊列中。這不會影響結果的正確性，儘管它可能會影響您的效率。

來源

2014-02-23 00:33:15 user2357112

BFS函數的正確性？

回答

相關問題