An Empirical Comparison of Backtracking Algorithms

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. PAMI-4, NO. 3, MAY 1982

309

pictures form simple polygons, since the sampling process often results in collinear points.

REFERENCES [1] W. E. Snyder and D. A. Tang, "Finding the extrema of a region,"

IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-2, pp. 266269, May 1980.

b

L

Fig. 5. Illustrating the proof of the theorem.

REFERENCES [11 W. E. Snyder and D. A. Tang, "Finding the extrema of a region," IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-2, pp. 266269, May 1980. [2] M. I. Shamos, "Geometric complexity," in Proc. 7th ACM Symp. Theory of Comput., May 1975, pp. 224-233.

[31 D. P. Dobkin and L. Snyder, "On a general method for maximiz[4]

[5] [6] [7] [8]

ing and minimizing among certain geometric problems," in Proc. 20th Annu. Symp. Foundations Comput. Sci., San Juan, Puerto Rico, Oct. 1979, pp. 9-17. D. McCallum and D. Avis, "A linear algorithm for finding the convex hull of a simple polygon," Inform. Process. Lett., vol. 9, pp. 201-206, Dec. 1979. J. Jacobsen, "Biomedical computer analysis of cells," in Proc. 1 7th Annu. Conf Eng. in Med. Biol., 1964, p. 117. M. A. Fischler, "Fast algorithms for two maximal distance problems with applications to image analysis," Pattern Recog., vol. 12, pp. 35-40, 1980. G. T. Toussaint, "Pattern recognition and geometrical complexity," in Proc. 5th Int. Conf. Pattern Recog., Miami Beach, FL, Dec. 1980, pp. 1324-1347. D. Avis, G. T. Toussaint, and B. K. Bhattacharya, "On the multimodality distances in convex polygons," Comput. Math. Appl., to be published.

Comments on "A Counterexample to a Diameter Algorithm for Convex Polygons" W. E. SNYDER AND D. A. TANG In our paper [ 1 ] we described an algorithm which efficiently found the diameter of arbitrary regions, convex or concave, simple or not, filled (boundary not identified) or not. In our enthusiastic desire to describe this very general and very efficient algorithm, we described, for completeness, some more simple algorithms to handle some of the more simple and "uninteresting" (to us) cases, such as convex polygons. Unfortunately, one of those "more simple" cases was in fact not so simple, and Bhattacharya and Toussaint' have very accurately pointed out a condition under which one of the simple techniques we described fails. We are very grateful to them for that observation. It should be noted, however, that this flaw does not propagate to our general algorithm, which converges to the diameter for arbitrary regions. As one further note, it has been our experience that it is unreasonable to assume the boundaries of regions in digital Manuscript received November 16, 1981. The authors are with the Department of Electrical Engineering, North Carolina State University, Raleigh, NC 27607. 1B. K. Bhattacharya and G. T. Toussaint, this issue, pp. 306-309.

An Empirical Comparison of Backtracking Algorithms CYNTHIA A. BROWN AND PAUL W. PURDOM, JR.

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 onelevel backtracking is preferred over zero-evel and two-level methods, thereby showing that the zero-level method is best for very small probleins. The one-level method is best for moderate size problems, and the two-evel 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. Index Terms-Backtracking, constraint satisfaction, search algorithms,

tree search.

I. INTRODUCTION An important task of computer scientists is devising general algorithms that can be used to solve any problem from a large set of related problems. Such sets of problems can be divided into two classes, sometimes called "easy" and "hard." The easy sets are those for which each problem in the set can be solved within a time which is a polynomial function of the problem size. An example of such an easy set is the computation of the shortest path between two nodes in a graph. An individual problem in the set consists of a graph whose arcs have nonnegative labels and a distinguished pair of vertices. There are wellknown general methods for solving any problem in this set in a time proportional to the square of the number of nodes in the graph [ 7 1. For naturally occurring easy problem sets, the degree of the polynomial time bound is usually no greater than three, so rapid solution of large problems is possible. A hard problem set is one for which the best known algorithm takes more than polynomial time for some sequence of problems in the set. (For some hard problem sets, there are solution methods with small average time.) Many important hard problem sets are NP complete. Garey and Johnson [8] give a thorough discussion of the NP complete class and list many NP complete problem sets. An examination of the problems listed by Garey and Johnson shows that most of them have a natural representation as a predicate of the form p1

A

I < i< m

Ri(w,x

* *

*, Wv)

(1)

where each R is a relation that is simple in the sense that it depends on only a few of the variables and each w has a finite Manuscript received March 25, 1981; revised November 3, 1981. This work was supported in part by the National Science Foundation under Grant MCS 7906110. The authors are with the Department of Computer Science, Indiana University, Bloomington, IN 47405.

0162-8828/82/0500-0309$00.75 © 1982 IEEE

310

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. PAMI-4, NO. 3, MAY 1982

number of possible values. Moreover, the work of Cook [51 and Karp [ 151 shows that solving any NP problem is equivalent to determining the satisfiability of a conjunctive normal form (CNF) predicate with three literals per term where the size of the CNF formula is polynomially related to the size of the original problem. This means that any hard problem in NP can be represented in the form of (1), using simple relations for the R 's. Fast general methods for solving problems of form (1) would be useful for any NP complete set. (See also [ 11 1.) Problems of form (1) where each R depends on a small number of variables are called constrained labeling problems by some authors. Each R is then called a constraint, each v a unit, and each possible value for a unit is called a label. The problem is NP complete even when each R depends on only two variables and each variable has only three possible values [ 18 or when each R depends on three variables and each variable has two possible values [5] . Backtracking is a natural general method for solving problems of form (1) (as well as more difficult problems, such as alternating Turing machine computations [4], that have a similar structure). We have described our theoretical analyses of various backtracking algorithms elsewhere [21, [191. Here we report on empirical studies of these algorithms. The algorithms measured are the most efficient known simple methods for solving many moderate size problems from NP complete sets. The results of these studies, in conjunction with our theoretical work, providepractical criteria for selecting the most appropriate backtracking algorithm for a particular problem. Tree size estimation [ 161, [ 17] can then be used to judge how long the chosen method will take. The remainder of this paper is organized as follows. Section indicates some of the types of backtracking that have been IIstudied by us and other investigators and summarizes the current theoretical results on their average running time. Section III gives a more detailed description of the search rearrangement algorithms whose performance we measured. Section IV discusses the model problem set on which the average performance of the algorithms was measured. Section V is a discussion of our experimental techniques, and the results are given in Section VI. Section VII presents our conclusions.

II. BACKTRACKING Consider a problem that is expressed as a predicate P in form (1). A solution of the problem is a set of values W1, -, Wn for wl, *, w, that make P true. An intermediate predicate *, W1) is w, Wj) for P is a predicate such that Pj(w1, false only if P does not have a solution with wi = W1,*, w; = Wi. (When Pj is true, P still may not have such a solution.) An obvious choice for Pi is the conjunction of all the relations R If the intermediate predicates that depend only on w1, , are frequently false, they can be used to greatly increase the efficiency of a search for solutions to P, using simple backtracking. In simple backtracking, we begin with all the variables unset (they may be regarded as having a special value, "undefined," at this point). Each variable in order beginning with the first is set to its first value. As variable wj is set, the intermediate predicate Pj is tested. If the value of the predicate is false, the variable is set to its next value, until a value for which P1 is true is found. If the variable has no such value, it is reto the list of unset variables (set to "undefined") and turned the previous variable is set to its next value. This continues recursively until all the values of variable w1 have been tried. In a problem with v binary variables, the number of potential solutions is 2v, so an exhaustive search for solutions would take time exponential in v. Backtracking examines partial potential solutions as well as complete ones, so in the worst case, it examines twice as many sets of values as the exhaustive search method. In practice, however, backtracking usually performs

Pi(W1,

*

w;.

much better than exhaustive search.

D

B C

B

D

Fig.1. Zero-level backtrack tree for the predicate A A B AC-A D where A=aV-ic,B=--aVcVd,C=--iaVbVcV Each node where the predicate is false is labeled with a term that is false. Under each node, the variable that is introduced into the search at that point is given. In each case, the false branch is to the left.

-id,D=--ibVcV-,d.

In [2] we analyzed the behavior of simple backtracking over an NP complete set of problems consisting of conjunctive normal form formulas overv variables with s literals per term and (The parameters s anda are arbitrary vt terms,1