Tutorial by Edward Tsang |

* Combinatorial explosion* is a fundamental problem in computing.
It is the problem that the number of

The * combinatorial explosion problem* limits the ability of
computers to solve large problems. This is because in most realistic problems of
interest to us, the number of combinations is typically very large.

Suppose you have *n* decisions to make and for each decision,
you have 10 possible options.
Then you will have all together 10 to the power *n* combinations of solutions.
The number of combinations grows * exponentially* as

In chess, one could examine every possible move and their subsequent moves.
However, if we assume that there are 20 choices per move, then looking ahead 15 moves
will involve examination of 20 to the power 15, or 3.3x10^19, sequences.
If our computer manages to examine 1,000,000,000 sequences per second (be sure
that your desktop computer won't have that speed), a
brute force search would have to take over 90 million hours ( over 10,000 years) to make one move, which is
obviously unacceptable. To improve the speed of play, one needs either *much
faster computers* or *clever algorithms* which allows one to be highly
selective in what sequences to examine.
The * combinatorial explosion problem* prevented computers from competing with
human world champions until recently.

Edward Tsang

Constraint Satisfaction and Optimisation Group

Department of Computer Science, University of Essex

12 May 2005