Combinatorial search algorithms are normally implemented in an efficient imperative programming language, in an expressive declarative programming language such as Prolog, or some compromise, perhaps a functional programming language such as LISP or Haskell.
Classic combinatorial search problems include the Eight Queens Puzzle. See also Brute-force search.
A study of Computational complexity theory helps to motivate combinatorial search. Combinatorial search algorithms are typically concerned with problems that are NP-hard. Such problems are not believed to be efficiently solvable in general. However, the various approximations of complexity theory suggest that some instances (e.g. "small" instances) of these problems could be efficiently solved. This is indeed the case, and such instances often have important practical ramifications.
The concept of state space search is widely used in Artificial Intelligence. Successive configurations or states of an instance are considered, with the goal of finding a goal state with a desired property. This differs from traditional computer science search methods because the state space is implicit: the typical state space graph is much too large to generate and store in memory. Instead, nodes are generated as they are explored, and typically discarded thereafter. A solution to a combinatorial search instance may consist of the goal state itself, or of a path from some initial state to the goal state.
wikipedia.org dumped 2003-03-17 with terodump