A* Search

Uninformed search treats all unexplored directions alike and therefore wastes effort expanding nodes leading away from the goal. Greedy search uses a heuristic estimate of remaining distance but ignores the cost already paid, so it can commit to a cheap-looking route that turns out to be expensive. A* combines both signals.

Each node is scored by f(n) = g(n) + h(n), where g is the known cost of the best path found to n so far and h estimates the remaining cost from n to a goal. Since f is an estimate of the total cost of a solution passing through n, always expanding the smallest f pursues the route that currently looks cheapest overall.

Optimality rests on a condition Russell and Norvig state precisely: h must be admissible, meaning it never overestimates the cost of reaching the goal. Because g is the true cost incurred, an admissible h makes f never overestimate the true cost of a solution through that node. Admissible heuristics are optimistic by nature, and that optimism is what stops A* from discarding a route that is genuinely best. For graph search a slightly stronger condition, consistency, is normally required as well.

The heuristic determines efficiency rather than correctness. With h identically zero, A* reduces to uniform-cost search and is optimal but explores broadly. With a heuristic close to the true remaining cost it drives almost directly to the goal. Stronger admissible heuristics are therefore the main lever on performance, and much of classical search research is about constructing them.

For route-finding on a road map, g is the distance actually driven to reach a town and h is the straight-line distance from that town to the destination. Straight-line distance is admissible because no road can be shorter than the direct line.

The search expands the town minimizing driven-distance plus straight-line-remaining. A town slightly off the direct line but reached cheaply may still be expanded before one that lies nearer the destination but required a long detour to reach.

Replacing straight-line distance with something that could overestimate, say a guess inflated for safety, breaks the optimality guarantee. A* may then return a suboptimal route because it pruned the genuinely best one on the strength of an overestimate.