26 Feb combinatorial explosion

The paradox of choices is a fundamental problem in computational search and problem solving. As the number of possible constraint or solution combinations that one has to examine grows exponentially, even the fastest computers may require excessive amounts of time to deliver acceptable results. This effectively limits a system’s ability to solve large problems. As it is, many problems of real interest to us have either a large number of constraints or possible solutions. Traditional “brute-force” searches where each option is compared consume processor time incrementally for each additional option. After a certain number of options, you would simply run out of time.

As an example, if you have n constraints or factors for a decision, each with 10 possible options, then you will have all together 10 to the power n combinations of results. The number of combinations grows exponentially as n increases.

In chess, a system could examine every possible move and the possible moves that could follow. However, if we limit it to 20 choices per move, then looking ahead 15 moves would require the system to compare 20 to the 15th power, or 3.3×10^19, sequences. If the system manages to examine 1 Billion sequences per second, a brute force search would have to take over 90 million hours or over 10,000 years to make one move. To improve the speed of play, one needs either much faster computers or heuristic algorithms that do not perform exhaustive search but choose which sequences to examine. The combinatorial explosion problem prevented computers from competing with human world champions until suitable heuristic solutions were invented.