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.
| Component | Role | Typical implementation |
|---|---|---|
| State representation | Encodes one configuration of the problem | Tuple, bit vector or grid coordinates |
| Successor function | Generates reachable states and action costs | Rules of the puzzle, road graph edges |
| Goal test | Decides whether a state solves the problem | Equality check or predicate |
| Heuristic function h(n) | Estimates the remaining cost to a goal | Distance metric, relaxed problem, pattern database |
| Frontier | Holds candidate states in priority order | Binary heap or bucket queue |
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.
| Algorithm | Evaluation function | Optimal | Memory use |
|---|---|---|---|
| Greedy best-first search | f(n) = h(n) | No | Exponential in worst case |
| A* search | f(n) = g(n) + h(n) | Yes, with admissible h | Stores all generated states |
| Weighted A* | f(n) = g(n) + w h(n), w above 1 | Within factor w of optimal | Usually lower than A* |
| IDA* | Depth-first passes with rising f limit | Yes, with admissible h | Linear in solution depth |
| Beam search | Keeps only the best k states per level | No | Bounded by beam width k |
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 method | Idea | Example |
|---|---|---|
| Relaxed problem | Remove constraints and solve the easier problem exactly | Manhattan distance in sliding-tile puzzles |
| Geometric distance | Use straight-line or grid distance | Euclidean distance in route planning |
| Pattern database | Precompute exact costs for subproblems | Corner cubies of a Rubik’s Cube |
| Landmarks | Count facts every plan must achieve | Classical planners such as LAMA |
| Learned heuristic | Train a model to predict cost-to-go | Neural value estimates in planning research |
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 compared with related approaches
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.
| Approach | Uses domain knowledge | Needs a model | Typical output |
|---|---|---|---|
| Uninformed search | No | Yes | Path, optimal for uniform-cost search |
| Heuristic search | Yes, through h(n) | Yes | Path or plan |
| Local search | Yes, through an objective | Yes | Good configuration, no path |
| Monte Carlo tree search | Optional, through rollouts | Simulator | Next action in a game |
| Reinforcement learning | Learned from rewards | Not necessarily | Policy or value function |
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.