Course contentsShow
← Computer Science
Lesson 1003 of 2,87223. Shortest Path AlgorithmsFree lesson

Admissible Heuristics

Define admissible heuristics that never overestimate the true cost and guarantee A* finds optimal solutions.

Admissible Heuristics

What You'll Learn

You'll understand what makes a heuristic "admissible" and why this property guarantees that A* finds optimal shortest paths.

The Core Idea

An admissible heuristic is a heuristic function h(n) that never overestimates the true cost to reach the goal from node n. In other words, your heuristic is always optimistic—it might underestimate or guess exactly right, but it never guesses too high.

Think of it like estimating travel time to the airport. If you say "I need at least 20 minutes" but the actual fastest route takes 30 minutes, you've overestimated (inadmissible). But if you say "I need at least 40 minutes" when the true minimum is 30, you've underestimated (admissible). An admissible heuristic is like a best-case scenario that reality can only meet or exceed.

Why Admissibility Matters

When your heuristic is admissible, A* is guaranteed to find the optimal (shortest) path to the goal. Here's why: because h(n) never overestimates, A* never prematurely dismisses a path that might actually be optimal. The algorithm remains optimistic about every path's potential, ensuring it explores thoroughly enough to find the true shortest route.

Mathematically, for all nodes n:

h(n) ≤ actual_cost(n, goal)

Common Examples

  • Euclidean distance for grid pathfinding (straight-line distance is never longer than any actual path)
  • Manhattan distance for grid-restricted movement (minimum steps ignoring obstacles)

Key Takeaway: An admissible heuristic never overestimates the cost to reach the goal, which guarantees A* will find the optimal solution—making it both efficient and correct.