Enriching Non-Parametric Bidirectional Search Algorithms — Extended Abstract

Authors

  • Shahaf Shperberg Ben-Gurion University of the Negev
  • Ariel Felner Ben-Gurion University of the Negev
  • Nathan Sturtevant University of Alberta
  • Solomon Shimony Ben-Gurion University of the Negev
  • Avi Hayoun Ben-Gurion University of the Negev

DOI:

https://doi.org/10.1609/socs.v10i1.18488

Abstract

NBS is a non-parametric bidirectional search algorithm, proved to expand at most twice the number of node expansions required to verify the optimality of a solution. We introduce new variants of NBS that are aimed at finding all optimal solutions. We then introduce an algorithmic framework that includes NBS as a special case. Finally, we introduce DVCBS, a new algorithm in this framework that aims to further reduce the number of expansions. Unlike NBS, DVCBS does not have any worst-case bound guarantees, but in practice it outperforms NBS in verifying the optimality of solutions.

SoCS 2019 Proceedings Cover

Downloads

Published

2021-09-01

How to Cite

Shperberg, S., Felner, A., Sturtevant, N., Shimony, S., & Hayoun, A. (2021). Enriching Non-Parametric Bidirectional Search Algorithms — Extended Abstract. Proceedings of the International Symposium on Combinatorial Search, 10(1), 196–197. https://doi.org/10.1609/socs.v10i1.18488

Issue

Vol. 10 No. 1 (2019): Twelfth Annual Symposium on Combinatorial Search

Section

Extended Abstracts