In computer science and artificial intelligence, combinatorial search studies 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.
A study of computational complexity theory helps to motivate combinatorial search.
Common algorithms for solving combinatorial search problems include: Lookahead is an important component of combinatorial search, which specifies, roughly, how deeply the graph representing the problem is explored.
A naive breadth-first search of these graphs would quickly consume all the memory of any modern computer.
When these techniques are used, lookahead is not a precisely defined quantity, but instead either the maximum depth searched or some type of average.