On the computational complexity of branch and bound search strategies
Loading...
Authors
Smith, Douglas R.
Subjects
Combinatorial Optimization
Branch and Bound
Complexity of Computation
Search Strategy
Tree Search
Probabilistic Modelling
Branch and Bound
Complexity of Computation
Search Strategy
Tree Search
Probabilistic Modelling
Advisors
Date of Issue
1979-11
Date
1979-11
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
Abstract
Many important problems in operations research, artificial intelligence, combinatorial algorithms, and other areas seem to require search in order to find an optimal solution. A branch and bound procedure, which imposes a tree structure on the search, is often the most efficient known means for solving these problems. While for some branch and bound algorithms a worst case complexity bound is known, the average case complexity is usually unknown despite the fact that it gives more information about the performance of the algorithm. In this dissertation the branch and bound method is discussed and a proabilistic model of its domain is given, namely a class of trees with an associated probability measure. The best bound first and depth-first search strategies are discusses and results on the expected time and space complexity of these strategies are presented and compared. The best-bound search strategy is shown to be optimal in both time and space. These results are illustrated by data from random traveling salesman problems. Evidence is presented which suggests that the asymmetric traveling salesman problem can be solved exactly in time O(nﾳlnﾲ(n)) on the
Type
Technical Report
Description
Series/Report No
Department
Organization
Operations Research (OR)
Graduate School of Operational and Information Sciences (GSOIS)
Identifiers
NPS Report Number
NPS-52-79-004
Sponsors
Prepared for: National Science Foundation; Washington, D.C. 20550
Funder
NSF Grant MCS74-14445-A01
Format
vii, 101 p.: ill. ; 28 cm.
Citation
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.