How to Search Efficiently

1. Introduction

Some problems can be solved by direct calculation in an efficient, straightforward way, but for many important classes of problems the best known method is a controlled search for solutions. Such searches, unfortunately, can consume extremely (exponentially) large amounts of time, Efforts to study and improve search methods are therefore of considerable practical importance.

· This research was supported in part by the National Science Foundation under Grant no. MCS

7906110.

HOW TO SEARCH EFFICIENTLY*

Cynthia A. Brown and Paul Walton Purdom, Jr.

Computer Science Department Indiana University Bloomington, IN 47405

By carefully analyzing a particular set of problems it may be possible to find problem­ specific information that can be used to control the search, This can be an excellent approach; in some cases it has led to algorithms that avoid searching altogether. Often, however, after all problem-specific information has been used, excessive search time is still required, Another approach is to study general search algorithms and identify features that lead to an efficient search, The two approaches are complementary; the best algorithm for a particular problem is often obtained by combining problem-specific techniques with the best general search methods.

Here we report the initial results of a systematic study of the average time performance of search methods, All methods have about the same worst case time (exponentially large). Also, techniques that lead to an improvement in average performance often result in a minor degradation of worst-case behavior, so a study of worst-case behavior can be misleading. The average time performance of these algorithms can be much better than the worst-case performance. Some of the methods we study lead to an exponential improvement in average search time,

The search methods we analyzed include simple backtracking, search rearrangement backtracking [1,15), an algorithm similar to backtracking except that it notices when the predicate is true instead of noticing when it is unsatisfiable (the empty predicate method), and the empty predicate method combined with simple backtra,cking. Our analysis shows that the empty predicate rule does not contribute much to the performance of search algorithms, and that search rearrangement backtracking can be much more efficient than ordinary backtracking when the typical problem contains a large number of clauses with few

literals per clause.

Goldberg [8) analyzed a version of the Putnam- Davis procedure that essentially relies on the pure literal rule. The analysis shows that the pure literal rule can save a huge amount of time on problems that have a large number of literals per clause, but it also suggests that the rule is unimportant when the typical clause does not have many literals.

We hope to analyze the full Putnam-Davis procedure[4]. The points that remain to be analyzed are the effect of stopping the search when the first solution is found and the effect of the pure literal rule when the typical clause has only a few literals. The effect of combining various techniques also needs to be analyzed.

~ ~ Procedures

Searching is used to solve problems that .can be expressed in the form

where each Ri, 1~i~ , is a relation (a fUnction whose value is true or false) over a small number of variables, and the variables va are taken ik

from a set {vi I 1~i~n} of variables, each of which is restricted to a finite set of values. A solution of the problem is an assignment of values to the variables that makes all of the relations true.

Any problem in the class NP can be expressed as a predicate in the form of Eq.( 1 ). Many examples of such problems are given in [6]. We illu~trate the encoding of problems in this form with the game of generali~ed instant insanity [16]. The game is played with n cubes. Each face of each cube is painted with some color. The object of the game is to form a stack of n cubes with each cube oriented so that each face of the stack consists of cube faces that have distinct colors. Each cube has twenty-four possible orientations. Since the order of the cubes in the stack is irrelevant, the problem is equivalent to the predicate

where ok is the orientation of cube k and Rij(oi,o j) is true if and only if, when cube i has orientation oi and cube j has orientation oj, the pair of cubes forms a legal stack of height two (all faces of the stack are made up of distinct colors).

The most obvious method of searching for solutions to a predicate in this form is to try all combinations of values of the variables. This sort of exhaustive search is prohibitively slow for large problems. Fortunately, the special form of Eq. 1 permits three types of improvements. First, since each relation is defined over a small subset of the variables, a relation may become false as soon as all of its variables have been assigned values. In this case no extension of the current partial assignment of values to variables can be a solution. Such extensions need not be investigated. This is the idea behind backtracking.

A second improvement consists of looking for variables that should be assigned values early in the search. It is particularly helpful to find a variable all of whose values make a clause false (under the current partial assignment), or which has only one value which does not make a clause false. This is the basic idea of search rearrangement backtracking [ 1,15], and of the unit clause rule in the Putnam-Davis procedure [4].

A third approach involves looking for the values of a variable that are most likely to lead to a solution. In some cases there is a value that makes all relations which depend on the variable true. In that case only that one value of the variable requires consideration. This is the basis of the pure literal rule in the Putnam-Davis procedure.

These ideas have been used extensively to improve the average running time of search algorithms. We are studying algorithms that use various combinations of the ideas. To specify these algorithms we first give a common general procedure and then present the details that distinguish the various methods. The procedure uses a stack to keep track of which variables have been set.

Generalized ~ Procedure

1. [Initialize.) Set each variable to undefined. Set Stack to empty.
2. [Select variable.) Select as the current variable a variable that needs to be tested. If there is no such variable, go to Step 5. Push the current variable onto Stack and mark all of its values as untested.

1. [Select value.) For the current variable select an untested value that requires testing. If there is no such value, go to Step 6. Otherwise set the variable to that value and mark the
2. value as tested.
3. [Test.) If some clause of the predicate is false under the present partial assignment of values to variables, go to Step 3. If all solutions are desired, go to Step 2.
4. [Solution.) The current assignment of values to variables is a solution (any remaining unassigned variables may take on any of their values). If only one solution is desired, stop. If all solutions are desired, go to step 3.
5. [Back up.) Set the current variable to undefined. Pop Stack. The new current variable is at the top of Stack. If Stack is empty, stop. Otherwise go to Step 3.

Many search algorithms simplify the predicate as they search. For example, in the Putnam-Davis procedure clauses that become true are dropped. The dropped clauses are restored when the algorithm

backs up.

The algorithms that we have analyzed search for all solutions; they never stop at Step 5. In the future, unless otherwise stated, we will assume that Step 5 always goes to Step 3. For these algorithms the order in which values are tested at Step 3 is immaterial, since all values must eventually be tested.

Simple backtracking is obtained from the generalized search procedure by selecting the variables in a fixed order at Step 2 and the values in a fixed order at Step 3. Every variable and ever y value that is considered at Step 3 requires testing. In search rearrangement backtracking [1] a simple test is used to select a variable at Step 2. Each value of each variable is tested (using the same test used in Step 4), and the variable for which the fewest values pass the test is selected. More sophisticated search rearrangement

algorithms [15) test combinations of values.

In t he Putnam-Davis procedure variables are selected by examining the predicate directly rather t han by testing the values of variables. This me t hod of selection is more powerful, but it is also more difficult to program and requires more knowledge of the internal structure of the clauses.

The original Putnam-Davis procedure was designed for predicates in conjunctive normal form. To describe a more general procedure we first give some (nonstandard) definitions. A relation R is a ~ clause if, under the current partial assignment of values to variables, there is an unset variable v such that R is false for every value but one of v. We call v the associated variable of the unit clause. A variable v is relevant if there is a relation R whose value under the current partial assignment depends on v. A variable v is associated H1th ~ ~ literal if under the current partial assignment there is some value x of v such that when v is assigned value x every R that depends on v is true. The value x is called a ~ ~.

The generalized Putnam-Davis procedure is our general search procedure with the following modifications. In Step 2i if possible, select a variable associated with a unit clause. Otherwise, if possible, select a variable associated with a pure literal. Only one safe value is tested. If there are no variables associated with pure literals or unit clauses, then select any relevant variable. If there are no relevant variables, go to Step 5. The Putnam-Davis procedure stops when

the first solution is found.

We also considered the empty predicate method, an algorithm that may be viewed as an extremely simplified version of the Putnam-Davis procedure. In this algor! thm variables are selected in fixed order at Step 2, as long as some variable is relevant (the selected variable is not necessarily relevant). All values are tested at Step 3, and no tests are done at Step 4 (i.e. the test gives the result true) unless all relevant variables have been assigned values. The procedure searches for all solutions. The procedure is like backtracking except that it backs up when all the Ri are true instead of when one of them is false. It works by noticing when the predicate can be simplified to

the point where it is empty.

3. ~ Problems

To do an average time analysis it is necessary to select a set of representative problems and a probability distribution over the set. For backtracking it is not obvious what a "typical" problem is. In this paper we consider two types of random problem sets. Both are instances of conjunctive normal form predicates. for each type of problem set we give a method of forming a random clause; a random predicate is then the conjunction of t random clauses selected independently (thus, a random predicate may happen to contain two copies of the same clause).

In the first method of constructing random clauses each clause has s literals for some fixed s. The s literals are independently selected from the 2v possible literals. This method was used in our earlier analyses of backtracking algorithms [2,13].

In the second method each literal has probablity p of being in the clause for some fixed p. This method was used by Goldberg [8]. The two models are roughly equivalent when the parameters are set so that p = s/2v.

We follow the original papers in computing "running time" in the two models. In our model we assume that the "running time" is equal to the number of binary nodes in the search tree. The actual running time increases more rapidly (by a factor of approximately v [3)) but this error is unimportant compared to the exponential differences in the average running times of the various search algoriti:Jns.

In Goldberg's model we assume that the time to process a node is equal to avt , where a is a constant, v is the number of unset variables, and t is the number of terms that are still being considered. Both unary and binary nodes are counted.

4. Results

Table 1 summarizes the exact results for the average "running time" of various search algorithms. Host of the exact results are not in closed form, so it is difficult to understand their significance. An asymptotic analysis makes these results easier to interpret. To obtain an interesting asymptotic analysis, careful consideration must be given to how s, p, and t should vary as v increases. We believe that keeping s fixed (or letting p = a/v for fixed a) and letting t = bv for fixed b gives results similar to those for many interesting realistic problems. This keeps the individual terms small while letting the number of terms increase with v. We also consider t = va for fixed a>1. (For example, generalized instant insanity can be coded with s = 10 (five logical variables for each oi in the original problem) and t = (v/5)2.) The first choice for t produces problems where the number of constraints increases proportionately to the number of variables. The second choice produces problems where the number of constraints increases more rapidly.

