How Does A* Search Use an Admissible Heuristic?

The A* search algorithm finds the shortest path between a start node and a goal node in a weighted graph by combining exact path costs with an estimated remaining distance. It uses an admissible heuristic function to ensure that its estimates never overestimate the true cost to reach the goal, which allows the algorithm to prioritize promising paths while guaranteeing an optimal solution.

The Evaluation Function

At every step of the exploration, A* maintains a priority queue of candidate nodes to expand. Each node \(n\) is evaluated using the function:

\[f(n) = g(n) + h(n)\]

Here, \(g(n)\) represents the exact known cost of the shortest path found so far from the start node to node \(n\). The term \(h(n)\) is the heuristic function, which estimates the minimum cost to travel from node \(n\) to the goal node. By always selecting the node with the lowest \(f(n)\) value from the priority queue, A* balances exploring paths that are already cheap with exploring paths that appear close to the goal.

What Makes a Heuristic Admissible

A heuristic function \(h(n)\) is admissible if, for every node \(n\) in the graph, it never overestimates the true minimum cost \(h^*(n)\) to reach the goal:

\[0 \le h(n) \le h^*(n)\]

Because \(h(n)\) is an optimistic lower bound, \(f(n)\) is always less than or equal to the true total cost of any path passing through \(n\). For example, in a two-dimensional grid or road network, the straight-line Euclidean distance between two points is an admissible heuristic because no physical path can be shorter than a straight line.

Guiding Exploration and Guaranteeing Optimality

When A* pops the goal node from the priority queue, the admissibility of \(h(n)\) guarantees that the path found is optimal. Suppose a suboptimal path to the goal has already been discovered with cost \(C > C^*\), where \(C^*\) is the true shortest-path cost. Any node \(n\) along the optimal path will have:

\[f(n) = g(n) + h(n) \le g(n) + h^*(n) = C^* < C\]

Because \(f(n)\) for nodes on the optimal path is strictly less than \(C\), A* will always expand the nodes leading to the optimal path before it ever pops the suboptimal goal node from the queue.

Without a heuristic, setting \(h(n) = 0\) reduces A* to Dijkstra's algorithm, which explores outward in all directions based solely on \(g(n)\). An admissible heuristic focuses the search toward the goal, pruning large portions of the graph that cannot possibly beat the best-known path. The closer \(h(n)\) is to \(h^*(n)\) without exceeding it, the fewer nodes A* needs to expand, making it both complete and optimally efficient for classical shortest-path problems.