Heuristic Search and A*

Heuristic search uses a problem-specific estimate of the cost remaining to a goal to guide which states to explore first; A* is its canonical algorithm, expanding states in order of the sum of cost-so-far and estimated cost-to-go.

Definition

Heuristic search is informed search that orders the frontier using an evaluation function combining the known cost from the start with a heuristic estimate of the remaining cost; A* uses f(n) = g(n) + h(n) and is optimal when h is admissible.

Scope

This topic covers informed (heuristic) search strategies, centred on best-first search and the A* algorithm, including the design and properties of heuristic functions (admissibility, consistency/monotonicity), the optimality and efficiency guarantees these properties confer, and memory-bounded variants such as iterative-deepening A* (IDA*). It addresses how heuristics are constructed (relaxed problems, pattern databases) and how they trade accuracy against computation. Learning heuristics from data belongs to the machine-learning subfield.

Core questions

• What makes a heuristic admissible, and why does admissibility guarantee A* optimality?
• How does consistency (monotonicity) strengthen the guarantees and prevent node re-expansion?
• How are good heuristics designed, for example from relaxed versions of the problem?
• How do memory-bounded variants such as IDA* preserve optimality with limited space?

Key concepts

• evaluation function f = g + h
• admissible heuristic
• consistent (monotone) heuristic
• greedy best-first search
• A* search
• iterative-deepening A* (IDA*)
• heuristic dominance
• relaxed problem and pattern databases

Key theories

A* optimality under admissible heuristics

When the heuristic h never overestimates the true remaining cost, A* expands nodes by increasing f = g + h and is guaranteed to return a least-cost path; among algorithms using the same heuristic information, A* is optimally efficient.

Heuristic design via relaxation

Admissible heuristics can be derived systematically by solving a relaxed version of the problem (one with fewer restrictions on actions), since the exact cost of an easier problem is a lower bound on the original; dominating (more informed) heuristics expand fewer nodes.

Memory-bounded heuristic search

Iterative-deepening A* performs successive depth-first searches bounded by an increasing f-cost threshold, achieving A*-like optimality with memory linear in the solution depth.

Clinical relevance

Heuristic search powers route finding in maps and games, motion planning in robotics, and the search engines inside automated planners and puzzle solvers; the practical art of heuristic design directly determines whether large problems are solvable in acceptable time.

History

The A* algorithm was introduced by Hart, Nilsson, and Raphael (1968), giving heuristic search a formal optimality basis. Pearl's 1984 monograph Heuristics provided the definitive theoretical treatment, and Korf's 1985 IDA* addressed A*'s memory cost. These results remain core material in AI education.

Key figures

• Peter E. Hart
• Nils J. Nilsson
• Bertram Raphael
• Judea Pearl
• Richard E. Korf

Seminal works

• hart1968
• pearl1984
• korf1985

Frequently asked questions

What is an admissible heuristic?

A heuristic is admissible if it never overestimates the true cost of reaching the goal from any state. Admissibility is the condition under which A* is guaranteed to find an optimal (least-cost) solution.

What is the difference between greedy best-first search and A*?

Greedy best-first search expands the state that appears closest to the goal according to the heuristic alone (h), which is fast but can be far from optimal. A* adds the actual cost incurred so far (g), expanding by f = g + h, which preserves optimality when the heuristic is admissible.