Pathfinding problems show up everywhere: routing packets through networks, moving robots through warehouses, and planning actions in games. Many of these problems can be modelled as finding the lowest-cost path in a graph, where each edge has a cost and the goal is to minimise the total cost. Heuristic search algorithms—especially A*—are popular because they can be both fast and optimal when used correctly. If you are learning search theory in an AI course in Delhi, admissibility is one of the most important ideas to master because it connects “smart guessing” with provable correctness.
This article explains what heuristic admissibility means and shows, in a clear mathematical way, why admissible heuristics allow A* to guarantee optimal paths under specific cost constraints.
1) Core Definitions: Costs, Estimates, and What “Admissible” Really Means
Consider a graph where each state (node) is a location, and each action (edge) has a non-negative cost. Let:
- g(n)g(n)g(n) be the cost from the start node to a node nnn.
- h(n)h(n)h(n) be a heuristic estimate of the cheapest cost from nnn to the goal.
- h∗(n)h^*(n)h∗(n) be the true cheapest cost from nnn to the goal.
- f(n)=g(n)+h(n)f(n) = g(n) + h(n)f(n)=g(n)+h(n) be the estimated total cost of a solution path through nnn.
A heuristic is admissible if it never overestimates the true remaining cost:
∀n, 0≤h(n)≤h∗(n)\forall n,\; 0 \le h(n) \le h^*(n)∀n,0≤h(n)≤h∗(n)Intuitively, admissibility means the heuristic is “optimistic.” It may underestimate, but it cannot exaggerate the remaining distance-to-go.
2) Why A* Uses Admissibility to Guarantee Optimality
A* expands nodes in increasing order of f(n)f(n)f(n). The key claim is:
If edge costs are non-negative and hhh is admissible, then A* (with standard graph-search handling) returns an optimal path to the goal.
The main inequality behind the proof
Take any node nnn on an optimal path to the goal. Because h(n)≤h∗(n)h(n) \le h^*(n)h(n)≤h∗(n), we get:
f(n)=g(n)+h(n)≤g(n)+h∗(n)f(n) = g(n) + h(n) \le g(n) + h^*(n)f(n)=g(n)+h(n)≤g(n)+h∗(n)But g(n)+h∗(n)g(n) + h^*(n)g(n)+h∗(n) equals the cost of the optimal solution passing through nnn. Let the optimal solution cost be C∗C^*C∗. Then:
f(n)≤C∗f(n) \le C^*f(n)≤C∗This simple inequality is powerful: every node on an optimal solution path has an fff-value that does not exceed the optimal solution cost.
3) Proof Sketch: Why the First Goal Found Has Optimal Cost
Let A* select nodes with the smallest fff first. Suppose, for contradiction, that A* returns a goal node GGG with solution cost g(G)=Cg(G) = Cg(G)=C where C>C∗C > C^*C>C∗ (a suboptimal solution).
Consider the optimal path to the goal with cost C∗C^*C∗. There must exist at least one frontier node nnn on that optimal path that A* has not yet expanded at the moment it selects GGG. From the inequality above, that node satisfies:
f(n)≤C∗f(n) \le C^*f(n)≤C∗Since C∗<CC^* < CC∗<C, we have f(n)<Cf(n) < Cf(n)<C. But at a goal node, h(G)=0h(G)=0h(G)=0, so f(G)=g(G)=Cf(G)=g(G)=Cf(G)=g(G)=C. Therefore:
f(n)<f(G)f(n) < f(G)f(n)<f(G)A* always selects the node with the smallest fff. So it should have selected nnn before selecting GGG. That contradicts the assumption that A* chose GGG first. Hence the returned goal cannot be suboptimal; A* must return a goal with cost C∗C^*C∗.
This is the core optimality argument taught in many curricula, including an AI course in Delhi, because it shows how a single constraint—“never overestimate”—is enough to ensure correctness.
4) The “Specific Cost Constraints” That Make the Proof Work
Admissibility alone is not magic; it relies on cost constraints and algorithm details:
Non-negative edge costs
The proof assumes all step costs are ≥0\ge 0≥0. If negative edges exist, g(n)g(n)g(n) can decrease later, breaking the “expand in best order” logic. In practice, most pathfinding cost models enforce non-negativity (distance, time, energy).
Proper handling of repeated states (graph search)
In a graph (not a tree), the same state can be reached via different paths. A* needs a consistent way to track best-known ggg-values. Many implementations use a closed set plus updates when a better path is found.
Consistency strengthens the guarantee
A stronger condition, consistent (monotone) heuristics, satisfies:
h(n)≤c(n,n′)+h(n′)h(n) \le c(n,n’) + h(n’)h(n)≤c(n,n′)+h(n′)for every edge (n,n′)(n,n’)(n,n′) with cost c(n,n′)c(n,n’)c(n,n′). Consistency implies admissibility and also guarantees that once a node is expanded, its best ggg is final—making implementations simpler and more efficient.
Conclusion
Heuristic admissibility is the bridge between efficiency and proof-level correctness in heuristic search. By ensuring h(n)≤h∗(n)h(n) \le h^*(n)h(n)≤h∗(n), you guarantee that A* never “talks itself into” a path that looks cheaper than the truly optimal route when it is not. Under non-negative step costs and standard A* mechanics, admissibility gives a clean contradiction proof that the first goal found must be optimal. If you are revising these ideas for an AI course in Delhi, focus on the key inequality f(n)≤C∗f(n) \le C^*f(n)≤C∗ for nodes on the optimal path—it is the mathematical heart of the optimality guarantee.