双向搜索的终止条件 [英] Termination Criteria for Bidirectional Search

问题描述

根据我所做的大部分阅读，据说双向搜索算法在向前"和向后"边界第一次相交时终止.但是，在人工智能:现代方法的第 3.4.6 节中，Russel 和 Norvig 声明:

According to most of the reading I have done, a bidirectional search algorithm is said to terminate when the "forward" and "backward" frontiers first intersect. However, in Section 3.4.6 of Artificial Intelligence: A Modern Approach, Russel and Norvig state:

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

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* 搜索的前向和后向边界之间的第一个交集不是最短路径?

I have considered this statement for quite some time, but am unable to find an example of this behavior. Can anyone provide an example graph where the first intersection between the forward and backward frontiers of a bidirectional BFS or A* search is not the shortest path?

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

Clearly BFS will not find the shortest path in a weighted graph. It sounds like this excerpt is referring to bidirectional BFS on a undirected graph. Alternatively, I would be interested in seeing a counterexample using bidirectional A* on a weighted graph.

推荐答案

我不知道这是否是 Russel 和 Norvig 的想法，但是如果图是加权的(即某些边比其他边长)，则最短 路径可能比在 BFS 中更快找到的路径有更多的步骤.即使步数相同，也不一定先找到最好的；考虑一个有六个节点的图:

I don't know if this is what Russel and Norvig had in mind, but if the graph is weighted (i.e. some edges are longer than others), the shortest path might have more steps than another which would be found sooner in a BFS. Even if the number of steps is the same, the best might not be found first; consider a graph with six nodes:

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

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

(B->D) = 2

(C->E) = 1

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

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

从A向前一步，从F向后一步，前边界为{B,C}，后边界为{D,E}.搜索者现在展开 B，嘿！路口！(A->B->D->F) = 2. 但还是要搜索得更远一点才会发现 (A->C->E->F) 更好.

After one step forward from A and one step backward from F, the forward frontier is {B,C} and the backward frontier is {D,E}. The searcher now expands B and hey! intersection! (A->B->D->F) = 2. But it should still search a little farther to discover that (A->C->E->F) is better.

这篇关于双向搜索的终止条件的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！