When a route finder searches a city map, checking streets equally in every direction wastes effort. Informed search uses an estimate of the remaining cost to favor nodes closer to the destination. section 12.1
A* uses two costs to guide that search:
- g(n) is the actual cost paid to reach node n; h(n) estimates the cost still ahead. A* selects the node with the smallest f(n) = g(n) + h(n). section 12.4
- The heuristic must be admissible: it cannot overestimate the true remaining cost. This preserves A*’s guarantee of finding a shortest path. section 12.1
- A* does not stop just because it first discovers the goal; it waits until the goal is the lowest-priority node in the queue. section 12.4
A route through six intersections
In a worked map, A* first finds a route to the goal costing 11. It continues searching, then finds a route through D costing 10 and returns S → B → D → G. section 12.4
Table 12.1 Common admissible heuristics
|
Problem Domain
|
Heuristic h(n)
|
Why it never overestimates
|
|
Road network routing
|
Euclidean Distance (Straight Line)
|
A road can only be longer than a straight line between two
points, never shorter
|
|
Grid-based movement (4 directions)
|
Manhattan Distance
|
No sequence of horizontal/vertical moves can cover the
required displacement in fewer steps
|
|
Grid-based movement (8 directions, diagonals allowed)
|
Chebyshev Distance
|
A diagonal move covers one unit of both axes at once, so
this is the true minimum move count on an open grid.
|
|
Sliding-tile puzzle
|
Sum of each tile Manhattan distance from its goal position
|
Every tile must travel at least that many rows and
columns, even if no tile were in the way.
|
Compare admissible heuristic choices for roads, grid movement, and sliding-tile puzzles. section 12.4


