Optimizing Backtrack Search for all Solutions to Conjunctive Problems

1. Introduction

In this paper we consider the problem of optimization of search effort for the generation of all solutions to a problem that is stated as a conjunction of subproblems. Conjunctive problems arise frequently in many applications of Artificial Intelligence as well as in database applications of logic. Depth-first search with backtracking is a commonly used problem-solving search tech­ nique used in such applications. It is the default strategy for the control of inference in sequential Prolog. Our motivation here is to develop search ordering conditions for the optimal control of depth-first search required in such problem-solving systems. Knowing what constitutes optimal ordering conditions or a characterization of the conditions that can be used systematically to improve a given ordering is critical for optimizing the effi­ ciency of problem-solving systems.

A conjunctive problem has the generic form:

where, G (S) is the problem to be solved and S - {.x;, X2, · · · , X.} is a set of n argument variables. For 1 s i s m , P, (S,) is the ;'· subproblem with arguments S,, where S 1 t;;.S . A solution to problem G is a binding of constants to each of the arguments of P~o P2, ··· , P,. such that a) each subproblem P, is solved, and b) each argument that is common to two or more subproblems must be consistently bound to a constant value. Two solutions are distinct if they have different bindings, i.e., in one solution there is at least one argument whose binding is dif­ ferent in the other solution.

It has been recognized [SMI85a] that a significant weakness of backtracking is that the computational effort in searching for all feasible solutions to a conjunctive problem is quite sensitive to the sequence in which the subproblems are considered. In the next section, we review related work on controlling the search required to generate all solutions to conjunctive problems. In Section 3, we present our results on how to order subproblems such that the search effort for generating all solutions is mini­ mized. The results are summarized as follows. We show the conditions for optimal ordering of subproblems of a conjunctive problem that has: a) many independent subproblems, or b) ex­ actly two dependent subproblems. For conjunctive problems with an arbitrary number of dependent subproblems, we derive necessary conditions for optimal ordering. The conditions can be used for systematic transformation of a given ordering of subproblems into a locally optimal sequence of subproblems. In Section 4 we present our conclusions.

2. Related Work

The problem we consider here, namely, the efficient generation of all solutions to a conjunctive problem with backtracking as the basic problem-solving strategy, has been addressed in the past by a number of researchers. The work of Warren [WAR81], Smith [SMI85a] and Smith and Genesereth [SMI85b] are espe­ cially pertinent to us.

Warren [WAR81] considered the efficient evaluation of data­ base queries, which may be regarded as a class of conjunctive problems, expressed in the Prolog language. Warren developed a heuristic approach for improving the efficiency by a suitable reordering of the subproblems of a conjunctive problem. The approach, demonstrated experimentally in a system for natural language question answering, relies on the availability of statis­ tical information such as the number of solutions to each sub­ problem, the number of distinct values for each argument in a solution, etc. Two important as:;umptions are made in [W AR81 ]. The first assumption made is that the uniform dis­ tribution of attribute values holds. The uniform distribution as­ sumption holds if in the solution set of a problem, each argument variable of the problem is bound to elements of its domain with equal frequency.

The second assumption made implicitly in [W AR81] is the uni­ form cost assumption. The assumption is that the cost of ob­ taining a solution to a subproblem is the same across all subproblems, i.e., each subproblem is computationally just as hard as any other subproblem in the conjunctive problem. We note that there are many applications for which the uniform cost assumption does not hold. To illustrate this, consider a conjunctive problem consisting of three subproblems, say, PI> P2 and P 3 · Suppose the solutions to Subproblem P1 are explicitly available and stored in the main memory of a computer; solutions to Subproblem P 2 are also explicitly available but stored in a slower peripheral device, such as a disk; and, solutions to P3 are not explicitly available but a problem-solving search procedure can determine the solutions after possibly applying certain in­ ference procedures. In such a situation, the cost (or equivalently, the time needed) for obtaining a solution is very unlikely to be the same across different subproblems. For the purpose of effi­ cient solution of conjunctive problems under such more general conditions, we relax the uniform cost assumption and allow the cost per solution depend on the subproblem being solved. We still·assume, however, that for any given subproblem the cost of obtaining a solution is constant, i.e., it does not depend on the specific solution obtained for the subproblem.

