## Definition **A\* search** is the most widely used heuristic search algorithm. It expands the node with the lowest **$f(n) = g(n) + h(n)$**, where $g(n)$ is the cost from the start and $h(n)$ is an admissible heuristic estimate of the remaining cost. ## Algorithm ``` frontier ← priority queue ordered by f(n) g[start] ← 0 insert(frontier, start) while frontier non-empty: n ← pop min f if isGoal(n): return path(n) for each successor n' of n: tentative_g ← g[n] + c(n, n→n') if tentative_g < g[n']: g[n'] ← tentative_g f[n'] ← tentative_g + h(n') insert_or_update(frontier, n') return failure ``` ## Properties - **Complete:** yes (with positive action costs). - **Optimal:** yes — if $h$ is **admissible** for tree search, or **consistent** for graph search (see [[Admissibility and Consistency of Heuristics]]). - **Optimally efficient:** for a given consistent heuristic, no algorithm guaranteed to find the optimal solution expands fewer nodes than A*. ## Why It Works The key invariant: when A* pops a node from the frontier, it has found the optimal path to that node. Proof relies on consistency: $f$-values are non-decreasing along any path. ## Limitations - **Space-heavy.** Keeps all generated nodes in memory. For large state spaces, memory exhaustion before time exhaustion. - **Sensitive to heuristic quality.** A bad heuristic degrades A* toward [[Uniform Cost Search]]. ## Variants - **[[IDA Star Algorithm]]** — iterative-deepening variant with linear space. - **SMA\*** (Simplified Memory-bounded A*) — drops worst-$f$ nodes when memory fills. - **Weighted A\*** — $f(n) = g(n) + w \cdot h(n)$ with $w > 1$: faster, no longer optimal. - **Bidirectional A\*** — search forward from start and backward from goal simultaneously. ## When to Use - Pathfinding (games, robotics, route planning). - Puzzle solving with strong heuristics. - Planning with informative cost estimates. ## Related - [[Heuristic Search]] - [[Uniform Cost Search]] - [[IDA Star Algorithm]] - [[Admissibility and Consistency of Heuristics]]