对于双向搜索终止标准 [英] Termination Criteria for Bidirectional Search

问题描述

据大部分的阅读我都做了，双向搜索算法被认为结束的时候，前进和后退边境第一相交。然而，在第3.4.6的人工智能：一种现代方法的，罗素和弱势族群的状态：

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.

推荐答案

我不知道这是罗素和弱势族群脑子里想的，但如果图表加权（即一些边缘比别人更长的时间），在最短的路径可能比另一种更步骤，这将在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

(B->D) = 2

（C-> E）= 1

(C->E) = 1

（D-> F）=（E-> F）= 0

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

在一步步推进，从A和退一步从楼正向边境是{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屋！