Estimating the efficiency of backtrack programs
Donald E. Knuth · Mathematics of Computation · 1975
One of the chief difficulties associated with the so-called backtracking technique for combinatorial problems has been our 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.
Cited by 251 works. doi:10.1090/s0025-5718-1975-0373371-6 Open-access PDF
Authors
References
- The Art of Computer Programming
- The Art of Computer Programming. Volume 1: Fundamental Algorithms.
- Branch-and-Bound Methods: A Survey
- Backtrack Programming
- Poor Man’s Monte Carlo
- Theorie Der Endlichen Und Unendlichen Graphen
- Elements of Combinatorial Computing
- An enumerative technique for a class of combinatorial problems
- Monte Carlo Methods.
- Combinatorial Analysis and Computers