Relevant analytical work on optimal static ordering of the sub­ problems of a conjunctive problem has recently been reported by Smith and Genesereth [SMI85a] [SMI85b]. Static ordering means the planning, i.e., the decision on how to sequence the subproblems, is made before the actual backtrack enumeration effort is undertaken. Once an ordering of the subproblems is chosen it is left unchanged during the entire enumeration phase of problem-solving. Smith and Genesereth have addressed how a problem-solving system can minimize the effort in generating all solutions by using information provided to the system re­ garding average number of solutions to each subproblem. The uniform distribution assumption regarding attribute values and the uniform cost assumption have also been made in [SMI85b]. The work cited above, based on assumptions of uniform cost and uniform distribution, provides a good starting point for us.

We note that the total search effort in enumerating all the sol­ utions to a conjunctive problem typically depends on both: a) how the values of each argument variable are distributed in the solution set of each subproblem, and b) the cost associated with the solution of each subproblem. In this paper, we consider the impact of relaxing the assumptions of uniform cost and uniform distribution, on optimizing the search ordering.

3. Results

Consider the problem G(S) stated in ( 1 ). Suppose the solutions to G are enumerated by solving the subproblems in the sequence shown in (1) . Let~ and C, be respectively the number of sol­ utions and the cost of obtaining a solution to Subproblem P,, given that subproblems P 1 through P,_, have been solved. Assume the root of the search tree is at Level 0. There are N1 solutions to P 1 and each solution is represented by a node at Level 1. Corresponding to each solution of P1 there are N2 solutions of P2 and hence, N 1 N 2 nodes at Level 2. In general , at Level i of the search tree, there are N1N2 ··· ~ nodes. Thus, the total number of nodes in the backtrack search tree corresponding to the se­ quence expressed in (1) is:

Since there are N 1 nodes at Level 1, each requiring a search effort of C~> the total search cost at Levell is N,C, . In general, the total search effort at Level i is N 1 N2 ··. ~C, , the product of the number of nodes at Level i and the search effort per node at that level. Thus, the total cost of the backtrack search algorithm corre­ sponding to the sequence expressed in ( 1) is :

3.1 Independent Subproblems

A Subproblem P,(S,) is defined to be independent of Subproblem P/S) (fori"¢ j) if S 1 has no variable in common with S,. Two subproblems that share at least one common variable are defined to be directly .dependent. Two Subproblems, P,, P 1 (i "¢ j) , are considered indirectly dependent if there exists a Subproblem P. (kd "¢ ij). such that P, is directly dependent on P. and P. is de­ ~en ent, etther directly or indirectly, on P 1 . For a sequence of mdependent subproblems, the following result shows the condi­ tions that must be satisfied by an optimal ordering of subprob­ le~s. The result. holds regardless of the distributions of argument vanables. The proof can be found in [NAT86].

Result Let a conjunctive problem, expressed as in (1), have Subp.roblems P,(S1) through Pm(Sm) that are pairwise independ­ ::nt, J.e., no subproblem s)Jares a variable with any other sub­ problem. Then the ordering that minimizes (3), the cost of generating all solutions to the problem, is to sequence the sub­ problems such that:

fori"¢ j, 1 :5 ij :5 m.

Special Case (i). If each subproblem has the same number of sol­ . utions (i.e., N, = Nz = · .. = Nm ), then the subproblems must be ordered in decreasing order of their costs, i.e., Subproblem P. should be solved before Subproblem P whenever C > C · J i ]'

Special Case (ii). If the cost of obtaining a solution is identical for the subproblems (i.e., C1 = C2 = · · · = Cm), then the subprob­ lems must be ordered in ascending order of their number of sol­ utions, i.e., Subproblem P, should be solved before Subproblem P 1 whenever N, < ~·

It is significant to note that the above result can often be used even if, in practice, a given conjunctive problem expressed in the form of (1) may have the property that every pair of subprob­ lems is dependent, either directly or indirectly, on each other. A problem-solver can use the knowledge about optimal ordering conditions for independent subproblems even if the given conjunctive problem contains only dependent pairs of subprob· I ems.

