Accession Number : ADA314598

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

Descriptive Note : Research rept.,

Corporate Author : UNIVERSITY OF SOUTHERN CALIFORNIA MARINA DEL REY INFORMATION SCIENCES INST

Personal Author(s) : Zhang, Weixiong

PDF Url : ADA314598

Report Date : MAY 1996

Pagination or Media Count : 37

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.

Descriptors :   *ALGORITHMS, *OPTIMIZATION, COMPUTATIONS, QUEUEING THEORY, ACCURACY, PROBLEM SOLVING, RECURSIVE FUNCTIONS, SYSTEMS ANALYSIS, DYNAMIC PROGRAMMING, ITERATIONS, STRUCTURED PROGRAMMING.

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE