Estimating the Efficiency of Backtrack Programs.
Abstract
One of the chief difficulties associated with the so-called backtracking technique for combinatorial problems has been the inability to predict the efficiency of a given algorithm, or to compare the efficiencies of different approaches, without actually writing and running the programs. This paper presents a simple method which produces reasonable estimates for most applications, requiring only a modest amount of hand calculation. The method should prove to be of considerable utility in connection with D. H. Lehmer's branch-and-bound approach to combinatorial optimization.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1974
- Accession Number
- ADA004208
Entities
People
- Donald Knuth
Organizations
- Stanford University