双向搜索的终止标准

Question

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

双向搜索是通过将目标测试替换为检查来实现的 两个搜索的边界是否相交；如果他们这样做了，就已经找到了解决方案。 重要的是要认识到，找到的第一个解决方案可能不是最佳的，即使 两次搜索都是广度优先；需要进行一些额外的搜索以确保存在 不是跨越鸿沟的捷径。

我已经考虑这个说法很长一段时间了，但我找不到这种行为的例子。谁能提供一个示例图，其中双向 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 层中的所有节点等）

Answer 2

我不知道这是否是拉塞尔和诺维格的初衷，但如果对图进行加权（即某些边比其他边长），那么最短路径可能比另一个路径有更多的步骤，这将导致在 BFS 中更快被发现。即使步数相同，也不一定先找到最好的；考虑一个具有六个节点的图：

(A->B) = (A->C) = 0

(B->D) = 2

(C->E) = 1

(D->F) = (E→F)＝0

从A向前一步，从F向后一步后，向前前沿是{B，C}，向后前沿是{D，E}。搜索者现在展开 B，嘿！路口！ (A->B->D->F) = 2。但仍然应该进一步搜索才能发现 (A->C->E->F) 更好。

Answer 3

在未加权（单位成本）图中，双向 BFS 在遇到交叉点时已找到最佳解决方案，如 Russell & Norvig 在 2003 年版《AIMA》第 80 页上写道：

双向搜索是通过让一个或两个搜索在扩展节点之前检查每个节点来实现的，以查看它是否位于另一棵搜索树的边缘 [...] 该算法是完整且最佳的（对于统一的步骤成本）如果两个搜索都是广度优先[.]

（通过“扩展节点”，R＆N意味着生成后继。强调。）

Answer 4

一个简单的三角形就可以满足您的条件，边长为 6,6,10。最佳路径是长度为 10 的单段。在双向中，算法向前搜索较短的路径，长度为 6，然后反向也将采用较短的路径，长度同样为 6 - 它们会相遇，并且算法检测到找到一条完整的路径。

但很明显，2 个 6 的线段 (6+6=12) 比 1 个长度为 10 的线段长。