2.1.2 The Problem: Combinatorial Explosion
The naive way of solving combinatorial problems can be paraphrased as `generate and test': In a first step one enumerates all combinations from which one selects all solutions in the second step. In most cases however, `generate and test' is simply not feasible. This is obvious if the set of combinations is infinite. But even if it is finite then it is usually very large, i.e. exponentially large in size of the problem description. In this case, the generation step runs into a combinatorial explosion (from which it usually returns only several billions of years later).
Constraint Satisfaction Problems
A typical example is a constraint satisfaction problem: it consists of variables V1,...,Vn which respectively take values from finite domains D1,...,Dn, where Di is a finite set of values such as an interval of integers. The problem is to find assignments of values to the variables such that a constraint C(V1,...,Vn) is satisfied.
Let's consider the following example of 15 variables V1,...,V15, all taking values in the domain {1,...,15} and for which we want to find all solutions that satisfy the constraints:
V1 < V2
V2 < V3
...
V14 < V15Clearly, there is only 1 solution to this problem, namely:
V1=1, V2=2, ... , V15=15Let's see how various general problem solving techniques perform on this example.
Generate and Test
We can enumerate the possible assignments by picking a non-assigned variable, non-deterministically choosing a value in its domain as its assignment, and repeating until all variables are assigned values. This process spawns a tree: each inner node of this tree corresponds to a non-deterministic choice of value to assign to a variable, and the leaves are all possible complete assignments.
The leaves which satisfy the problem's constraint are said to be solutions. Those which violate this constraint are said to be failures. We will often display a search tree graphically as shown below, where blue circles represents choice points, red squares failures, and green diamonds solutions. For convenience, a subtree whose leaves are all failures (resp. solutions) is usually abbreviated by a red (resp. green) triangle.
For our problem, there are 15 variables, each taking one of 15 possible values: this means there are 15^15 = 437.893.890.380.859.375 possible assignments. Let's be optimistic and suppose we have a fast computer able to check 10^9 assignments per second to decide whether each is a solution or a failure: checking all possibilities would still take approximately 14 years.
For a concrete example, let's consider only 6 variables V1,...,V6 taking values in {1,...,6} and such that they must satisfy V1 < ... < Vn. The generate and test method produces the following search tree with 93311 nodes:
