## Definition **Admissibility** and **consistency** are two properties of a heuristic $h$ that determine whether [[A Star Algorithm|A*]] returns an optimal solution. ## Admissibility $h$ is **admissible** if it never overestimates the true cost to reach a goal: $h(n) \leq h^*(n) \quad \forall n$ where $h^*(n)$ is the optimal remaining cost from $n$. **Guarantee:** A\* with an admissible heuristic returns an optimal solution **on tree search**. ## Consistency (Monotonicity) $h$ is **consistent** if for every node $n$ and every successor $n'$ reached by action $a$: $h(n) \leq c(n, a, n') + h(n')$ In words: the heuristic estimate at a parent never exceeds the action cost plus the estimate at the child. The heuristic obeys a triangle inequality with respect to step costs. **Guarantee:** A\* with a consistent heuristic returns an optimal solution **on graph search** (with a closed list). Once a node is expanded, its $g$-value is optimal — no need to re-open it. ## Relationship $\text{Consistent} \implies \text{Admissible}$ The converse is not true: there are admissible-but-not-consistent heuristics, though they're rare in practice. Almost all "natural" heuristics — Manhattan distance, straight-line distance, misplaced tiles — are consistent. ## Why Both Matter - **Tree search:** only admissibility needed. - **Graph search:** consistency matters because nodes can be reached by multiple paths. Without it, A* may need to re-open nodes when a better path is discovered. ## Example: 8-Puzzle Heuristics - $h_1$ = number of misplaced tiles. Admissible (each misplaced tile needs at least 1 move). Consistent (each move can fix at most one misplaced tile). - $h_2$ = sum of Manhattan distances of each tile to its goal. Admissible (each tile needs at least its Manhattan-distance moves). Consistent. Both are consistent; $h_2$ dominates $h_1$ — A* with $h_2$ expands strictly fewer nodes. ## Designing Heuristics - **Relaxation:** drop constraints from the problem; solve the relaxed version optimally; the cost is an admissible heuristic for the original. - **Pattern databases:** precompute optimal costs for sub-problems. - **Max of multiple heuristics:** $h(n) = \max(h_1(n), h_2(n), \dots)$ is admissible if each $h_i$ is. ## Related - [[A Star Algorithm]] - [[Heuristic Search]] - [[IDA Star Algorithm]]