BFS 中的目标检查

Question

我尝试根据我的研究在 JAVA 中实现 BFS 算法，但我有点困惑，我不确定我是在检查节点是否是目标节点还是在添加在适当的位置探索列表的节点。这是代码：

frontier.add(nodes.getFirst());//node.isGoal is only true if the node is desired node
    if(frontier.getFirst().isGoal)//Checking if the root node is goal
    {
        explored.add(frontier.getFirst());
        prev.put(frontier.getFirst(), null);
        goalNode = explored.getFirst();
        frontier.poll();
    }
    while (!frontier.isEmpty())
    {
        currentNode = frontier.poll();
        explored.add(currentNode);
        for (Node node : currentNode.children) {//adding node children to fronier and checking if they are goal
            if (!frontier.contains(node) || !explored.contains(node)) {
                frontier.add(node);
                prev.put(node, currentNode);//mapping nodes to parent node to return sequence of nodes
                if (node.isGoal) {
                    goalNode = node;
                    break;
                }
            }
        }
    }

提前致谢。

Answer 1

根据我对您代码的理解，您似乎做错了：您检查了初始集合中的第一个节点（例如树级别），如果它不是目标节点，则添加任何 children 尚未在 frontier 中且尚未访问过。没关系，但可能没有必要。问题在于您在检查 parent 的任何兄弟姐妹之前先检查 child，因此您的搜索不完全是 breadth-first.

那么could/should你做什么？

让我们假设您的数据代表一棵树（breadth-first 表示）并且您从某个级别（例如根节点）开始。由于数据是 breadth-first 方法中的一棵树，因此任何 child 都不可能已经被访问过，并且也可能不在您的 frontier 列表中，因此无需检查（如果您有一个更一般的图表，但情况可能并非如此。

因此算法可能如下所示：

LinkedList<Node> frontier = new LinkedList<>();

//assuming you always have a root node just add it
frontier.add( root );

Node goal = null;

//loop until the list is empty, if we found a goal node we'll break the loop from the inside
while( !frontier.isEmpty() ) {
  //get the node at the start of the list and remove it
  //in the first iteration this will be the root node
  Node node = frontier.pop();

  //found a goal so we're done
  if( node.isGoal ) {
    goal = node ;        
    break; //this breaks the while loop
  }

  //didn't find a goal yet so add the children at the end
  if( node.children != null ) {
    frontier.addAll( node.children );
  }
}

这样做意味着您在末尾添加下一级 (children) 的节点，并从前面弹出树中更高的节点，直到找到您要搜索的内容为了。这意味着您应该始终在列表中只有一个或两个级别的树，即当前级别以及任何已处理的当前级别节点的直接 children。

如您所见，由于我们是在树上操作，因此无需保留 explored 集。

此外，您可能需要考虑是否真的需要在迭代期间构建 prev 地图，因为您可能不得不再次删除元素，而地图并不适合从目标节点获取路径到根。您可能希望在每个节点中保留一个 link 到 parent，因此一旦找到目标节点，您就可以迭代直到到达根节点。

BFS 中的目标检查

Goal checking in BFS

java

breadth-first-search