Brute-force search

Brute-force search

In computer science, a brute-force search consists of systematically enumerating every possible solution of a problem until a solution is found, or all possible solutions have been exhausted. For example, an anagram problem can be solved by enumerating all possible combinations of words with the same number of letters as the desired phrase, and checking one by one whether the words make a valid anagram.

Combinatorial explosion

Many real-world problems have exponential time or space complexity, so that only very small problems are amenable to this approach. For example,

searching the space of six-digit numbers takes only a million iterations: assuming a thousand instructions are needed to check the solution, a single modern computer can solve the problem in a billion instructions, or approximately a second at a rate of 1 billion instructions per second.
searching the space of twelve-digit numbers would take 10¹⁵ instructions, or 10⁶ seconds (around 10 days) on a single computer. This computation could still be performed in a single second if it was possible to farm it out onto one million separate computers, and this parallel technique is used in real problems.
searching the space of 24-digit numbers would take 10²⁷ instructions, or 10¹⁸ seconds on a single computer. Even farmed out over a million modern computers, this would still take 10¹² seconds, or around 30,000 years!

The traveling salesman problem is the classic example of this type of problem.

The field of computational complexity theory was developed to deal with these issues.

Speeding up brute-force searches

In many cases problems can be transformed to reduce the search space. For example, in the proof of the four color theorem, a potentially infinite search space was first reduced to a set of finite problems by intensive consideration of mathematical issues, the finite problems were then reduced further in size by more theoretical work, and only then was the problem finished off by brute force search of the remaining possibilities.

Heuristics can also be used to make an early cutoff of parts of the search. One example of this is the minimax principle for searching game trees. This eliminates many subtrees at an early stage in the search, effectively doubling the depth of search that can be made for a given amount of computation.

In certain fields such as language parsing techniques such as chart parsing can exploit constraints in the problem to reduce an exponential complexity problem into a polynomial complexity problem.

In the anagram problem:

an example of problem simplification is that all words containing letters not in the original phrase can be excluded from the search
an example of early cutoff is that once a partial set of words has used a letter more times than it exists in the target phrase, all sets of words starting with that subset of words can be rejected

The search space for problems can also be reduced by replacing the full problem with a simplified version. For example, in computer chess, rather than computing the full minimax tree of all possible moves for the remainder of the game, a more limited tree of minimax possibilities is computed, with the tree being pruned at a certain number of moves, and the remainder of the tree being approximated by a static evaluation function.