Branch-and-Bound Search Algorithms and Their Computational Complexity.

Abstract

Branch-and-bound (BnB) is a general problem-solving paradigm that has been studied extensively in the areas of computer science and operations research, and has been employed to find optimal solutions to computation-intensive problems. Thanks to its generality, BnB takes many search algorithms, developed for different purposes, as special cases. Some of these algorithms, such as best-first search and depth-first search, are very popular, some, such as iterative deepening, recursive best-first search and constant-space best-first search, are known only in the artificial intelligence area. Because it was studied in different areas, BnB has been described under different formulations. The first part of this paper, we give comprehensive descriptions of the BnB method and of these search algorithms, consolidating the basic features of BnB. In the second part, we summarize recent theoretical development on the average-case complexity of BnB search algorithms.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1996
Accession Number
ADA314598

Entities

People

  • Weixiong Zhang

Organizations

  • University of Southern California

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Artificial Intelligence
  • Computational Complexity
  • Computations
  • Computer Science
  • Computers
  • Mathematics
  • Operations Research
  • Theoretical Computer Science

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Artificial Intelligence
  • Robotics and Automation.

Technology Areas

  • AI & ML
  • AI & ML - Machine Learning Algorithms
  • Space