Heuristic search

Also known as: informed search

On this page 7

Heuristic search, also called informed search, is a family of algorithms that find a path from a start state to a goal state by using a heuristic function, an estimate of the cost still remaining, to decide which state to expand next. In artificial intelligence, it is one of the classic techniques of automated planning and problem solving, and it underpins route finders, puzzle solvers, game engines and many scheduling tools.

Where uninformed search such as breadth-first search treats every unexplored state alike, heuristic search ranks the frontier by promise. A good heuristic can shrink the explored space by many orders of magnitude, while a poor one can make the search slower than a blind method or lead it to a costly answer.

How heuristic search explores a state space

Heuristic search works on a state space: a graph whose nodes are configurations of the problem and whose edges are actions with costs. The algorithm keeps a frontier (often called the open list) of states that have been generated but not yet expanded, and a closed list of states already expanded, so that duplicates are not processed twice.

At each step, the algorithm removes the state with the best evaluation score from the frontier, checks whether it is a goal, and otherwise generates its successors. The evaluation usually combines two quantities: g(n), the exact cost already paid to reach state n, and h(n), the heuristic estimate of the cost from n to the nearest goal.

The following table lists the main components that every heuristic search implementation must define.

ComponentRoleTypical implementation
State representationEncodes one configuration of the problemTuple, bit vector or grid coordinates
Successor functionGenerates reachable states and action costsRules of the puzzle, road graph edges
Goal testDecides whether a state solves the problemEquality check or predicate
Heuristic function h(n)Estimates the remaining cost to a goalDistance metric, relaxed problem, pattern database
FrontierHolds candidate states in priority orderBinary heap or bucket queue
Core components of a heuristic search

Main heuristic search algorithms

The algorithms in this family differ mainly in how they combine g(n) and h(n) and in how much memory they keep. The choice determines whether the answer is guaranteed to be optimal and how quickly memory runs out.

AlgorithmEvaluation functionOptimalMemory use
Greedy best-first searchf(n) = h(n)NoExponential in worst case
A* searchf(n) = g(n) + h(n)Yes, with admissible hStores all generated states
Weighted A*f(n) = g(n) + w h(n), w above 1Within factor w of optimalUsually lower than A*
IDA*Depth-first passes with rising f limitYes, with admissible hLinear in solution depth
Beam searchKeeps only the best k states per levelNoBounded by beam width k
Common algorithms and their guarantees

A* search is the reference algorithm because it is complete and optimal when the heuristic never overestimates, and it expands no more states than any other optimal algorithm using the same heuristic. Its weakness is memory consumption, which motivated IDA*, recursive best-first search and memory-bounded variants such as SMA*.

Properties that make a heuristic useful

The quality of heuristic search depends almost entirely on the heuristic. Two formal properties matter most. A heuristic is admissible when it never overestimates the true remaining cost, which guarantees that A* returns an optimal solution. It is consistent (or monotone) when h(n) is no larger than the step cost to a neighbor plus h of that neighbor, which ensures that A* never needs to reopen a closed state.

Beyond correctness, practitioners judge heuristics by accuracy and computation cost. One admissible heuristic dominates another when it is always at least as large; a dominating heuristic expands fewer states. The effective branching factor, often between 1 and 2 for strong heuristics, gives a single number for comparing them on the same problem.

Design methodIdeaExample
Relaxed problemRemove constraints and solve the easier problem exactlyManhattan distance in sliding-tile puzzles
Geometric distanceUse straight-line or grid distanceEuclidean distance in route planning
Pattern databasePrecompute exact costs for subproblemsCorner cubies of a Rubik’s Cube
LandmarksCount facts every plan must achieveClassical planners such as LAMA
Learned heuristicTrain a model to predict cost-to-goNeural value estimates in planning research
Ways to design a heuristic

Taking the maximum of several admissible heuristics yields another admissible heuristic that dominates each component, a simple and widely used technique. Learned heuristics can be very accurate but usually lose the admissibility guarantee, so the optimality of the answer is no longer certain.

Heuristic search sits between blind systematic search and local search. It differs from constraint satisfaction problem solvers, which prune assignments by propagating constraints, and from reinforcement learning, which learns a policy from interaction instead of planning over a known model.

ApproachUses domain knowledgeNeeds a modelTypical output
Uninformed searchNoYesPath, optimal for uniform-cost search
Heuristic searchYes, through h(n)YesPath or plan
Local searchYes, through an objectiveYesGood configuration, no path
Monte Carlo tree searchOptional, through rolloutsSimulatorNext action in a game
Reinforcement learningLearned from rewardsNot necessarilyPolicy or value function
How heuristic search relates to neighboring methods

The boundaries are porous. Modern game and planning systems often combine learned evaluations with tree search, which echoes the bitter lesson that general methods scaling with computation tend to outperform hand-crafted knowledge over time.

Limitations and common mistakes

Heuristic search does not escape exponential worst-case complexity; it only postpones it. On large problems with weak heuristics, the frontier can exhaust memory long before a goal is found. Typical errors in practice are listed below.

  • Using an overestimating heuristic with A* and still assuming the answer is optimal.
  • Ignoring duplicate detection, which makes graph search revisit the same states repeatedly.
  • Choosing a heuristic that is too expensive to compute, so fewer expansions still cost more time.
  • Applying search to problems with huge branching factors where sampling or decomposition fits better.
  • Breaking ties between equal f values arbitrarily; preferring larger g often reaches goals sooner.

In simple terms

Heuristic search is a way for a computer to find a solution without trying every possibility. At each step it asks which option looks closest to the goal and checks that option first.

Think of driving in an unfamiliar city toward a tall tower you can see on the horizon. You do not explore every street; you prefer the streets that head toward the tower. The tower is your rule of thumb. If the rule never makes the remaining trip look longer than it really is, the method can still guarantee the shortest route.

A practical example

A warehouse robotics team must plan paths for picking robots on a grid of about 40,000 cells with shelves as obstacles. Breadth-first search finds correct paths but expands most of the grid on long trips, which takes too long when dozens of robots replan every second.

The engineers switch to A* with Manhattan distance as the heuristic, which is admissible because robots move only in four directions at unit cost. On typical cross-warehouse trips, the planner now expands a small fraction of the cells it explored before, and paths remain the shortest possible. For peak hours they add weighted A* with w = 1.5, accepting paths at most 50 percent longer than optimal in exchange for faster replanning, and measure that real path lengths increase only slightly.