Heuristic Search and the A* Algorithm

A* improves on Dijkstra's algorithm by using a heuristic estimate $h(n)$ of the remaining cost to the goal. This lesson defines admissible heuristics, introduces the A* priority function $f(n) = g(n) + h(n)$ , and traces A* end-to-end on small air-route graphs.

Step 1 of 157%

Tutorial

Heuristic Functions and Admissibility

In Dijkstra's algorithm, we explore nodes purely by the cheapest cost found from the source. On a large air-routing graph this can waste effort on legs that point away from the destination. A heuristic search uses extra information about the goal to focus the search.

A heuristic function $h(n)$ is an estimate of the cost of the cheapest path from node $n$ to the goal. We say $h$ is admissible if

h(n) \le h^*(n) \quad \text{for every node } n,

where $h^*(n)$ is the true shortest-path cost from $n$ to the goal. An admissible heuristic never overestimates.

In air routing, the great-circle distance from $n$ to the destination is admissible: an actual sequence of flight legs cannot be shorter than the straight-line spherical distance.

For instance, suppose airports $A, B, G$ have true distances to the destination $G$ of $h^*(A) = 500$ and $h^*(B) = 300$ nmi. The heuristic

h(A) = 480, \quad h(B) = 290, \quad h(G) = 0

is admissible. However, the heuristic

h(A) = 480, \quad h(B) = 320, \quad h(G) = 0

is not admissible, because $h(B) = 320 > 300 = h^*(B)$ .