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, state space 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.

See also

• Search algorithm