Heuristic Function Design and Admissibility / Consistency — Beginner-Friendly Notes

1. What Is a Heuristic

$h(n)$ = estimate of cheapest true cost from $n$ to goal $h*(n)$. Good heuristics make A* fast; bad ones make it slow or non-optimal.

2. Admissibility — Never Overestimate

Admissible iff for every node $n$: $h(n) \leq h*(n)$ (optimistic, never thinks it is farther than reality).

• Example: straight-line distance ≤ actual road distance → admissible.
• 8-puzzle: misplaced tiles ($h1$) and Manhattan distance ($h2$) are admissible; if you count diagonal moves as 1, it would be inadmissible if it overestimates.

If $h$ is admissible, A is optimal* (tree search) — standard exam theorem.

3. Consistency (Monotonicity) — Stronger Condition

Consistent iff for every edge $n \rightarrow n'$ with cost $c(n,n')$: $h(n) \leq c(n,n') + h(n')$ (triangle inequality), and $h(goal)=0$.

• Means $f(n)=g(n)+h(n)$ never decreases along a path — $f$ is monotonic.
• Consistent ⇒ Admissible (but not vice versa).
• With consistency, A* graph search is optimal and never needs to re-open closed nodes.

Beginner mnemonic: Admissible = optimistic. Consistent = optimistic and smooth.

4. Dominance — Which Heuristic to Pick

$h2$ dominates $h1$ if for all $n$, $h2(n) \geq h1(n)$ and both admissible → $h2$ is better (expands fewer nodes, still optimal).

• Example: Manhattan $h2$ dominates misplaced-tiles $h1$ for 8-puzzle → always prefer $h2$.
• Best $h$ is $h*(n)$ itself (perfect), but computing it is as hard as solving the problem.

5. How to Design Heuristics (3 tricks)

1. Relax the problem: allow illegal moves, cost of relaxed problem ≤ real cost → admissible. (e.g., allow tiles to move anywhere → misplacedtiles).
2. Use pattern database: precompute exact costs for subproblems.
3. Learn it: train a model to predict $h*(n)$.

6. Common Exam Traps

• Admissible does not mean "good" — $h(n)=0$ is admissible (then A* = UCS) but not informative.
• Inconsistent but admissible $h$ can still be optimal with tree search, but graph search may need to re-expand nodes.

7. One-Line Summary

A heuristic is admissible if it never overestimates $h*(n)$ (ensuring A* optimality) and consistent if $h(n) \leq c(n,n')+h(n')$ (ensuring monotonic $f$ and graph-search optimal efficiency); dominant heuristics among admissible ones should be preferred.

8. Quick Self-Check

1. Is $h(n)=h*(n)+2$ admissible?
2. Does consistent imply admissible? Does admissible imply consistent?
3. Which dominates for 8-puzzle: $h1=2$, $h2=4$ when truth is 5?