Two new bidirectional search algorithms

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

Research output: Contribution to journalArticlepeer-review

Abstract

This paper presents two new bidirectional heuristic search algorithms for solving the shortest path problem on graphs: consistent-heuristic bucket-based bidirectional search (CBBS) and front-to-front GPU bidirectional search (FFGBS). CBBS uses a consistent heuristic and groups nodes into buckets that organize nodes based on estimated path cost and known heuristic errors. FFGBS splits the work between the CPU and GPU, with the GPU solving a front-to-front heuristic and the CPU choosing nodes to expand. This paper also includes a new front-to-front version of the GAP heuristic for the pancake problem that is efficient to solve on a GPU. Computational experiments for CBBS are performed on the pancake problem. CBBS is faster and requires less node expansions with the GAP-1 heuristic, compared to bidirectional state of the algorithms like DIBBS and DVCBS. Computational experiments for FFGBS are performed on the pancake problem and DIMACS road network, showing that FFGBS is consistently the fastest algorithm on all but the smallest pancake stacks when using the GAP-2 heuristic and is also the fastest algorithm on the largest road networks.

Original languageEnglish (US)
Pages (from-to)377-409
Number of pages33
JournalComputational Optimization and Applications
Volume80
Issue number2
DOIs
StatePublished - Nov 2021

Keywords

  • Bidirectional search
  • Consistent heuristic
  • Discrete algorithm
  • Heuristic search
  • Pancake
  • Road

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Two new bidirectional search algorithms'. Together they form a unique fingerprint.

Cite this