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

谢谢你

- mrjasmin

---

它为什么不工作？请具体说明。 - Borgleader

似乎它正在探索“错误”的节点和路径。 - mrjasmin

您有很多方法没有向我们展示。您似乎从两个不同的数组/列表中提取节点，并将可达节点插入到一个列表中。您的条件也很奇怪，在经典实现中，应该只检查“已探索”列表。基本思路是：从列表开头提取第一个节点，将其所有邻居添加到同一列表的末尾。当列表为空或将目标节点添加到该列表时停止。 - IVlad

这只是一个假设，但是你的SearchNode类中hashCode和equals方法是怎样的呢？explored.contains(child)方法可以使用这两个方法来查找SearchNode，但有可能会失败。 - daniel

我将 addNodeToBack 恢复为 addNodeToFront - 因为这是一个重要的问题，在 Alex Lynch 的回答中已经提到。请不要更改它，因为它可能会帮助未来遇到类似问题的读者，并且在阅读编辑后的问题后不会理解出错了什么。 - amit

Answer 1

frontier.addNodeToFront(child);

假设你的代码（getReachableStatesFrom()等）都正确，将元素添加到队列前面会使您的代码执行深度优先搜索。

- Alex Lynch

---

是的，你说得对。我犯了一个愚蠢的错误。在将节点添加到后面后，它似乎“几乎可以工作”：D - mrjasmin

@user1285737 如果你能找到代码可能存在问题的另一个地方，可以开一个新的问题 :) 如果你认为我已经适当地回答了这个问题，接受我的答案是表达感谢的首选方式。祝你好运！ - Alex Lynch

Answer 2

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

- Mohammad