Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

Estimating the efficiency of backtrack programs


Author: Donald E. Knuth
Journal: Math. Comp. 29 (1975), 122-136
MSC: Primary 68A20
MathSciNet review: 0373371
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] F. DE CARTEBLANCHE, "The colored cubes problem," Eureka, v. 9, 1947, pp. 9-11.
  • [2] 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.
  • [3] T. R. DAWSON, Caissa's Wild Roses, C. M. Fox, Surrey, England, 1935; reprinted in Five Classics of Fairy Chess, Dover, New York, 1973.
  • [4] T. R. DAWSON, "Chess facts and figures," Chess Pie III, souvenir booklet of the International chess tournament, Nottingham, 1936, pp. 34-36.
  • [5] Paul J. Gans, Self-avoiding random walks. I. Simple properties of intermediate-length walks, J. Chem. Phys. 42 (1965), 4159–4163. MR 0185685 (32 #3147)
  • [6] Solomon W. Golomb and Leonard D. Baumert, Backtrack programming, J. Assoc. Comput. Mach. 12 (1965), 516–524. MR 0195585 (33 #3783)
  • [7] N. T. Gridgeman, The 23 Colored Cubes, Math. Mag. 44 (1971), no. 5, 243–252. MR 1571968
  • [8] Marshall Hall Jr. and D. E. Knuth, Combinatorial analysis and computers, Amer. Math. Monthly 72 (1965), no. 2, 21–28. MR 0172812 (30 #3030)
  • [9] J. M. Hammersley and D. C. Handscomb, Monte Carlo methods, Methuen & Co., Ltd., London; Barnes & Noble, Inc., New York, 1965. MR 0223065 (36 #6114)
  • [10] 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 0064475 (16,287i)
  • [11] DONALD E. KNUTH, "Uncrossed knight's tours," (letter to the editor), J. Recreational Math., v. 2, 1969, pp. 155-157.
  • [12] Donald E. Knuth, The art of computer programming, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR 0378456 (51 #14624)
  • [13] DÉNES KÖNIG, Theorie der endlichen und unendlichen Graphen, Leipzig, 1936; reprint, Chelsea, New York, 1950.
  • [14] E. L. Lawler and D. E. Wood, Branch-and-bound methods: A survey, Operations Res. 14 (1966), 699–719. MR 0202469 (34 #2338)
  • [15] 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.
  • [16] 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.
  • [17] ÉDOUARD LUCAS, Récréations Mathématiques, v. 1, Paris, 1882.
  • [18] MICHIO MATSUDA & S. KOBAYASHI, "Uncrossed knight's tours," (letter to the editor), J. Recreational Math., v. 2, 1969, pp. 155-157.
  • [19] T. H. O'BIERNE, Puzzles and Paradoxes, Oxford Univ. Press, New York and London, 1965.
  • [20] C. B. TOMPKINS, review of "Random-number generating dice," by Japanese Standards Association, Math. Comp., v. 15, 1961, pp. 94-95.
  • [21] 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 (22 #12048)
  • [22] Mark B. Wells, Elements of combinatorial computing, Pergamon Press, Oxford-New York-Toronto, Ont., 1971. MR 0277082 (43 #2819)
  • [23] 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

DOI: http://dx.doi.org/10.1090/S0025-5718-1975-0373371-6
PII: S 0025-5718(1975)0373371-6
Keywords: Backtrack, analysis of algorithms, Monte Carlo method, Instant Insanity, color cubes, knight's tours, tree functions, branch and bound
Article copyright: © Copyright 1975 American Mathematical Society