Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Estimating the efficiency of backtrack programs
HTML articles powered by AMS MathViewer

by Donald E. Knuth PDF
Math. Comp. 29 (1975), 122-136 Request permission

Abstract:

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.
References
    F. DE CARTEBLANCHE, "The colored cubes problem," Eureka, v. 9, 1947, pp. 9-11. T. R. DAWSON, "Echecs Feeriques," problem 186, L’Echiquier, (2), v. 2, 1930, pp. 1085-1086; solution in L’Echiquier, (2), v. 3, 1931, p. 1150. T. R. DAWSON, Caissa’s Wild Roses, C. M. Fox, Surrey, England, 1935; reprinted in Five Classics of Fairy Chess, Dover, New York, 1973. T. R. DAWSON, "Chess facts and figures," Chess Pie III, souvenir booklet of the International chess tournament, Nottingham, 1936, pp. 34-36.
  • Paul J. Gans, Self-avoiding random walks. I. Simple properties of intermediate-length walks, J. Chem. Phys. 42 (1965), 4159–4163. MR 185685, DOI 10.1063/1.1695912
  • Solomon W. Golomb and Leonard D. Baumert, Backtrack programming, J. Assoc. Comput. Mach. 12 (1965), 516–524. MR 195585, DOI 10.1145/321296.321300
  • N. T. Gridgeman, The 23 Colored Cubes, Math. Mag. 44 (1971), no. 5, 243–252. MR 1571968, DOI 10.1080/0025570X.1971.11976161
  • Marshall Hall Jr. and D. E. Knuth, Combinatorial analysis and computers, Amer. Math. Monthly 72 (1965), no. 2, 21–28. MR 172812, DOI 10.2307/2313307
  • J. M. Hammersley and D. C. Handscomb, Monte Carlo methods, Methuen & Co., Ltd., London; Barnes & Noble, Inc., New York, 1965. MR 0223065
  • J. M. Hammersley and K. W. Morton, Poor man’s Monte Carlo, J. Roy. Statist. Soc. Ser. B 16 (1954), 23–38; discussion 61–75. MR 64475, DOI 10.1111/j.2517-6161.1954.tb00145.x
    • DONALD E. KNUTH, "Uncrossed knight’s tours," (letter to the editor), J. Recreational Math., v. 2, 1969, pp. 155-157.
  • Donald E. Knuth, The art of computer programming, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms. MR 0378456
    • DÉNES KÖNIG, Theorie der endlichen und unendlichen Graphen, Leipzig, 1936; reprint, Chelsea, New York, 1950.
  • E. L. Lawler and D. E. Wood, Branch-and-bound methods: A survey, Operations Res. 14 (1966), 699–719. MR 202469, DOI 10.1287/opre.14.4.699
    • DERRICK H. LEHMER, "Combinatorial problems with digital computers," Proc. Fourth Canadian Math. Congress (1957), Univ. of Toronto Press, Toronto, 1959, pp. 160-173. See also: Proc. Sympos. Appl. Math., vol. 6, Amer. Math. Soc., Providence, R. I., 1956, pp. 115, 124, 201. DERRICK H. LEHMER, "The machine tools of combinatorics," Chapter 1 in Applied Combinatorial Mathematics, edited by Edwin F. Beckenbach, Wiley, New York, 1964, pp. 5-31. ÉDOUARD LUCAS, Récréations Mathématiques, v. 1, Paris, 1882. MICHIO MATSUDA & S. KOBAYASHI, "Uncrossed knight’s tours," (letter to the editor), J. Recreational Math., v. 2, 1969, pp. 155-157. T. H. O’BIERNE, Puzzles and Paradoxes, Oxford Univ. Press, New York and London, 1965. C. B. TOMPKINS, review of "Random-number generating dice," by Japanese Standards Association, Math. Comp., v. 15, 1961, pp. 94-95.
  • R. J. Walker, An enumerative technique for a class of combinatorial problems, Proc. Sympos. Appl. Math., Vol. 10, American Mathematical Society, Providence, R.I., 1960, pp. 91–94. MR 0121306
  • Mark B. Wells, Elements of combinatorial computing, Pergamon Press, Oxford-New York-Toronto, Ont., 1971. MR 0277082
    • L. D. YARBROUGH, "Uncrossed knight’s tours," J. Recreational Math., v. 1, 1968, pp. 140-142.
Similar Articles
  • Retrieve articles in Mathematics of Computation with MSC: 68A20
  • Retrieve articles in all journals with MSC: 68A20
Additional Information
  • © Copyright 1975 American Mathematical Society
  • Journal: Math. Comp. 29 (1975), 122-136
  • MSC: Primary 68A20
  • DOI: https://doi.org/10.1090/S0025-5718-1975-0373371-6
  • MathSciNet review: 0373371