Editing Brute-force search (section)

==Alternatives to brute-force search==
There are many other search methods, or metaheuristics, which are designed to take advantage of various kinds of partial knowledge one may have about the solution. [[Heuristic]]s 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, that eliminates many subtrees at an early stage in the search. 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 many cases, such as in [[Constraint Satisfaction Problem]]s, one can dramatically reduce the search space by means of [[Constraint propagation]], that is efficiently implemented in [[Constraint programming]] languages. 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 [[evaluation function|static evaluation function]].