A heuristic is a quick estimate used to guide a search. In A*, h(n) estimates the cost from a node to the goal; an admissible heuristic never overestimates that cost, preserving the shortest-path guarantee while influencing which nodes are explored first. section 12.1 section 12.4
The estimate depends on the problem:
- For A*, straight-line distance can estimate road distance; Manhattan distance estimates movement on a four-direction grid. section 12.1
- In ant colony optimization, the heuristic represents a path’s immediate desirability, often measured as the inverse of its distance; pheromone records past success. section 8.4
Choosing a grid estimate
On a grid where movement is only horizontal or vertical, Manhattan distance adds the horizontal and vertical separation from a node to the goal. It is admissible because no route can cover that displacement in fewer moves. section 12.1
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 estimates for road routing, grid movement, and sliding-tile puzzles. section 12.1