3.2 Dependent Subproblems

Typically, the number of solutions to P;(S) depends on all the subproblems that were solved prior to P,. The objective of min­ imizing the search cost is equivalent to choosing the best per­ mutation of the set of subproblems such that the cost expressed in (3) is minimized. A conjunctive problem is considered feasible if there exists at least one solution to the problem.

3.2.1 Two Subproblems in a Conjunctive Problem

We first consider conjunctive problems expressed as conjunc· tions of exactly two subproblems. In this section, the uniform distribution assumption and the uniform cost assumption are both relaxed. Consider a problem stated as a conjunction of two subproblems: P 1 (S 1 ) & P2(S2) , where the cost of obtaining a solution to Subproblems P 1 and P2 are C1 and C2 respectively. Without loss of generality, assume that S1 and S2 have exactly one variable X common to them. Let D(X) - { v., ~ · ... , vK} be the domain of X with cardinality K. X can be bound to one of the K elements. Among the solutions to Subproblems P.(s.) and P 2 (S 2 ) , let X be bound to v, with frequencies N1~ and N2,, respec· tively. Let R 1 represent the sequence Subproblem P1 followed by Subproblem P2 and R2 represent the sequence Subproblem P2 followed by Subproblem P1· Let Cost(R1) and Cost(R2) respec­ tively denote the cost of searching for all solutions by using R 1 and R2· The cost of search for the two different sequences is computed as follows. Let 1J.2 be the number of solutions to the conjunctive problem.

Thus, we have the following result.

From ( 4) we obtain the following results for special cases. Case (i) : H the search cost per solution of each subproblem is the same (i.e., C1 - C2) , then the subproblem with fewer solutions should be solved first. Case (ii) : H the two subproblems have an equal number of solutions (i.e., N1 ... N2) and the conjunctive problem has at least N. solutions, then the subproblem that is more costly should be solved first ; otherwise, the less costly problem should be solved first.

3.2.2 At Least Three Subproblems in a Conjunctive Problem

We next consider conjunctive problems that are expressed as a conjunction of three or more subproblems. We relax the uniform cost assumption-but assume the uniform distribution assumption holds for the individual subproblems. H a subproblem has t sol­ utions, and X is one of its argument variables with domain D(X) . = { v., ~ · ... , vK} , our assumption is that for any specific value of X, there will be exactly t I K solutions to the subproblem.

Suppose a conjunctive problem expressed as in (1) is solved by ordering the subproblems in two different sequences, R 1 and R 2 as follows:

The subproblems solved at each level of the search tree traversed by a backtracking algorithm is shown in Fig. 1. Note that each level of the search tree corresponds to exactly one of the m dis­ tinct subproblems of the conjunctive problem. The two search sequences, R1 and R2 differ in only the relative ordering of Subproblems P, and P,.1 · Consequently they spend exactly the same computational effort at all levels except at Level i and Level (i + 1) of the search tree. For a given ordering of the subprob­ lems, let Cosl(l£vel} be the search cost incurred at Levelj of the search tree corresponding to the ordering. Note that Cost(l£vel} is the product of the total number of attempts to find a solution to the subproblem considered at Levelj and the aver­ age cost per solution attempt of the subproblem. We have,

~t Q denote the total number of partial solutions to the the ftrst (I - 1) s~bproblems of either sequence. We have to distinguish two possible cases that may arise.

~~)~The set of variables inS, that are bound when P, is solved IS dJ~Jomt from the set .of variables in s,. 1 that are bound when P,.1 IS solved.

CIIM(~i): The set of variables in S, that are bound when P, is solved contams at least one variable that also occurs ins, ··.

Let a, denote the number of solutions to P, given that the initial sequence of subproblems, P., P 2 , ··· , P,_., has been solved. Let a, ·· denote the number of solutions to P,. 1 given that the initial sequence of subproblems, P., P 2 , · · · , P,_., has been solved.

CIIM!(i): The difference in search costs of sequences R and R2, Cost(R1) - Cost(R 2 ) , equals: 1 ·

