A* Search

A* expands the node with the lowest estimated total cost:

where $g(n)$ is the cost of the path from start to $n$ and $h(n)$ is the heuristic estimate of cost-to-go from $n$ to a goal.

Algorithm

``` function A_star(initial, goal, h): frontier = PriorityQueue([(h(initial), 0, initial, [])]) visited = {} while frontier not empty: (f, g, state, path) = frontier.pop_min() if state is goal: return path if state in visited and visited[state] <= g: continue visited[state] = g for action in actions(state): next = transition(state, action) g_next = g + step_cost(state, action) f_next = g_next + h(next) frontier.push((f_next, g_next, next, path + [action])) return failure ```

Optimality

A* with an admissible heuristic finds the optimal solution. Sketch: at the moment we expand a goal node $G$, every node with $f(n) < f(G)$ has been expanded. Since $h$ is admissible, $f(G) = g(G) =$ actual cost of the path to $G$. No cheaper path can exist or its $f$-value would be lower and we'd have expanded its goal first.

With a consistent heuristic, A* is also optimally efficient: no algorithm using the same heuristic can guarantee finding the optimal solution by expanding fewer nodes (modulo ties).

Heuristic quality matters

• $h = 0$: A* degenerates to uniform-cost search.
• $h = h^*$: A* expands only nodes on the optimal path. Perfect oracle.
• In between: A* expands $b^{d_{\text{eff}}}$ nodes where $d_{\text{eff}}$ depends on how informative $h$ is. Small improvements in heuristic quality compound exponentially.

Memory

A*'s biggest weakness: it stores the entire frontier in memory. For really large state spaces this exhausts RAM long before time runs out. Solutions:

• IDA*: iterative deepening with cost cutoffs. $O(bd)$ memory.
• SMA*: keeps a memory budget; drops worst nodes when full.
• Beam search: keep only the top-$k$ frontier nodes. Loses optimality but stays bounded.

When A* is the right answer

Any time you have:

• A discrete state space
• Known transitions and costs
• An admissible heuristic

It's the default; deviate only when memory or specific structure makes something else better.