Proceedings:
Proceedings of the AAAI Conference on Artificial Intelligence, 12
Volume
Issue:
Search and Genetic Algorithms
Track:
Search
Downloads:
Abstract:
Previous approaches to bidirectional search require exponential space, and they are either less efficient than unidirectional search for finding optimal solutions, or they cannot even find such solutions for difficult problems. Based on a memory-bounded unidirectional algorithm for trees (SMA*), we developed a graph search extension, and we used it to construct a very efficient memory-bounded bidirectional algorithm. This bidirectional algorithm can be run for difficult problems with bounded memory. In addition, it is much more efficient than the corresponding unidirectional search algorithm also for finding optimal solutions to difficult problems. In summary, bidirectional search appears to be the best approach to solving difficult problems, and this indicates the extreme usefulness of a paradigm that was neglected for long.
AAAI
Search and Genetic Algorithms