Heuristic and Informed Search

Informed (heuristic) search strategies use a heuristic function h(n), an estimate of the cost from state n to the nearest goal, to decide which frontier node looks most promising. Greedy best-first search always expands the node with the lowest h(n), ignoring the cost already paid to reach it. On a small route map — Start with straight-line distance to Goal estimated at h=10, neighbor A with h=6, neighbor B with h=8 — greedy search immediately commits to A purely because its heuristic looks better, even if the actual road to A is a costly detour. This makes greedy search fast in practice but neither complete (it can loop forever chasing an attractive-looking dead end) nor optimal (a heuristic that underrates a costlier path can lead it straight past the truly cheapest route). Its appeal is speed: because it only ever consults h(n) and ignores how expensive the journey so far has been, greedy search often reaches a goal after expanding far fewer nodes than an exhaustive search would, which is exactly why it remains attractive whenever a fast, "good enough" answer matters more than a provably shortest one.

A* search fixes this by combining both pieces of information into a single evaluation function, f(n) = g(n) + h(n), where g(n) is the exact cost already paid to reach n and h(n) is the estimated cost remaining; A* always expands the frontier node with the lowest f(n). The algorithm was introduced by Hart, Nilsson, and Raphael in their 1968 paper formalizing heuristic graph search. Trace A* on Start→A (cost 2)→Goal (cost 5) versus Start→B (cost 2)→Goal (cost 4), with straight-line-distance heuristics h(Start)=7, h(A)=4, h(B)=5, h(Goal)=0: expanding Start yields A with f = g+h = 2+4 = 6 and B with f = 2+5 = 7; A* expands A first (lower f); from A, Goal is reached with f = (2+5)+0 = 7. But B was still in the frontier at f=7 too, and expanding B would reach Goal via B at f = (2+4)+0 = 6 — a cheaper total path. Because A* keeps comparing f-values across the whole frontier rather than committing early, it correctly returns the path through B (total cost 6) rather than through A (total cost 7), illustrating exactly how g(n) protects A* from greedy search's blind spot.

This behavior is not an accident of the specific numbers chosen — it is a general property that Hart, Nilsson, and Raphael proved formally: provided the heuristic never overestimates the true remaining cost (a condition called admissibility, developed fully in the next lesson), A* is guaranteed to return an optimal solution, and it does so while expanding no more nodes than any other optimal algorithm using the same heuristic information. This optimality guarantee, combined with the practical speed gained from a good heuristic, is why A* is the default choice for informed search across robotics path planning, puzzle solving, and game AI whenever a reasonable heuristic is available. It is worth stressing that this optimality proof is conditional: it depends entirely on the heuristic supplied to the algorithm having a specific mathematical property, admissibility, and an A* run with a heuristic that violates that property forfeits the guarantee and can return a suboptimal path just as greedy search can — which is exactly why heuristic design, the topic of the next lesson, is not a minor implementation detail but the crux of using A* correctly.

A heuristic h(n) is admissible if it never overestimates the true cost h*(n) of reaching the nearest goal from n — formally, 0 ≤ h(n) ≤ h*(n) for every state n. Straight-line distance is a natural admissible heuristic for route-finding, since no actual road can ever be shorter than the straight line between two points. For the 8-puzzle (sliding numbered tiles into a goal configuration), two standard admissible heuristics are the number of misplaced tiles (each misplaced tile needs at least one move to fix, so this never overestimates) and the sum of Manhattan distances each tile must travel to reach its goal position (since each single move shifts exactly one tile by one grid step). Comparing two admissible heuristics on the same problem, if h2(n) ≥ h1(n) for every state n, h2 is said to dominate h1, and Manhattan distance dominates misplaced-tile count because it accounts for how far, not just whether, each tile is displaced — a dominant heuristic guides A* to explore fewer nodes while remaining just as safely admissible.

