ML Anthology

Bidirectional Search That Is Guaranteed to Meet in the Middle

Robert C. Holte, Ariel Felner, Guni Sharon, Nathan R. Sturtevant
AAAI 2016 pp. 3411-3417
doi:10.1609/AAAI.V30I1.10436 /aaai/2016/holte2016aaai-bidirectional/

Abstract

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.

PDF AAAI Semantic Scholar

Cite

Text

Holte et al. "Bidirectional Search That Is Guaranteed to Meet in the Middle." AAAI Conference on Artificial Intelligence, 2016. doi:10.1609/AAAI.V30I1.10436

Markdown

[Holte et al. "Bidirectional Search That Is Guaranteed to Meet in the Middle." AAAI Conference on Artificial Intelligence, 2016.](https://mlanthology.org/aaai/2016/holte2016aaai-bidirectional/) doi:10.1609/AAAI.V30I1.10436

BibTeX

@inproceedings{holte2016aaai-bidirectional,
  title     = {{Bidirectional Search That Is Guaranteed to Meet in the Middle}},
  author    = {Holte, Robert C. and Felner, Ariel and Sharon, Guni and Sturtevant, Nathan R.},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2016},
  pages     = {3411-3417},
  doi       = {10.1609/AAAI.V30I1.10436},
  url       = {https://mlanthology.org/aaai/2016/holte2016aaai-bidirectional/}
}