广度优先搜索- Java

Question

作为学校摘录，我在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;
    }

谢谢

Answer 1

frontier.addNodeToFront(child);

假设您的其余代码(getReachableStatesFrom()等)是正确的，向队列前面添加元素将导致您的代码作为深度优先搜索执行。

Answer 2

为了实现广度优先搜索，您应该使用队列。这个过程可能会变得非常复杂。所以，最好让它保持简单。您应该将节点的子节点推送到队列(先左后右)，然后访问该节点(打印数据)。然后，您应该从队列中删除该节点。您应该继续此过程，直到队列变为空。您可以在这里查看我的BFS实现：https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TreeTraverse.java