# Combinatorial search

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Combinatorial_search
> Markdown URL: https://mediated.wiki/source/Combinatorial_search.md
> Source: https://en.wikipedia.org/wiki/Combinatorial_search
> Source revision: 1235533628
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve this article by introducing more precise citations. (January 2013) (Learn how and when to remove this message)

This article relies largely or entirely on a single source. Please help improve this article by citing more sources. Find sources: "Combinatorial search" – news · newspapers · books · scholar · JSTOR (May 2024)

In [computer science](/source/Computer_science) and [artificial intelligence](/source/Artificial_intelligence), **combinatorial search** studies [search algorithms](/source/Search_algorithms) for solving instances of problems that are believed to be hard in general, by efficiently exploring the usually large solution space of these instances. Combinatorial search algorithms achieve this efficiency by reducing the effective size of the search space or employing heuristics. Some algorithms are guaranteed to find the optimal solution, while others may only return the best solution found in the part of the state space that was explored.

Classic combinatorial search problems include solving the [eight queens puzzle](/source/Eight_queens_puzzle) or evaluating moves in games with a large [game tree](/source/Game_tree), such as [reversi](/source/Reversi) or [chess](/source/Chess).

A study of [computational complexity theory](/source/Computational_complexity_theory) helps to motivate combinatorial search. Combinatorial search algorithms are typically concerned with problems that are [NP-hard](/source/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.

## Examples

Common algorithms for solving combinatorial search problems include:

- [A* search algorithm](/source/A*_search_algorithm)

- [Alpha–beta pruning](/source/Alpha%E2%80%93beta_pruning)

- [Branch-and-bound](/source/Branch-and-bound)

- [Minimax](/source/Minimax)

## Lookahead

Lookahead is an important component of combinatorial search, which specifies, roughly, how deeply the [graph](/source/Graph_(data_structure)) representing the problem is explored. The need for a specific limit on lookahead comes from the large problem graphs in many applications, such as [computer chess](/source/Computer_chess) and [computer Go](/source/Computer_Go). A naive [breadth-first search](/source/Breadth-first_search) of these graphs would quickly consume all the memory of any modern computer. By setting a specific lookahead limit, the algorithm's time can be carefully controlled; its time [increases exponentially](/source/Exponential_growth) as the lookahead limit increases.

More sophisticated search techniques such as [alpha–beta pruning](/source/Alpha%E2%80%93beta_pruning) are able to eliminate entire subtrees of the search tree from consideration. When these techniques are used, lookahead is not a precisely defined quantity, but instead either the maximum depth searched or some type of average.

## See also

- [Brute-force search](/source/Brute-force_search)

- [Combinatorial explosion](/source/Combinatorial_explosion)

- [Combinatorial optimization](/source/Combinatorial_optimization)

- [Search algorithm](/source/Search_algorithm)

- [State space search](/source/State_space_search)

## References

- Russell and Norvig. *[Artificial Intelligence: A Modern Approach](/source/Artificial_Intelligence%3A_A_Modern_Approach)*.

---
Adapted from the Wikipedia article [Combinatorial search](https://en.wikipedia.org/wiki/Combinatorial_search) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Combinatorial_search?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.