根据我所做的大部分读数,双向搜索算法据说在"forward"和"backward"前沿首先相交时终止 . 然而,在人工智能:现代方法的第3.4.6节中,Russel和Norvig说:
通过检查目标测试以查看两个搜索的边界是否相交来实现双向搜索;如果他们这样做,就找到了解决方案 . 重要的是要意识到找到的第一个解决方案可能不是最优的,即使这两个搜索都是广度优先的;需要进行一些额外的搜索,以确保跨越差距没有捷径 .
我已经考虑了这个陈述很长一段时间了,但我找不到这种行为的例子 . 任何人都可以提供一个示例图,其中双向BFS或A *搜索的前向和后向边界之间的第一个交叉点不是最短路径吗?
Edit: 显然,BFS无法在加权图中找到最短路径 . 听起来这段摘录指的是无向图上的双向BFS . 或者,我有兴趣在加权图上看到使用双向A *的反例 .
4 回答
我不知道这是否是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)更好 .
我认为这与双向搜索的实现方式有关 .
BFS的伪代码如下:
想象一下实现这样的双向搜索:
基本上,“前进”BFS和“后退”BFS的交替步骤 . 现在想象一下这样的图:
BFS的第一次前进和后退将给我们这样一个状态:
现在算法选择下一个节点从前沿扩展并选择B.
现在我们运行一个向后的BFS并展开节点D.D的孩子C在前沿,所以我们返回路径A - B - C - D - E.
我认为这就是Russel和Norvig所指的内容 . 如果实现不考虑这种情况,它可能会给你一个不是最优的解决方案 .
在决定找到最佳解决方案之前,它应该完成扩展边界中具有相同“深度”的所有节点 . 或者可以按层而不是按节点交替前向和后向BFS搜索(向前展开第0层中的所有节点,向后展开第0层中的所有节点,向前展开第1层中的所有节点,等等)
在未加权(单位成本)图中,双向BFS在碰到交叉点时找到了最佳解决方案,正如Russell&Norvig本身在2003年版“AIMA”的第80页上所述:
(通过“扩展节点”,R&N意味着产生后继者 . 强调增加 . )
一个简单的三角形将满足你的条件,边是6,6,10,最佳路径穿过长度为10的段 . 在双向中,算法向前搜索较短的路径,然后反向也采用较短的路径他们会见面,找到一条完整的道路
但显然6 6的2个部分比10个长度的部分差 .