Divide-and-Conquer Bidirectional Search

Search Techniques for Problem Solving Under Uncertainty and Incomplete Information

Volume

Search Techniques for Problem Solving Under Uncertainty and Incomplete Information

Contents

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 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 in the middle of 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 middle node, and also between the middle node and the goal node.