Classical Search: From Breadth-First to A*

Long before anything was learned from data, artificial intelligence worked by searching. You describe the situation you are in, the moves available, and what counts as done - and then an algorithm walks the space of possibilities until it arrives. Route planning, puzzle solving, scheduling, and theorem proving are all the same problem in this framing, which is exactly why the framing is worth having.

A. What a search problem is

A search problem is five things: an initial state, the actions available in each state, a transition model saying where each action leads, a goal test, and a step cost for each action. The first three define the state space, the graph of everything reachable from the start.

The state space is never written down. It is generated one successor at a time, on demand, which is what allows these algorithms to work in spaces with more states than there are atoms in the observable universe. Nothing is enumerated that is not visited.

Every strategy below is judged on four questions. Is it complete - does it find a solution when one exists? Is it optimal - does it find the cheapest one? What is its time cost, in nodes generated, and its space cost, in nodes held at once? The answers are written in the branching factor $b$ and the depth $d$ of the shallowest goal.

B. Uninformed search, and the wall it hits

Breadth-first search expands the shallowest unexpanded node. It is complete whenever $b$ is finite, and it generates on the order of $b^d$ nodes when the goal test is applied as each node is generated (delay it to expansion, as uniform-cost search must, and it is $O(b^{d+1})$). It is also optimal, but only under a condition that is easy to skip past: it returns the shallowest goal, which is the cheapest goal only when every step costs the same. When step costs differ, uniform-cost search - expand the lowest $g(n)$, the cheapest path so far - is the right algorithm.

The famous problem with breadth-first search is not its running time. Because it holds the entire frontier, its memory is $O(b^d)$ as well, and Russell & Norvig draw the conclusion bluntly: the memory requirements are a bigger problem than the execution time. On their illustrative numbers, a search to depth 12 finishes in about thirteen days - tolerable, if the answer matters - and needs a petabyte of memory, which is not tolerable at all. Time is a nuisance; memory is a wall.

Depth-first search inverts the trade. It stores only the current path, $O(bm)$ for maximum depth $m$, and gives up both optimality and, on infinite or looping spaces, completeness.

Iterative deepening takes the good half of each: run depth-limited search with limit 0, then 1, then 2, until a goal appears.

Regenerating the upper levels on every pass looks wasteful, and is not. In a tree with a roughly constant branching factor almost every node lives in the bottom level, which is generated once. The repetition costs a constant factor; the memory saving is exponential. That is why iterative deepening is the default uninformed method when the space is large and the solution depth unknown.

C. Adding a heuristic

A heuristic $h(n)$ estimates the cost remaining from $n$ to a goal. The obvious way to use one is to expand whichever node looks closest, $f(n) = h(n)$ - greedy best-first search. On a road map with the straight-line-distance heuristic it heads almost directly for the destination.

It is also not optimal, because it ignores what the journey has already cost. A town near the destination might only be reachable the long way round, and greedy search will commit to that detour without ever comparing it to an alternative whose first step looked worse.

A* repairs precisely that omission:

$$f(n) = g(n) + h(n)$$

Cost already incurred plus cost estimated to come, so $f(n)$ estimates the total cost of a solution through $n$. Setting $h = 0$ recovers uniform-cost search; ignoring $g$ recovers greedy search; A* is the general case containing both.

Optimality then depends on two conditions on the heuristic.

Admissibility. $h$ must never overestimate the true remaining cost. Since $g$ is a cost actually paid, an optimistic $h$ makes $f$ a lower bound on the true cost of any solution through that node, so no genuinely-best route is ever pruned on the strength of an inflated guess. Straight-line distance qualifies, because no road is shorter than the direct line.

Consistency. For graph search - where a state can be reached by several paths - the stronger condition is

$$h(n) \le c(n, a, n') + h(n')$$

for every successor $n'$ reached by action $a$: a triangle inequality on the estimate. It makes $f$ non-decreasing along any path, so the first time A* expands a node it has already found the cheapest route to it. Every consistent heuristic is admissible.

Within the class of algorithms that extend paths from the root using the same heuristic, A* is optimally efficient: for a given consistent heuristic, no other optimal algorithm is guaranteed to expand fewer nodes. The remaining lever is the heuristic itself, and a standard way to build one is to solve a relaxed problem - drop a constraint, solve the easier version exactly, use its cost. Removing constraints cannot make a solution more expensive, so the result is admissible by construction.

D. Worth checking on a real map

The Arad-to-Bucharest corner of Russell & Norvig's Romania map is small enough to run three ways and compare. Uniform-cost search finds the 418 km route through Rimnicu Vilcea and Pitesti, expanding every city on the map to do it. Greedy search expands only four cities and returns the route through Fagaras - 450 km, exactly 32 km worse. A* returns the 418 km route while expanding fewer cities than uniform cost. Optimality and effort are separate properties, and the heuristic is what buys the second without spending the first.

The practical limit of A* is memory, not correctness: it keeps every generated node so that $f$ values remain comparable. Iterative-deepening A* trades repeated work for a far smaller footprint, exactly as iterative deepening did for breadth-first search.

E. When the path does not matter

All of the above keeps the path, which is essential for route finding and pointless for a timetable or a circuit layout, where only the final configuration is the answer. Local search holds one current state, moves to a neighbour, and forgets where it came from, so its memory does not grow with the search at all.

Plain hill climbing - always move to the best neighbour - gets stuck in three characteristic ways: at a local maximum, higher than its neighbours but not the highest; on a plateau, where neighbours score alike and there is no gradient to follow; and on a ridge, where no single move improves though a combination would. Random restarts help: if each attempt succeeds with probability $p$, the expected number of attempts is $1/p$.

Simulated annealing escapes differently. It picks a random neighbour, always accepts an improvement, and accepts a worsening move of size $\Delta E$ with probability $e^{-\Delta E/T}$. Bad moves are therefore common early, when the temperature $T$ is high, and rare later - the algorithm shakes the surface hard enough to bounce out of a local optimum, then gradually stops shaking. If the cooling schedule lowers $T$ slowly enough, the probability of finding a global optimum approaches 1, which is a statement about the limit rather than a promise about any schedule fast enough to run.

The figure below is a bumpy surface with seven local maxima and one global one. Pick a start: hill climbing walks uphill and stops on whichever bump it was standing on, and annealing wanders past several of them. Neither run is the lesson on its own, so the read-out also carries the rate - hill climbing reaches the optimum from 26.4% of the 201 starting states, counted exactly, which is the p in the expected 1/p restarts. Then move the temperature and watch the count of accepted worsening moves, because that count is the escape mechanism itself.

Where to go next

The training path Search and Heuristics works through all of this with quizzes and a runnable cell that searches the Romania map three ways. Adversarial Search and Minimax takes up the case where the obstacle is not distance but an opponent, and A* Search is the reference entry.