## Definition **Heuristic search** (or informed search) uses a **heuristic function** $h(n)$ that estimates the cost of the cheapest path from node $n$ to a goal. Heuristics inject domain knowledge into [[State Space Search]], allowing far larger problems to be solved than [[Uninformed Search]] can handle. ## The Heuristic Function $h(n)$: $S \to \mathbb{R}_{\geq 0}$ — an estimate of the remaining cost to reach a goal from state $n$. By convention $h(\text{goal}) = 0$. ## Properties That Matter ### Admissibility $h$ is **admissible** if it *never overestimates* the true remaining cost $h^*(n)$: $h(n) \leq h^*(n) \quad \forall n$ Admissibility guarantees [[A Star Algorithm|A*]] returns an optimal solution on a tree search. ### Consistency (Monotonicity) $h$ is **consistent** if for every node $n$ and every action $a$ leading to $n'$: $h(n) \leq c(n, a, n') + h(n')$ Consistent heuristics are always admissible. Consistency is the stronger property required for optimality on **graph search** (with closed lists). ## Common Heuristics - **Manhattan distance** for grid pathfinding. - **Straight-line (Euclidean) distance** for road networks. - **Misplaced tiles** for the 8-puzzle. - **Relaxation-based heuristics** — solve a simplified version of the problem (e.g., ignore movement constraints) and use that as a lower bound. - **Pattern databases** — precompute optimal costs for sub-problems. ## Dominance If $h_2(n) \geq h_1(n) \forall n$ and both are admissible, $h_2$ *dominates* $h_1$. A dominant heuristic expands no more nodes than the dominated one. **Better heuristic = fewer expansions**, up to the limit of $h^* = h$ (no expansions beyond optimal path). ## Main Heuristic Algorithms - [[Greedy Best-First Search]] — orders by $h(n)$ alone. - [[A Star Algorithm]] — orders by $f(n) = g(n) + h(n)$. - [[IDA Star Algorithm]] — iterative deepening with $f$-cost limit. - [[Beam Search]] — keeps only the top-$k$ candidates. ## Related - [[State Space Search]] - [[A Star Algorithm]] - [[Admissibility and Consistency of Heuristics]]