Textbook of AI

Heuristic search is the family of search techniques in which a domain-specific evaluation function, the heuristic, orders candidate states by estimated promise, allowing the algorithm to explore the most plausible parts of the search space first and prune or defer the rest. The use of heuristics is the way every practical search system tames the combinatorial explosion that would otherwise make exhaustive search infeasible.

The classic formulation distinguishes uninformed search (breadth-first, depth-first, iterative deepening), which uses no information beyond the structure of the search tree, from informed search (best-first, A*, IDA*), which uses a heuristic h(n) estimating the cost from n to the nearest goal. A* combines a heuristic estimate with the actual cost-so-far g(n) to evaluate nodes by f(n) = g(n) + h(n) and is optimal whenever h is admissible, never overestimates the true remaining cost.

Heuristic search was the dominant paradigm of first-wave symbolic AI. Logic Theorist, GPS, the early chess and checkers programs and the geometry theorem prover were all heuristic-search systems at heart. The framework remains central: modern SAT solvers, planning systems, theorem provers and even neural-network-guided systems like AlphaGo and AlphaZero are at base heuristic searchers with progressively more sophisticated heuristics , sometimes learned, sometimes derived from problem structure.

Newell, Shaw and Simon's analyses of heuristic search in the late 1950s, and Pearl's 1984 textbook Heuristics: Intelligent Search Strategies for Computer Problem Solving, codify the field.