algorithm - 双向搜索的终止条件

Question

根据我所做的大部分阅读，双向搜索算法据说在“前向”和“后向”边界首次相交时终止。然而，在人工智能:现代方法的第 3.4.6 节中，Russel 和 Norvig 指出:

Bidirectional search is implemented by replacing the goal test with a check to see whether the frontiers of the two searches intersect; if they do, a solution has been found. It is important to realize that the first solution found may not be optimal, even if the two searches are both breadth-first; some additional search is required to make sure there isn't a shortcut across the gap.

我考虑这个说法已经有一段时间了，但我找不到这种行为的例子。谁能提供一个示例图，其中双向 BFS 或 A* 搜索的前向边界和后向边界之间的第一个交点不是最短路径？

编辑:显然 BFS 不会在加权图中找到最短路径。听起来这段摘录是指无向图上的双向 BFS。或者，我有兴趣看到在加权图上使用双向 A* 的反例。

Answer 1

我认为这与双向搜索的实现方式有关。

BFS 的伪代码是这样的:

until frontier.empty?
    node <- frontier.pop()
    add node to explored
    for each child not in expored or frontier:
        if child is goal then
            return path
        add child to frontier

想象一下像这样实现双向搜索:

until frontierForward.emtpy? or frontierBackward.empty?
    node <- frontierForward.pop()
    add node to exploredForward
    for each child not in exporedForward or frontierForward:
        if child in frontierBackward then
            return pathForward + pathBackward
        add child to frontierForward

    Do something similar but now searching backwards

基本上，“前向”BFS 和“后向”BFS 的交替步骤。现在想象这样一个图:

    B-C-D
  /       \
A           E
  \       /
    F - G

BFS 的第一次向前和向后运行会给我们这样的状态:

1) expandedForward = A ; frontierForward = B, F
2) expandedBackward = E ; frontierBackward = D, G

现在算法选择下一个节点从前向边界扩展并选择 B。

3) expandedForward = A, B ; frontierForward = F, C

现在我们运行反向 BFS 并扩展节点 D。D 的子节点 C 位于前向边界，因此我们返回路径 A - B - C - D - E。

我认为这就是 Russel 和 Norvig 所指的内容。如果实现不考虑这种情况，它可能会为您提供一个不是最佳的解决方案。

在确定找到最佳解决方案之前，它应该完成扩展边界中具有相同“深度”的所有节点。或者可以按层而不是按节点交替进行前向和反向 BFS 搜索(向前扩展第 0 层中的所有节点，向后扩展第 0 层中的所有节点，向前扩展第 1 层中的所有节点，等等)