廣度優先搜索 - Java

作爲一個學校，我有一個在java中實現廣度優先搜索的例子。我已經實現了幾乎所有的東西，但問題是，我的搜索不工作，我無法找到問題:(因此，進出口要你指點我，給我在哪裏，最終的問題可能會有一些guidlines。廣度優先搜索 - Java

public ArrayList<SearchNode> search(Problem p) { 
     // The frontier is a queue of expanded SearchNodes not processed yet 
     frontier = new NodeQueue(); 
     /// The explored set is a set of nodes that have been processed 
     explored = new HashSet<SearchNode>(); 
     // The start state is given 
     GridPos startState = (GridPos) p.getInitialState(); 
     // Initialize the frontier with the start state 
     frontier.addNodeToFront(new SearchNode(startState)); 

     // Path will be empty until we find the goal. 
     path = new ArrayList<SearchNode>(); 

     // The start NODE 

     SearchNode node = new SearchNode(startState); 

     // Check if startState = GoalState?? 
     if(p.isGoalState(startState)){ 
      path.add(new SearchNode(startState)); 
      return path; 
     } 


     do { 

      node = frontier.removeFirst(); 
      explored.add(node); 

      ArrayList reachable = new ArrayList<GridPos>(); 
      reachable = p.getReachableStatesFrom(node.getState()); 

      SearchNode child; 

      for(int i = 0; i< reachable.size(); i++){ 

       child = new SearchNode((GridPos)reachable.get(i)); 

       if(!(explored.contains(child) || frontier.contains(child))){ 
        if(p.isGoalState(child.getState())){ 
         path = child.getPathFromRoot() ; 
         return path; 
        } 
        frontier.addNodeToFront(child); 
       } 

      } 
     }while(!frontier.isEmpty()); 


     return path; 
    }

謝謝

來源

2012-09-23 mrjasmin

它是如何工作的？準確。 – Borgleader

它似乎在探索「錯誤」的節點和路徑。 – mrjasmin

你有很多方法，你沒有向我們展示。您好像從兩個不同的數組/列表中提取節點，並將可達節點插入到一個節點中。你的情況也很奇怪，你應該只在經典的實現中檢查'explored'列表。其基本思想是：從列表的開頭提取第一個節點，將其所有鄰居添加到同一列表的末尾。當列表爲空或當您將目標節點添加到該列表時停止。 – IVlad

frontier.addNodeToFront(child);

假設你的代碼（getReachableStatesFrom（），等）的其餘部分是正確的，將元素添加到您的隊列的前面會導致代碼執行的深度優先搜索。

來源

2012-09-23 19:34:09

是的，你是對的。我愚蠢的錯誤。在改變它以將節點添加到後面後，似乎它「幾乎可以工作」：D – mrjasmin

@ user1285737如果您可以識別出代碼可能存在問題的另一個地方，請隨時打開另一個問題:)如果您相信我我已經適當地回答了這個問題，接受我的回答是給予感謝的首選方式。祝你好運！ –

對於實施廣度優先搜索，你笑uld使用隊列。這個過程可能會變得非常複雜。所以，最好保持簡單。您應該將節點的子節點推送到隊列中（左側然後右側），然後訪問節點（打印數據）。然後，你應該從隊列中刪除節點。你應該繼續這個過程，直到隊列變空。你可以在這裏看到我的BFS實現：https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TreeTraverse.java

來源

2016-08-07 00:16:49 Mohammad

廣度優先搜索 - Java

回答

相關問題