广度优先搜索 - 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

回答

相关问题