algorithm - Termination Criteria for Bidirectional Search

Question

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.

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?

Edit: 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.

Answer 1

I think it has to do with how bidirectional search is implemented.

The pseudocode for BFS goes something like this:

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

Imagine implementing bidirectional search like this:

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

Basically, alternating steps of "forward" BFS and "backwards" BFS. Now imagine a graph like this:

    B-C-D
  /       
A           E
         /
    F - G

The first forward and backward runs of BFS would give us a state like this:

1) expandedForward = A ; frontierForward = B, F
2) expandedBackward = E ; frontierBackward = D, G

Now the algorithm picks the next node to expand from the forward frontier and it picks B.

3) expandedForward = A, B ; frontierForward = F, C

Now we run a backwards BFS and expand node D. D's child, C, is in the forward frontier, so we return the path A - B - C - D - E.

I think this is what Russel and Norvig where referring to. If the implementation doesn't consider this scenario it could give you a solution that's not optimal.

It should finish expanding all the nodes in the frontier that have the same "depth" before deciding it has found an optimal solution. Or maybe alternate the forward and backward BFS searches by layer and not by node (expand forward all nodes in layer 0, expand backward all nodes in layer 0, expand forward all nodes in layer 1, etc.)