双向搜索的终止标准

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在碰到交叉点时找到了最佳解决方案,正如Russell&Norvig本身在2003年版"AIMA"的第80页上所述:

双向搜索由具有一个或两个搜索检查每个节点膨胀以查看它是否在其他搜索树的边缘之前实现[...]的算法是完整和最佳的(均匀步骤成本),如果两个搜索都是广度优先[.]

(通过"扩展节点",R&N意味着产生后继者.强调增加.)

Answer 3

我不知道这是否是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)更好.

Answer 4

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

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