next up previous
Next: Quantum Search Methods Up: Combinatorial Search Previous: Phase Transitions


The Combinatorial Search Space

A general view of the combinatorial search problem is that it consists of N itemsgif and a requirement to find a solution, i.e., a set of tex2html_wrap2324 items that satisfies specified conditions or constraints. These conditions in turn can be described as a collection of nogoods, i.e., sets of items whose combination is inconsistent with the given conditions. In this context we define a good to be a set of items that is consistent with all the constraints of the problem. We also say a set is complete if it has L items, while smaller sets are partial or incomplete. Thus a solution is a complete good set. In addition, a partial solution is an incomplete good set.

A key property that makes this set representation conceptually useful is that if a set is nogood, so are all of its supersets. These sets, grouped by size and with each set linked to its immediate supersets and subsets, form a lattice structure. This structure for N=4 is shown in Fig. 1. We say that the


sets of size i are at level i in the lattice. As described below, the various paths through the lattice from levels near the bottom up to solutions, at level L, can be used to create quantum interference as the basis for a search algorithm.

Figure 1:  Structure of the set lattice for a problem with four items. The subsets of {1,2,3,4} are grouped into levels by size and lines drawn between each set and its immediate supersets and subsets. The bottom of the lattice, level 0, represents the single set of size zero, the four points at level 1 represent the four singleton subsets, etc.

As an example, consider a problem with N=4 and L=2, and suppose the constraints eliminate items 1 and 3. Then we have the sets {}, {2}, and {4} as partial goods, while {1} and {3} are partial nogoods. Among the 6 complete sets, only {2,4} is good as the others are supersets of {1} or {3} and hence nogood.

For the search problems studied here, the nogoods directly specified by the problem constraints will be small sets of items, e.g., of size two or three. On the other hand, the number of items and the size of the solutions will grow with the problem size. This gives a number of small nogoods, i.e., near the bottom of the lattice. Examples of such problems include binary constraint satisfaction, graph coloring and propositional satisfiability mentioned above.

For CSPs, the items are just the possible variable-value pairs in the problem. Thus a CSP with n variables and b values for each has N=nb itemsgif. A solution consists of an assignment to each variable that satisfies whatever constraints are given in the problem. Thus a solution consists of a set of L=n items. In terms of the general framework for combinatorial search these constraint satisfaction problems will also contain a number of problem-independent necessary nogoods, namely those corresponding to giving the same variable two different values. There are tex2html_wrap2330 such necessary nogoods. For a nontrivial search we must have tex2html_wrap2331 , so we restrict our attention to the case where tex2html_wrap2332 . This requirement is important in allowing the construction of the quantum search method described below.

Another example is given by a simple CSP consisting of n=2 variables ( tex2html_wrap2334 and tex2html_wrap2335 ) each of which can take on one of b=2 values (1 or 2) and the single constraint that the two variables take on distinct values, i.e., tex2html_wrap2337 . Hence there are N=nb=4 variable-value pairs tex2html_wrap2339 which we denote as items 1,2,3,4 respectively. The corresponding lattice is given in Fig. 1. What are the nogoods for this problem? First there are those due to the explicit constraint that the two variables have distinct values: tex2html_wrap2341 and tex2html_wrap2342 or {1,3} and {2,4}. In addition, there are necessary nogoods implied by the requirement that a variable takes on a unique value so that any set giving multiple assignments to the same variable is necessarily nogood, namely tex2html_wrap2344 and tex2html_wrap2345 or {1,2} and {3,4}. Referring to Fig. 1, we see that these four nogoods force all sets of size 3 and 4 to be nogood too. However, sets of size zero and one are goods as are the remaining two sets of size two: {2,3} and {1,4} corresponding to tex2html_wrap2348 and tex2html_wrap2349 which are the solutions to this problem.

Search methods use various strategies for examining the sets in this lattice. For instance, methods such as simulated annealing [32], heuristic repair [39] and GSAT [46] move among complete sets, attempting to find a solution by a series of small changes to the sets. Generally these search techniques continue indefinitely if the problem has no solution and thus they can never show that a problem is insoluble. Such methods are called incomplete. In these methods, the search is repeated, from different initial conditions or making different random choices, until either a solution is found or some specified limit on the number of trials is reached. In the latter case, one cannot distinguish a problem with no solution at all from just a series of unlucky choices for a soluble problem. Other search techniques attempt to build solutions starting from smaller sets, often by a process of extending a consistent set until either a solution is found or no further consistent extensions are possible. In the latter case the search backtracks to a previous decision point and tries another possible extension until no further choices remain. By recording the pending choices at each decision point, these backtrack methods can determine a problem is insoluble, i.e., they are complete or systematic search methods.

This description highlights two distinct aspects of the search procedure: a general method for moving among sets, independent of any particular problem, and a testing procedure that checks sets for consistency with the particular problem's requirements. Often, heuristics are used to make the search decisions depend on the problem structure hoping to identify changes most likely to lead to a solution and avoid unproductive regions of the search space. However, conceptually these aspects can be separated, as in the case of the quantum search algorithm presented below.

next up previous
Next: Quantum Search Methods Up: Combinatorial Search Previous: Phase Transitions

Tad Hogg
Wed Mar 20 16:29:17 PST 1996