title: An empirical comparison of backtracking algorithms.
abstract: In this paper we report the results of experimental studies of zero-level, one-level, and two-level search rearrangement backtracking. We establish upper and lower limits for the size problem for which one-level backtracking is preferred over zero-level and two-level methods, thereby showing that the zero-level method is best for very small problems. The one-level method is best for moderate size problems, and the two-level method is best for extremely large problems. Together with our theoretical asymptotic formulas, these measurements provide a useful guide for selecting the best search rearrangement method for a particular problem.
authors.affiliation: Department of Computer Science, Indiana University, Bloomington, IN 47405.
authors.forename: C A
authors.initials: CA
authors.lastname: Brown
authors.forename: P W
authors.initials: PW
authors.lastname: Purdom