Proceedings

A Divide and Conquer Bidirectional Search: First Results

Download BibTeX Cite

Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence. Search. Pages 1184-1190.

© 1999 International Joint Conferences on Artificial Intelligence

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.

  1. Carrillo, H., and D. Lipman, The multiple sequence alignment problem in biology, SIAM Journal of Ap- plied Mathematics, Vol. 48, No.5, October 1988, pp. 1073-1082.
  2. Dijkstra, E.W., A note on two problems in connex- ion with graphs, Numerische Mathematik, Vol. 1, 1959, pp. 269-71.
  3. Hirschberg, D.S., A linear space algorithm for com- puting maximal common subsequences, Communi- cations of the ACM, Vol. 18, No. 6, June, 1975, pp. 341-343.
  4. Hart, P.E., N.J. Nilsson, and B. Raphael, A formal basis for the heuristic determination of minimum cost paths, IEEE Transactions on Systems Science and Cybernetics, Vol. SSC-4, No. 2, July 1968, pp. 100-107.
  5. Ikeda, T., and H. Imai, Enhanced A* algorithms for multiple alignments: optimal alignments for sev- eral sequences and k-opt approximate alignments for large cases, Theoretical Computer Science, Vol. 210, 1998.
  6. Kernighan, B.W., and D.M. Ritchie, The C Pro- gramming Language, second edition, Prentice Hall, Englewood Cliffs, N.J., 1988.
  7. Korf, R.E., Space-efficient search algorithms, Com- puting Surveys, Vol. 27, No. 3, Sept., 1995, pp. 337- 339.
  8. Korf, R.E., Depth-first iterative-deepening: An op- timal admissible tree search, Artificial Intelligence, Vol. 27, No. 1, 1985, pp. 97-109.
  9. Korf, R.E., and D.M. Chickering, Best-first mini- max search, Artificial Intelligence, Vol. 84, No. 1-2, July 1996, pp. 299-337.
  10. Miura, T., and T. Ishida, Stochastic node caching for memory-bounded search, Proceedings of the Na- tional Conference on Artificial Intelligence { AAAI- 98), Madison, WI, July, 1998, pp. 450-456.
  11. Taylor, L., and R.E. Korf, Pruning duplicate nodes in depth-first search, Proceedings of the National Conference on Artificial Intelligence ( AAAI-93 ), Washington D.C., July 1993, pp. 756-761.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards