A Divide and Conquer Bidirectional Search: First Results

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 app li cation to gene sequence alignment in computational biology. Th e main id ea 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 algo rithm 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 algor ithm reduces the memory requirement from O(nd) to O(nd-l ). Th e time complexity only increases by a constant factor of 1r in two dimensions, and 7rV3/3 ::::::: 1.8 in three dimensions.