   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 items and a requirement to find a solution, i.e., a set of 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 items . 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 such necessary nogoods. For a nontrivial search we must have , so we restrict our attention to the case where . 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 ( and ) 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., . Hence there are N=nb=4 variable-value pairs 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: and 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 and 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 and 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 , heuristic repair  and GSAT  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: Quantum Search Methods Up: Combinatorial Search Previous: Phase Transitions