Iterative Deepening Dynamically Improved Bounds Bidirectional Search

John A. Pavlik (), Edward C. Sewell () and Sheldon H. Jacobson ()
Additional contact information
John A. Pavlik: Department of Computer Science, University of Illinois, Urbana, Illinois 61801
Edward C. Sewell: Department of Mathematics and Statistics, Southern Illinois University Edwardsville, Edwardsville, Illinois 62026
Sheldon H. Jacobson: Department of Computer Science, University of Illinois, Urbana, Illinois 61801

INFORMS Journal on Computing, 2022, vol. 34, issue 2, 974-989

Abstract: This paper presents a new bidirectional search algorithm to solve the shortest path problem. The new algorithm uses an iterative deepening technique with a consistent heuristic to improve lower bounds on path costs. The new algorithm contains a novel technique of filtering nodes to significantly reduce the memory requirements. Computational experiments on the pancake problem, sliding tile problem, and Rubik’s cube show that the new algorithm uses significantly less memory and executes faster than A* and other state-of-the-art bidirectional algorithms. Summary of Contribution: Quickly solving single-source shortest path problems on graphs is important for pathfinding applications and is a core problem in both artificial intelligence and operations research. This paper attempts to solve large problems that do not easily fit into the available memory of a desktop computer, such as finding the optimal shortest set of moves to solve a Rubik’s cube, and solve them faster than existing algorithms.

Keywords: bidirectional heuristic search; consistent heuristic; pancake; sliding tile; Rubik’s cube (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2021.1116 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:34:y:2022:i:2:p:974-989

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().