A stronger property, consistency (sometimes called monotonicity), requires that for every state n and every successor n′ reached via an action of cost c, h(n) ≤ c + h(n′) — a form of triangle inequality stating the heuristic can't drop by more than the actual cost of a single step. Every consistent heuristic is automatically admissible, but the converse is not guaranteed. Consistency matters practically because it guarantees f(n) never decreases along any path in the search — once A* using a consistent heuristic expands a node, it has already found the optimal path to it, so the node never needs to be re-expanded at a lower cost later. Straight-line distance and Manhattan distance are both consistent as well as admissible, which is why they remain the standard textbook examples for A* in route-finding and puzzle domains, respectively. Without consistency, A*'s tree-search version remains optimal, but its graph-search version — the one that tracks an explored set to avoid the repeated-states problem discussed earlier — needs extra bookkeeping to handle nodes that are re-discovered at a lower cost after already being expanded, which is precisely the complication consistency eliminates.

Beyond hand-picking a heuristic, a systematic way to derive one is to solve a relaxed version of the problem — one with fewer restrictions than the original — and use the relaxed problem's exact solution cost as h(n). Manhattan distance, for instance, is exactly the solution cost of a relaxed 8-puzzle where a tile may move to any adjacent square even if occupied; dropping the occupancy restriction relaxes the problem and yields a heuristic that is provably admissible for the original. When multiple admissible heuristics h1, h2, …, hk are available, taking h(n) = max(h1(n), h2(n), …, hk(n)) yields a new heuristic that is still admissible (since none of the components ever overestimates) and dominates every individual one, making it a strictly better guide for A* without any additional risk of losing optimality. This is a common technique in practice — for the 8-puzzle, taking the maximum of misplaced-tile count and Manhattan distance costs almost nothing extra to compute and can never do worse than either heuristic alone, since a state's true value under the combined heuristic is simply whichever component heuristic currently gives the tightest, still-admissible estimate for that particular state.

A*'s optimality guarantee comes at a cost: it must retain every generated node in memory in case a cheaper path to it is discovered later, and in large state spaces this frontier can grow to consume all available memory well before a solution is found — a limitation A* shares with breadth-first and uniform-cost search, and one that becomes the binding constraint in practice long before running time does. Iterative-deepening A* (IDA*) addresses this by applying the same idea as iterative-deepening search from uninformed search, but using the f-cost bound instead of a raw depth bound: each iteration performs a depth-first search that prunes any branch whose f(n) exceeds the current bound, and if no goal is found, the bound is raised to the smallest f-value that exceeded the previous bound before the next iteration begins. Like plain DFS, IDA* needs memory only proportional to the longest path explored, a dramatic reduction from A*'s memory footprint, at the cost of repeating the shallow parts of the search on every iteration.

Simplified memory-bounded A* (SMA*) takes a different approach: it behaves like A* but, when memory fills up, it drops the frontier node with the highest f-value (the least promising node) to make room for new nodes, first recording that dropped node's f-value at its parent so the parent "remembers" that this branch was explored and how unpromising it looked, allowing the search to regenerate that subtree later only if every other option turns out worse. SMA* is complete if enough memory remains to hold at least one solution path, and it will find the optimal solution if that solution fits in the available memory, gracefully degrading to a best-effort answer only when memory is genuinely too small to guarantee optimality. Where IDA* trades memory for repeated computation on every iteration, SMA* trades memory for a more intricate bookkeeping scheme, forgetting and selectively re-deriving parts of the search tree as available memory demands — a more graceful, if more complex, response to the same underlying constraint.

In practice, the choice among greedy search, A*, and memory-bounded variants like IDA* and SMA* reflects a trade-off between solution quality guarantees and resource limits: greedy search is chosen when speed matters more than optimality and a decent heuristic exists; A* is chosen when memory is ample and an optimal (or provably good) solution is required, as in many robotics path-planning and puzzle-solving applications; and IDA* or SMA* are chosen when the state space is too large for A*'s memory footprint but an admissible heuristic is still available to prune the search intelligently, as is common in large combinatorial puzzles and real-time game AI pathfinding. None of these choices are exclusive to informed search, either — the same underlying tension between guaranteed solution quality and bounded resources reappears, in a very different form, in the local and metaheuristic optimization methods covered in the next module, which abandon path-based search altogether in favor of tracking a single current state.