combinatorial explosion

views updated

combinatorial explosion The exponential growth rate experienced in many search problems. For example, in the game of chess the number of choices at each level increases by the branching factor, which may typically multiply the options by 20 or more at each move. Although in theory it should be possible to analyze the game of chess from start to finish, the number of states to be examined is so enormous that it is completely impractical, not only at present but for any conceivable computer in the future. (To appreciate this, consider an example: if one million game states can be examined each second and the branching factor is 10, then to analyze 6 moves ahead takes 1 second, to analyze 12 moves takes 11 days, and to cover 18 moves takes nearly 32 000 years.)

One of the main thrusts of artificial intelligence work has been to find ways, such as heuristic search, to circumvent the combinatorial explosion.