On the Computational Complexity of Branch and Bound Search Strategies.
Abstract
Many important problems in operations research, artificial intelligence, and other areas of computer science 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 algorithm 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 probabilistic model of its domain is given, namely a class of trees with an associated probability measure. The best-bound-first search strategy and depth-first search strategy are discussed and results on the expected time and space complexity of these strategies are presented and discussed. The best-bound-first search strategy is shown to be optimal in both time and space. These results are illustrated by data from randomly generated traveling salesman problems.
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1979
- Accession Number
- ADA081608
Entities
People
- Douglas R. Smith
Organizations
- Naval Postgraduate School