Divide-and-Conquer Bidirectional

We present a new algorithm to reduce the space complexity of heuristic search. It is most effec-tive for problem spaces that grow polynomi-ally with problem size, but contain large num-bers 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 ini-tial node and the middle node, and also be-tween the middle 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(nd) to O(nd-1). For example, in a two-dimensional problem, the space complexity is reduced from quadratic to linear. The time complexity only increases by a constant factor of ~r in 2 dimen-sions, and ~rv/3/3 ~ 1.8 in 3 dimensions.