Iterative Deepening Dynamically Improved Bounds Bidirectional Search

John A. Pavlik, Edward C. Sewell, Sheldon H. Jacobson

Research output: Contribution to journalArticlepeer-review


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 stateof- 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.

Original languageEnglish (US)
Pages (from-to)974-989
Number of pages16
JournalINFORMS Journal on Computing
Issue number2
StatePublished - Mar 2022


  • Rubik's cube
  • bidirectional heuristic search
  • consistent heuristic
  • pancake
  • sliding tile

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Science Applications
  • Management Science and Operations Research


Dive into the research topics of 'Iterative Deepening Dynamically Improved Bounds Bidirectional Search'. Together they form a unique fingerprint.

Cite this