A* is only as good as its heuristic. Understanding what makes a heuristic safe, and how to build better ones, is the key skill in informed search.
The scoring rule
A* ranks nodes by f(n) = g(n) + h(n). Here g(n) is the cost already paid to reach the node, and h(n) is an estimate of the remaining cost to the goal.
Admissible and consistent
A heuristic is admissible if it never overestimates the true remaining cost. With an admissible heuristic, A* returns an optimal path in tree search. A heuristic is consistent if h(n) is never more than the step cost to a neighbor plus that neighbor's h value. Consistency guarantees optimal results for graph search without reopening nodes, and every consistent heuristic is also admissible.
Build heuristics by relaxing the problem
A reliable method is to remove some rules and solve the easier problem exactly. In the 8-puzzle, if tiles could move through each other, each tile would only need to travel its Manhattan distance to its goal square. The sum of those distances is admissible for the real puzzle. Counting misplaced tiles is also admissible, but weaker.
Stronger is better, up to a point
If h2(n) ≥ h1(n) for every node and both are admissible, then h2 dominates h1 and A* with h2 expands no more nodes. The maximum of several admissible heuristics is admissible too, so you can combine ideas safely. Computing the heuristic must stay cheap enough to be worth the savings.
Two pitfalls
Inflating a heuristic to "go faster" can break optimality. Setting h to zero removes the guidance entirely and turns A* into uniform-cost search.
Continue with the book
Explore the full treatment, worked examples, and exercises in The AI Algorithms Compendium.
Adapted from The AI Algorithms Compendium, published by Choral Software. Article text and original examples © 2026 Choral Software. All rights reserved.