java - 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

根据我对您代码的理解，您似乎做错了:您检查初始集中的第一个节点(例如树级别)，如果它不是目标节点，则添加尚未存在的任何子节点frontier 并且尚未访问过。没关系，但可能没有必要。错误在于您在检查 parent 的任何 sibling 之前先检查 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 );
  }
}

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

正如您所看到的，由于我们在树上进行操作，因此无需保留 explored 集。

此外，您可能需要考虑是否真的需要在迭代期间构建 prev map ，因为您可能需要再次删除元素，并且 map 并不真正适合从您的目标获取路径节点到根。您可能希望在每个节点中保留指向父节点的链接，因此一旦找到目标节点，您只需迭代直到到达根节点。