Admissible Heuristic

An admissible heuristic is a heuristic function that never overestimates the cost to reach the goal from any given state. Formally, for a heuristic h(n) estimating the cost from node n to the goal, admissibility requires that h(n) ≤ h*(n) for all n, where h*(n) is the true optimal cost. This property is the guarantee of optimality in A* search: if the heuristic is admissible, A* will never discard an optimal path in favor of a suboptimal one, because it never believes a path is better than it truly is.

Admissibility is not merely a technical condition. It is an epistemic commitment: a promise that the estimate is conservative, that the algorithm's optimism is bounded. This is the same structure that underlies conservative estimation in statistics, lower bounds in optimization, and proof by contradiction in logic. The admissible heuristic does not need to be accurate; it needs to be pessimistic in the right direction.

Admissibility and Consistency

A stronger property is consistency (or monotonicity): a heuristic is consistent if its estimate never decreases by more than the actual step cost between adjacent nodes. Formally, h(n) ≤ c(n, n') + h(n') for all edges (n, n'). Consistency implies admissibility, but not vice versa. A consistent heuristic guarantees that A* never needs to re-expand a node, which simplifies the algorithm and improves efficiency.

Most practical heuristics are both admissible and consistent. The straight-line distance heuristic in pathfinding is admissible because the shortest path between two points is a straight line; it is consistent because the triangle inequality holds in Euclidean space. The Manhattan distance heuristic is similarly admissible and consistent on grid worlds. The zero heuristic — h(n) = 0 for all n — is trivially admissible and consistent, but it reduces A* to Dijkstra's algorithm, eliminating the benefit of informed search.

Constructing Admissible Heuristics

The standard method for constructing admissible heuristics is relaxation: solve a simplified version of the problem in which some constraints are removed, and use the optimal solution to the relaxed problem as the heuristic for the original problem. In the sliding tile puzzle, relaxing the constraint that tiles cannot occupy the same position yields the Manhattan distance heuristic. In pathfinding, relaxing the constraint that movement must follow roads yields the straight-line distance heuristic.

This method reveals a deep connection: the admissible heuristic is a solution to an easier problem that bounds the solution to the harder problem. The easier problem is the original problem with constraints relaxed; the harder problem is the original problem with all constraints intact. The heuristic is the cost of the relaxed path; the true cost is the cost of the constrained path. Since relaxing constraints can only reduce cost, the heuristic is guaranteed to be admissible.

The admissible heuristic is not a guess. It is a proof — a demonstration that the goal is at least as far as it appears. In a world of uncertainty, this conservative certainty is the foundation of optimal search.