Heuristic Functions: Definition and Properties
What you'll learn: You'll understand what makes a heuristic function effective for informed search and the critical properties of admissibility and consistency.
What Is a Heuristic Function?
A heuristic function h(n) estimates the cost from a given state n to the nearest goal state. Think of it as an educated guess or "rule of thumb" that guides your search toward the goal without exploring every possibility.
For example, in navigating from one city to another, straight-line distance is a heuristic—it tells you approximately how far you still need to go, even though the actual road might be longer.
Key Properties
Admissibility
A heuristic is admissible if it never overestimates the true cost to reach the goal. Formally: h(n) ≤ h*(n), where h*(n) is the actual optimal cost from n to the goal.
Analogy: An admissible heuristic is like an optimistic friend who always underestimates travel time. They might say "15 minutes away" when it's really 20, but they'll never say "30 minutes" when it's only 15. This optimism ensures you won't prematurely abandon potentially optimal paths.
Consistency (Monotonicity)
A heuristic is consistent if, for every state n and its successor n' reached by action with cost c, the estimated cost satisfies: h(n) ≤ c + h(n').
This means the heuristic respects the "triangle inequality"—the direct estimate from n should not exceed the cost to get to n' plus the estimate from there. Consistent heuristics are always admissible, and they ensure that once a node is expanded in graph search, you've found the optimal path to it.
Why These Matter
Admissibility guarantees that search algorithms like A* find optimal solutions. Consistency provides additional efficiency benefits, preventing redundant exploration.
Key Takeaway: A good heuristic function never overestimates (admissible) and provides coherent estimates between neighboring states (consistent), enabling efficient, optimal pathfinding in informed search algorithms.