Estimating the efficiency of backtrack programs
Author:
Donald E. Knuth
Journal:
Math. Comp. 29 (1975), 122136
MSC:
Primary 68A20
MathSciNet review:
0373371
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: One of the chief difficulties associated with the socalled 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 branchandbound approach to combinatorial optimization.
 [1]
F. DE CARTEBLANCHE, "The colored cubes problem," Eureka, v. 9, 1947, pp. 911.
 [2]
T. R. DAWSON, "Echecs Feeriques," problem 186, L'Echiquier, (2), v. 2, 1930, pp. 10851086; 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. 3436.
 [5]
Paul
J. Gans, Selfavoiding random walks. I. Simple properties of
intermediatelength 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, 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. 155157.
 [12]
Donald
E. Knuth, The art of computer programming, 2nd ed.,
AddisonWesley Publishing Co., Reading, Mass.LondonAmsterdam, 1975.
Volume 1: Fundamental algorithms; AddisonWesley 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, Branchandbound 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. 160173. 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. 531.
 [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. 155157.
 [19]
T. H. O'BIERNE, Puzzles and Paradoxes, Oxford Univ. Press, New York and London, 1965.
 [20]
C. B. TOMPKINS, review of "Randomnumber generating dice," by Japanese Standards Association, Math. Comp., v. 15, 1961, pp. 9495.
 [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, 1971. MR
0277082 (43 #2819)
 [23]
L. D. YARBROUGH, "Uncrossed knight's tours," J. Recreational Math., v. 1, 1968, pp. 140142.
 [1]
 F. DE CARTEBLANCHE, "The colored cubes problem," Eureka, v. 9, 1947, pp. 911.
 [2]
 T. R. DAWSON, "Echecs Feeriques," problem 186, L'Echiquier, (2), v. 2, 1930, pp. 10851086; 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. 3436.
 [5]
 PAUL J. GANS, "Selfavoiding random walks. I. Simple properties of intermediatewalks," J. Chem. Phys., v. 42, 1965, pp. 41594163. MR 32 #3147. MR 0185685 (32:3147)
 [6]
 SOLOMON W. GOLOMB & LEONARD D. BAUMERT, "Backtrack programming," J. Assoc. Comput. Mach., v. 12, 1965, pp. 516524. MR 33 #3783. MR 0195585 (33:3783)
 [7]
 N. T. GRIDGEMAN, "The 23 colored cubes," Math. Mag., v. 44, 1971, pp. 243252. MR 1571968
 [8]
 MARSHALL HALL, JR. & D. E. KNUTH, "Combinatorial analysis and computers," Amer. Math. Monthly, v. 72, 1965, no. 2, part II, pp. 2128. MR 30 #3030. MR 0172812 (30:3030)
 [9]
 J. M. HAMMERSLEY & D. C. HANDSCOMB, Monte Carlo Methods, Methuen, London; Barnes & Noble, New York, 1965. MR 36 #6114. MR 0223065 (36:6114)
 [10]
 J. M. HAMMERSLEY & K. W. MORTON, "Poor man's Monte Carlo," J. Roy. Statist. Soc. Ser. B, v. 16, 1954, pp. 2328. MR 16, 287. MR 0064475 (16:287i)
 [11]
 DONALD E. KNUTH, "Uncrossed knight's tours," (letter to the editor), J. Recreational Math., v. 2, 1969, pp. 155157.
 [12]
 DONALD E. KNUTH, Fundamental Algorithms, The Art of Computer Programming, vol. 1, second edition AddisonWesley, Reading, Mass., 1973. 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 & D. E. WOOD, "Branchandbound methods: A survey," Operations Research, v. 14, 1966, pp. 699719. MR 34 #2338. 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. 160173. 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. 531.
 [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. 155157.
 [19]
 T. H. O'BIERNE, Puzzles and Paradoxes, Oxford Univ. Press, New York and London, 1965.
 [20]
 C. B. TOMPKINS, review of "Randomnumber generating dice," by Japanese Standards Association, Math. Comp., v. 15, 1961, pp. 9495.
 [21]
 R. J. WALKER, "An enumerative technique for a class of combinatorial problems," Proc. Sympos. Appl. Math., vol. 10, Amer. Math. Soc., Providence, R. I., 1960, pp. 9194. MR 22 #12048. MR 0121306 (22:12048)
 [22]
 MARK B. WELLS, Elements of Combinatorial Computing, Pergamon Press, Oxford and New York, 1971. MR 43 #2819. MR 0277082 (43:2819)
 [23]
 L. D. YARBROUGH, "Uncrossed knight's tours," J. Recreational Math., v. 1, 1968, pp. 140142.
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/S00255718197503733716
PII:
S 00255718(1975)03733716
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
