If uniform cost search is used for bidirectional search, is it guaranteed the solution is optimal?

Question

If uniform cost search is used for both the forward and backward search in bidirectional search, is it guaranteed the solution is optimal?

Answer 1

UCS is optimal (but not necessarily complete)

Let's first recall that the uniform-cost search (UCS) is optimal (i.e. if it finds a solution, which is not guaranteed unless the costs on the edges are big enough, that solution is optimal) and it expands nodes with the smallest value of the evaluation function $f(n) = g(n)$, where $g(n)$ is the length/cost of the path from the goal/start node to $n$.

Is bidirectional search with UCS optimal?

The problem of bidirectional search with UCS for the forward and backward searches is that UCS does not proceed layer-by-layer (as breadth-first search does, which ensures that when the forward and backward searches meet, the optimal path has been found, assuming they both expand one level at each iteration), so the forward search may explore one part of the search space while the backward search may explore a different part, and it could happen (although I don't have the proof: I need to think about it a little bit more!), that these searches do not meet. So, I will consider both cases:

• when the forward and backward searches do not "meet" (the worst case, in terms of time and space complexity)

• when they meet (the non-degenerate case)

Degenerate case

Let's consider the case when the forward search does not meet the backward search (the worst/degenarate case).

If we assume that the costs on the edges are big enough and the start node $s$ is reachable from $g$ (or vice-versa), then bidirectional search eventually degenerates to two independent uniform-cost searches, which are optimal, which makes BS optimal too.

Non-generate case

Let's consider the case when the forward search meets the backward search.

To ensure optimality, we cannot just stop searching when we take off both the frontiers the same $n$. To see why, consider this example. We take off the first frontier node $n_1$ with cost $N$, then we take off the same frontier node $n_2$ with cost $N+10$. Meanwhile, we take off the other frontier node $n_2$ with cost $K$ and the node $n_1$ with cost $K + 1$. So, we have two paths: one with cost $N+(K + 1)$ and one with cost $(N+10)+K$, which is bigger than $N+(K + 1)$, but we took off both frontiers $n_2$ first.

See the other answer for more details and resources that could be helpful to understand the appropriate stopping condition for the BS.

Answer 2

It depends on the stopping condition. If the stopping condition is "stop as soon as any vertex is encountered by both the forward and backward scan", then bidirectional uniform-cost search is not a correct algorithm -- it is not guaranteed to output the optimal path. But it is possible to adjust the stopping condition to make bidirectional uniform-cost search guaranteed to output an optimal solution.

See the following resources for details, and the correct stopping condition:

Computing Point-to-Point Shortest Paths from External Memory. Andrew V. Goldberg, Renato F. Werneck. ALENEX/ANALCO 2005.

Point-to-point shortest path algorithms with preprocessing. Andrew V. Goldberg. International Conference on Current Trends in Theory and Practice of Computer Science, 2007.

Efficient Point-to-Point Shortest Path Algorithms. Andrew V. Goldberg, Chris Harrelson, Haim Kaplan, Renato F. Wemeck.

I found these resources by looking at the Wikipedia article on bidirectional search; it mentions that the termination condition has been articulated by Andrew Goldberg et al and cites the third reference above. Then a quick search on Google Scholar immediately turned up the other papers as well.

Lesson for the future: It can be useful to spend a little time checking standard resources (such as Wikipedia and textbooks), and checking the literature (e.g., with Google Scholar). Many natural questions have already been answered in the literature.