Thus, Sequence R1 is better than Sequence R 2 ( ' C (R) t.e., ost 1 < Co.rt(R2) ) , if and only if,

From the condition expressed in (5) we obtain the following re­ sults for minimizing the average search cost.

a) If the search cost per solution of Subproblems P, and P,.1 is the same (i.e., C, = c,.1), then the subproblem with fewer solutions should be solved first.

b) If the two subproblems have equal number of solutions (i.e., a, -= a,.1) and the conjunctive problem is feasible, then the sub­ problem that is more costly should be solved before the Jess costly problem.

If neither the number of solutions nor the cost per solution of Subproblems P, and P,. 1 are equal, then Subproblem P, should be considered before P,.1 whenever:

• c, c,.1 c) P, is more costly than P,. 1 and the condition -a > -- holds. 1 a,. 1

d) P, is Jess costly than P,.t. and the condition a,C, < a,. 1C,. 1 holds.

In the general case, the decision about whether Subproblem P, should be solved before P,.1 is resolved by evaluating the condi­ tion expressed in (5) .

Case(ii): The size of the domain of a variable is the cardinality of the set of distinct values that can be bound to the variable. Let s represent the product of domain sizes of each variable that occurs in both S, and s,. 1 and has not already been bound during solution of the sequence Ph P1, ··· , P,_1 · The difference, Cost(R 1 ) - Cost(R 1 ) , in search costs of sequences R1 and R2 that differ in only the work done at Levels i and (i + 1) equals:

Thus, Sequence R1 is better than R2 , if and only if,

From the condition expressed in (6) we obtain the results anal­ ogous to (a), (b) , (c), and (d) in case (i) above for minimizing the average search cost. In the general case, the decision about whether Subproblem P, should be solved before P,. 1 is resolved by evaluating the condition expressed in (6).

The conditions for optimal ordering of subproblems derived in this section (3.2.2) are based on the key assumption of uniform distribution of arguments of each subproblem. The uniformity of distribution means that the structure of the search tree has the following characteristic. At any level of the search tree, the number of sons of each node at that level is the same. Ordering of subproblems has an impact on the degree (i.e., number of sons) of nonterminal nodes at each level of the search tree. At each specific level of the tree, the degree is uniform. Search or­ dering that minimizes total search effort is one of the m! possible sequences in which m subproblems may be statically sequenced before the enumeration effort begins.

We briefly discuss what will be the impact of non-uniform dis­ tribution of arguments ·of subproblems. Suppose one is inter­ ested in generating all solutions to a _conjunctive problem for which the uniform distribution assumption does not hold. Typi­ cally, search effort for such a problem can not be optimized by restricting to the class of static orderings of subproblems ( see [NAT86] for details). For such problems, the minimization of search effort requires that search ordering be context-dependent, i.e., whenever a decision has to be made on what subproblem to solve next, it must take into account the existing binding envi­ ronment at that instant. With this technique, the planning (i.e., sequencing of subproblems) is interleaved with the enumeration of solutions. This technique of dynamic search ordering or search rearrangement [Bm5] has been effectively used in the solution of combinatorial puzzles. The technique holds potential for effi­ cient solution of conjunctive problems in general problem­ solving applications that are characterized by non-uniform distributions.

4. Conclusions

In general, an optimal depth-first search sequence, that mini­ mizes the total computational effort for solving conjunctive problems, depends on both: a) how the values of each argument variable are distributed in the solution sets of the subproblems, and b) the cost associated with the solution of each subproblem.

For a sequence of independent subproblems, we stated the opti­ mal ordering conditions that can be used even if a given conjunctive problem has only dependent pairs of subproblems. For a sequence of three or more dependent subproblems, if the uniform distribution assumption holds and the uniform cost as­ sumption is relaxed, then we showed search ordering conditions that can be used for systematic transformation of a given order­ ing of subproblems into a locally optimal sequence of subprob­ lems. If assumptions regarding both the distributions and costs associated with subproblems are relaxed, then dynamic se­ quencing of subproblems is necessary to minimize the search ef­ fort. Issues related to the use of dynamic search ordering for improving search efficiency merit further study.