Table 2 gives the approximate value of the logarithm of the average "r~nning time" for each algorithm. The two models generate problems with the same number of solutions when a = (ln 2) s. Usually the form of the answers is the same for the two models, but Goldberg's model generates problems that are much easier to solve by backtracking when a t = v (for 1<a<s). The results show that the empty predicate method is not helpful when p ~ 0. A little thought suggests that this method is less helpful than stopping the search when the first solution is found, because both approaches need a solution before they can save any time.

Comparing the results for simple backtracking with those for search rearrangement on our model with t = va shows that search rearrangement saves about as much time as reducing the size of the clauses by one literal. This exponential improvement indicates that search rearrangement can be much more effective than simple backtracking. Further analysis is needed to determine how search rearrangement behaves for t = bv.

The following table shows the results of setting s = 3,a = 3 ln 2 = 2.08, and b = (ln 2) (ln (1-2-s))-1 = 5.19 in the formulas from Table 2. These values for the parameters lead to an interesting set of difficult problems where the typical problem has about one solution regardless of the size of the problem, as is often the case for realistic difficult problems. The values in the table demonstrate clearly the exponential improvement that can result from using simple backtrackin~

I

5. Goldberg's resylts

In [8] Goldberg reported an average time analysis of an algorithm based on using the pure literal rule to simplify the predicate. When no pure literal is available it chooses a variable and creates two simplified predicates, one for each value of the variable. It uses the same stopping rule as the empty predicate method. The analysis i s over the Goldberg model as described above, but with p constant. We are preparing a joint paper with Goldberg in which some minor errors in the derivation presented in [8] are corrected. (Reference [14] is becoming a draft of this paper.) These analyses show that Goldberg's procedure takes polynomial average time on his model. When p is f ixed, the size of the clauses increases with the number of variables, and the number of solutions to a typical predicate also increases. The analysis does not apply to models with variable p, but it suggests that, for the case in which p approaches zero as v becomes large, the performance of Gol dberg's algorithm is not dramatically better than that of the empty predicate method.

6. Conclusions

The Putnam-Davis procedure is the source of many good ideas for improving the efficiency of search algorithms. It may be viewed as a combination of 1) backtracking, 2) unit clause selection (one level search rearrangement), 3) empty predicate detection, 4) pure literal selection, and 5) stopping at the first solution. The methods of [2,13] and of this paper are adequate to analyze an algorithm with the first three features. To analyze the first four is .more difficult. Goldberg [8] analyzed the effect of the pure literal rule in an algorithm where it does not affect the order of selection of the variables. It is quite likely that his methods can be combined with those of [2,13,14] to analyze an algorithm that uses all of the first four features. No work has yet been done on the effect of stopping at the first solution.

The analyses of random problems show that backtracking is effective on problems that contain a large number of clauses with few literals per clause. When backtracking is effective, backtracking combined with the unit clause rule is even more effective, but when backtracking is not effective adding the unit clause rule does not help much. The pure 11 teral rule works well when each clause contains a large number of literals. Since such predicates usually have a large number of solutions, stopping at the first solution is also effective in this case [5]. None of the analyzed methods is very effective for problems with a moderate number of literals per term and with the number of terms equal to several times the number of variables.

The most straightforward direction for future work is completion of the analysis of search rearrangement backtracking. The blank entries in Table 3 for level one backtracking can be filled in by completing calculations similar to those which led to the first entry. The multi-level backtracking algorithms appear to be even more efficient for large problems [3], but analyzing their performance is difficult.

Backtracking algorithms are easy to use: once the general search algorithm has been coded the user need only provide the routine to test partial solutions. Adding features of the Putnam-Davis procedure that manipulate the predicate requires more programming effort, but the resulting algorithm may also be much more powerful. Analyses are needed to determine whether this is the case.

There may be algorithms that are both simpler to analyze and more powerful than the Putnam-Davis procedure. One weakness of the Putnam-Davis procedure is that it does not have any guidance concerning which variable to select in cases where the pure 11 teral rule and the unit clause rule ao not apply. A good technique is to select a variable from the shortest remaing clause. A recent analysis by Monien et al [12] showed that a problem with three literals per term can always be solved in time 1,62v using an improvement on the Putnam-Davis algorithm that selects variables from the shortest clause. Some improvement is also obtained for problems with more than three literals per term. Other interesting techniques for modifying backtracking have been proposed [7 ,9,10,11].

Another area where progress is possible is in the use of rules to manipulate the predicate. Subsumption can be combined with the Putnam-Davis procedure. Substitution of equal quantities can also be used.

Many of the techniques used in this paper were developed in earlier work [2,8,13]. Each of the original papers analyzes one algorithm on one model. Here we apply the techniques to a variety of algorithms and models to determine how important various features are to efficient searching. A large number of ideas have been suggested for improving the efficiency of searching. If they were all combined the result would be a large, complex program, containing many parts that made little or no contribution to its efficiency. Analysis of average running time is a powerful technique for determining the value of proposed improvements.