Colloquium Details
Divide-and-Conquer Bidirectional Search
| Author: | Richard Korf University of California, Los Angeles |
|---|---|
| Date: | October 14, 1999 |
| Time: | 16:00 |
| Location: | 220 Deschutes |
| Host: | Matt Ginsberg |
Abstract
We present a new algorithm to reduce the space complexity of heuristic search. It is most effective for problem spaces that grow polynomially with problem size, but contain large numbers of short cycles. For example, the problem of finding a lowest-cost corner-to-corner path in a d-dimensional grid has application to gene sequence alignment in computational biology. The main idea is to perform a bidirectional search, but saving only the Open lists and not the Closed lists. Once the search completes, we have one node on an optimal path, but don't have the solution path itself. The path is then reconstructed by recursively applying the same algorithm between the initial node and the intermediate node, and also between the intermediate node and the goal node. If $n$ is the length of the grid in each dimension, and $d$ is the number of dimensions, this algorithm reduces the memory requirement from $O(n^d)$ to $O(n^{d-1})$. The time complexity only increases by a constant factor of $\pi$ in two dimensions, and $\pi/\sqrt{3}\approx 1.8$ in three dimensions.