Combinatorial search

Combinatorial search is a branch of computer science that sits at the intersection of several fields, including artificial intelligence, mathematics and software engineering. Combinatorial search algorithms solve instances of problems that are believed to be hard in general, by exploring the usually-large solution space of these instances. Combinatorial search algorithms achieve this by reducing the effective size of the space, and by exploring the space efficiently.

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.