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 (more generally, traveling salesman problem is the classic example of combinatorial explosion.

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.

See also: brute force attack.