Richard E. Korf
Abstract
The critical resource that limits the application of best-first search is memory. We present a new class of best-first search algorithms that reduce the space complexity. The key idea is to store only the Open list of generated nodes, but not the Closed list of expanded nodes. The solution path can be recovered by a divide-and-conquer technique, either as a bidirectional or unidirectional search. For many problems, frontier search dramatically reduces the memory required by best-first search. We apply frontier search to breadth-first search of sliding-tile puzzles and the 4-peg Towers of Hanoi problem, Dijkstra's algorithm on a grid with random edge costs, and the A* algorithm on the Fifteen Puzzle, the four-peg Towers of Hanoi Problem, and optimal sequence alignment in computational biology.
- Araki, S., Goshima, M., Mori, S., Nakashima, H., and Tomita, S. 1999. Application of parallelized DP and A* algorithm to multiple sequence alignment. In Proceedings of the Genome Informatics Workshop IV, 94--102.Google Scholar
- Bode, J.-P., and Hinz, A. 1999. Results and open problems on the Tower of Hanoi. In Proceedings of the 30th Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL). Congressus Numerantium, Vol. 139. 112--122.Google Scholar
- Brungger, A., Marzetta, A., Fukuda, K., and Nievergelt, J. 1999. The parallel search bench ZRAM and its applications. Ann. Oper. Res. 90, 45--63.Google Scholar
- Chakrabarti, P., Ghose, S., Acharya, A., and de Sarkar, S. 1989. Heuristic search in restricted memory. Artif. Intell. 41, 2 (Dec.), 197--221. Google Scholar
- Culberson, J., and Schaeffer, J. 1998. Pattern databases. Computat. Intell. 14, 3, 318--334.Google Scholar
- Dijkstra, E. 1959. A note on two problems in connexion with graphs. Numer. Math. 1, 269--271.Google Scholar
- Dudeney, H. 1908. The Canterbury Puzzles (and Other Curious Problems). E.P. Dutton, New York.Google Scholar
- Dunkel, O. 1941. Editorial note concerning advanced problem 3918. Amer. Math. Month. 48, 219.Google Scholar
- Felner, A., Korf, R., and Hanan, S. 2004. Additive pattern database heuristics. J. Artif. Intell. Res. 22, 279--318. Google Scholar
- Felner, A., Meshulam, R., Holte, R., and Korf, R. 2004. Compressing pattern databases. In Proceedings of the 19th National Conference on Artificial Intelligence (AAAI-04) (San Jose, CA). 638--643. Google Scholar
- Frame, J. 1941. Solution to advanced problem 3918. Amer. Math. Month. 48, 216--217.Google Scholar
- Ghosh, S., Mahanti, A., and Nau, D. 1994. ITS: An efficient limited-memory heuristic tree search algorithm. In Proceedings of the 12th National Conference on Artificial Intelligence (AAAI-94) (Seattle, WA). 1353--1358. Google Scholar
- Hart, P., Nilsson, N., and Raphael, B. 1968. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cyber. SSC-4, 2 (July), 100--107.Google Scholar
- Hirschberg, D. 1975. A linear space algorithm for computing maximal common subsequences. Commun. ACM 18, 6 (June), 341--343. Google Scholar
- Hirschberg, D. 1997. Serial computations of levenshtein distances. In Pattern Matching Algorithms, A. Apostolic and Z. Galil, Eds. Oxford University Press, Oxford, England, 123--141. Google Scholar
- Hohwald, H., Thayer, I., and Korf, R. 2003. Comparing best-first search and dynamic programming for optimal multiple sequence alignment. In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI-03) (Acapulco, Mexico). 1239--1245. Google Scholar
- Ikeda, T., and Imai, H. 1999. Enhanced A* algorithms for multiple alignments: Optimal alignments for several sequences and k-opt approximate alignments for large cases. Theoret. Comput. Sci. 210, 341--374. Google Scholar
- Johnson, W., and Storey, W. 1879. Notes on the 15 Puzzle. Amer. J. Math. 2, 397--404.Google Scholar
- Kaindl, H., and Kainz, G. 1997. Bidirectional heuristic search reconsidered. J. Artif. Intell. Res. 7, 283--317. Google Scholar
- Klavzar, S., and Milutinovic, U. 2002. Simple explicit formulas for the Frame- Stewart numbers. Ann. Combinat. 6, 157--167.Google Scholar
- Korf, R. 1985. Depth-first iterative-deepening: An optimal admissible tree search. Artif. Intell. 27, 1 (Sept.), 97--109. Google Scholar
- Korf, R. 1993. Linear-space best-first search. Artif. Intell. 62, 1 (July), 41--78. Google Scholar
- Korf, R. 1999. Divide-and-conquer bidirectional search: First results. In Proceedings of the 16th International Joint Conference on Artificial Intelligence (IJCAI-99) (Stockholm, Sweden). 1184--1189. Google Scholar
- Korf, R. 2003. Delayed duplicate detection: Extended abstract. In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI-03) (Acapulco, Mexico). 1539--1541. Google Scholar
- Korf, R. 2004. Best-first frontier search with delayed duplicate detection. In Proceedings of the 19th National Conference on Artificial Intelligence (AAAI-2004) (San Jose, CA). 650--657. Google Scholar
- Korf, R. 2005. Large-scale parallel breadth-first search. In Proceedings of the 20th National Conference on Artificial Intelligence (AAAI-2005) (Pittsburgh, PA), 1380--1385. Google Scholar
- Korf, R., and Chickering, D. 1996. Best-first minimax search. Artif. Intell. 84, 1-2 (July), 299--337. Google Scholar
- Korf, R., Reid, M., and Edelkamp, S. 2001. Time complexity of Iterative- Deepening- A*. Artif. Intell. 129, 1--2 (June), 199--218. Google Scholar
- Korf, R., and Zhang, W. 2000. Divide-and-conquer frontier search applied to optimal sequence alignment. In Proceedings of the 17th National Conference on Artificial Intelligence (AAAI-00) (Austin, TX). 910--916. Google Scholar
- Lermen, M., and Reinert, K. 2000. The practical use of the A* algorithm for exact multiple sequence alignment. J. Computat. Biol. 7, 5, 655--671.Google Scholar
- Needleman, S., and Wunsch, C. 1970. A general method applicable to the search for similarities in the amino acid sequences of two proteins. J. Molec. Biol. 48, 443--453.Google Scholar
- Pearl, J. 1984. Heuristics. Addison-Wesley, Reading, MA.Google Scholar
- Pohl, I. 1970. Heuristic search viewed as path finding in a graph. Artif. Intell. 1, 193--204.Google Scholar
- Pohl, I. 1971. Bi-directional search. In Machine Intelligence 6, B. Meltzer and D. Michie, Eds. American Elsevier, New York, 127--140.Google Scholar
- Reinefeld, A. 1993. Complete solution of the Eight Puzzle and the benefit of node ordering in IDA*. In Proceedings of the 13th International Joint Conference on Artificial Intelligence (IJCAI-93) (Chambery, France). 248--253.Google Scholar
- Rudin, H. 1987. Network protocols and tools to help produce them. In Annual Review of Computer Science, J. Traub, B. Grosz, B. Lampson, and N. Nilsson, Eds. Annual Reviews Inc., Palo Alto, CA, 291--316.Google Scholar
- Russell, S. 1992. Efficient memory-bounded search methods. In Proceedings of the 10th European Conference on Artificial Intelligence (ECAI-92) (Vienna, Austria). 1--5. Google Scholar
- Schofield, P. 1967. Complete solution of the Eight Puzzle. In Machine Intelligence 3, B. Meltzer and D. Michie, Eds. American Elsevier, New York, 125--133.Google Scholar
- Sen, A., and Bagchi, A. 1989. Fast recursive formulations for best-first search that allow controlled use of memory. In Proceedings of the 11th International Joint Conference on Artificial Intelligence (IJCAI-89) (Detroit, MI). 297--302.Google Scholar
- Setubal, J., and Meidanis, J. 1997. Introduction to Computational Molecular Biology. PWS Publishing, Boston, MA.Google Scholar
- Spouge, J. 1989. Speeding up dynamic programming algorithms for finding optimal lattice paths. SIAM J. Appl. Math. 49, 5, 1552--1566. Google Scholar
- Stewart, B. 1941. Solution to advanced problem 3918. Amer. Math. Monthly 48, 217--219.Google Scholar
- Taylor, L., and Korf, R. 1993. Pruning duplicate nodes in depth-first search. In Proceedings of the 11th National Conference on Artificial Intelligence (AAAI-93) (Washington, DC). 756--761.Google Scholar
- Thayer, I. 2003. Methods for optimal multiple sequence alignment. M.S. dissertation. Computer Science Department, University of California, Los Angeles, CA.Google Scholar
- Thomson, J., Plewniak, F., and Poch, O. 1999. BAli BASE: A benchmark alignment database for the evaluation of multiple alignment programs. Bioinformatics 15, 1, 87--88.Google Scholar
- Ukkonen, E. 1985. Algorithms for approximate string matching. Info. Contr. 64, 100--118. Google Scholar
- Yoshizumi, T., Miura, T., and Ishida, T. 2000. A* with partial expansion for large branching factor problems. In Proceedings of the 17th National Conference on Artificial Intelligence (AAAI-00) (Austin, TX). 923--929. Google Scholar
- Zhou, R., and Hansen, E. 2002. Multiple sequence alignment using anytime A*. In Proceedings of the 18th National Conference on Artificial Intelligence (AAAI-02) (Edmonton, Alberta, Canada). 975--976. Google Scholar
- Zhou, R., and Hansen, E. 2003a. Sparse-memory graph search. In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI-03) (Acapulco, Mexico). 1259--1266. Google Scholar
- Zhou, R., and Hansen, E. 2003b. Sweep-A*: Space-efficient heuristic search in partially ordered graphs. In Proceedings of the 15th International Conference on Tools with Artificial Intelligence (ICTAI-03) (Sacramento, CA). 427--434. Google Scholar
- Zhou, R., and Hansen, E. 2004. Breadth-first heuristic search. In Proceedings of the 14th International Conference on Automated Planning and Scheduling (ICAPS-04) (Whistler, British Columbia, Canada). 92--100.Google Scholar
Index Terms
- Frontier search
Recommendations
Linear-time disk-based implicit graph search
Many search algorithms are limited by the amount of memory available. Magnetic disk storage is over two orders of magnitude cheaper than semiconductor memory, and individual disks can hold up to a terabyte. We augment memory with magnetic disks to ...
Applying the various optimal solution search methods to multiple sequence alignments and performance evaluation
In this paper, we applied various optimal solution search methods from the field of artificial intelligence to multiple sequence alignment, which is a basic problem of sequence analysis in the field of bioinformatics, to conduct performance evaluation ...
Stochastic Modeling of Branch-and-Bound Algorithms with Best-First Search
Special issue on COMPSAC 1982 and 1983Branch-and-bound algorithms are organized and intelligently structured searches of solutions in a combinatorially large problem space. In this paper, we propose an approximate stochastic model of branch-and-bound algorithms with a best-first search. We ...
Reviews
Carlos Linares Lopez
Currently, researchers are working to improve the performance of single-agent search algorithms in two ways: they are devising new ideas for deriving new search algorithms with lower asymptotic space complexities, and they are figuring out how to automatically improve the accuracy of heuristic functions. Though bidirectional search seemed to be a promising line of research, it was finally shown that this approach had some intrinsic drawbacks. Therefore, a different class of unidirectional search algorithms, depth-first single-agent search algorithms, received renewed attention. Unfortunately, depth-first search algorithms cannot detect all of the repeated states. Therefore, the authors have turned their attention to best-first search algorithms. The key idea behind this paper consists of saving the memory used by best-first search algorithms to store the closed list in a wide variety of cases. The resulting algorithm, frontier search, "dramatically reduces the memory required by best-first search," and preserves admissibility. In the general formulation, a bit representation of the operators is used to generate the open nodes while avoiding regeneration of the closed nodes. The procedure for coming up with the optimal solution relies on either geometric properties of the domain or some specific properties of the heuristic function employed. The empirical results of the frontier search are impressive. The authors devote large sections of the paper to discussions of the performance of their idea, and compare it with some other search algorithms, including the four-peg Towers of Hanoi problem, various sizes of the N-puzzle problem, shortest paths in grids, and multiple sequence alignment. In all cases, frontier search largely outperformed the other search algorithms. Overall, the paper is very well written, and is highly recommended not only for the importance and impact of the ideas introduced, but also for the thorough review of the current state of the art that it offers. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments