27

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

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

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

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

4

4 回答 4

12

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

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 层中的所有节点等）

于 2013-01-11T20:17:42.297 回答
7

我不知道这是否是 Russel 和 Norvig 的想法，但如果图是加权的（即某些边比其他边长），最短路径可能比另一个在 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) 更好。

于 2010-11-23T09:30:48.863 回答
6

在未加权（单位成本）图中，双向 BFS 在到达交叉点时找到了最佳解决方案，正如 Russell 和 Norvig 自己在 2003 年版“AIMA”的第 80 页上所说：

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

（通过“扩展一个节点”，R&N 意味着生成后继者。强调添加。）

于 2014-07-27T13:32:01.373 回答
1

一个简单的三角形将满足您的条件，边为 6,6,10，最佳路径通过长度为 10 的段。在双向中，算法向前搜索较短的路径，然后反向也将采用较短的路径，他们会相遇，找到一条完整的路径

但显然 6 + 6 的 2 段比长度为 10 的段差。

于 2018-09-15T00:21:05.817 回答