Bidirectional Search That Is Guaranteed to Meet in the Middle
DOI:
https://doi.org/10.1609/aaai.v30i1.10436Keywords:
Artificial Intelligence, Heuristic SearchAbstract
We present MM, the first bidirectional heuristic search algorithm whose forward and backward searches are guaranteed to ''meet in the middle'', i.e. never expand a node beyond the solution midpoint. We also present a novel framework for comparing MM, A*, and brute-force search, and identify conditions favoring each algorithm. Finally, we present experimental results that support our theoretical analysis.
Downloads
Published
2016-03-05
How to Cite
Holte, R., Felner, A., Sharon, G., & Sturtevant, N. (2016). Bidirectional Search That Is Guaranteed to Meet in the Middle. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1). https://doi.org/10.1609/aaai.v30i1.10436
Issue
Section
Technical Papers: Search and Constraint Satisfaction