Comparison of the number of nodes explored by cyclic best first search with depth contour and best first search

Wenda Zhang, Jason J. Sauppe, Sheldon H. Jacobson

Research output: Contribution to journalArticlepeer-review

Abstract

Search strategies are used in Branch-and-bound (B&B) algorithms to determine the order to process the nodes in a search tree. A search strategy that has seen frequent success in B&B algorithms is Best First Search (BFS). However, a new search strategy called Cyclic Best First Search with depth contour (CBFS-depth) has been shown to consistently process fewer nodes than BFS on several combinatorial optimization problems. In this paper, we study the properties of search trees under which CBFS-depth may outperform BFS in terms of the average number of nodes explored to prove optimality. To facilitate the study, a search tree model is proposed for minimization problems solved by B&B algorithms which is based on the distributions of nodes in the tree with different lower bounds. Using this model, we estimate the expected number of nodes expanded by CBFS-depth. Additionally, we apply B&B algorithms using both search strategies to trees that are randomly generated according to the proposed model in order to study how the average number of nodes expanded by each search strategy is affected by the search tree. Finally, both search strategies are tested on existing optimization problems to validate the observations from the randomly generated search trees.

Original languageEnglish (US)
Article number105129
JournalComputers and Operations Research
Volume126
DOIs
StatePublished - Feb 2021
Externally publishedYes

Keywords

  • Branch-and-bound algorithm
  • Cyclic best-first search
  • Performance comparison
  • Search strategies

ASJC Scopus subject areas

  • General Computer Science
  • Modeling and Simulation
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'Comparison of the number of nodes explored by cyclic best first search with depth contour and best first search'. Together they form a unique fingerprint.

Cite this