4.8 Informed search: greedy best-first and A*

What this is and why it exists

Informed search is where knowledge about the problem enters the algorithm, in the form of a guess about how far each state is from the goal. Two methods use that guess differently, and the difference is one term. This is the algorithm everyone quotes and few can justify; the bookkeeping is the whole lesson, and so is watching the memory fill up while the search is still working perfectly.

The vocabulary

• Heuristic — an estimate of the remaining cost from a state to a goal.
• Evaluation function — the score deciding which state to expand next.
• g — the cost of the path from the start to this state, which is known.
• h — the estimated cost from this state to a goal, which is a guess.
• f — the score combining them.
• Open list — the fringe of generated but unexpanded states.
• Closed list — the states already expanded.
• Best-first search — expanding whichever state scores best.

The mental model

All informed search is one idea: score each state, expand the best-scoring one. The score is the evaluation function, and the different algorithms are different scores. The problem knowledge lives entirely in the heuristic, which is where a person tells the algorithm something about the problem that the problem definition alone does not say — for a road map, the straight-line distance to the destination; for a sliding-tile puzzle, how many tiles are out of place.

Greedy best-first search scores each state by the heuristic alone. Expand whichever state looks closest to the goal. It is fast, it frequently finds a solution quickly, and it has a specific and instructive failure.

Consider a map where the destination lies to the east. Greedy search takes the eastward road at every junction, because eastward states have the smallest straight-line distance. If the eastward road leads into a dead-end valley whose exit is to the west, the search must at some point expand a state that looks worse than where it has been — and it will not, until every eastward option has been exhausted. On a tree search with no record of visited states it is worse still: it can oscillate between two states forever, each looking best when reached from the other. The reason is exactly that it ignores what has already been spent, so a state ten hours down a wrong road looks as attractive as one ten minutes down a right one, provided they are the same distance from the goal as the crow flies.

Adding that missing term is the whole fix. Score each state by the cost already spent to reach it plus the estimate of what remains — read aloud as "f of n equals g of n plus h of n". Now the score estimates the total cost of the best solution through this state, which is the quantity you actually want to compare. A state far down an expensive road carries that expense in its score, so a promising direction that turned out costly stops being chosen. The two quantities must be kept separate in your bookkeeping, and mixing them up is the practical difficulty of tracing this by hand — one is known and one is guessed, and they play different roles in every proof about the algorithm.

Work a road map by hand once, because the trace is where the understanding is. Take a small map with a dozen towns, road distances between them, and straight-line distances from each town to the destination. For every state you generate, write down three numbers: the cost so far, the estimate remaining, and their sum. Expand the smallest sum. Keep the open list visible as a list you rewrite each step.

Three things become obvious in the doing, and only in the doing. The heuristic prunes enormously — whole regions of the map are never expanded, because their total scores are worse than routes already under consideration, which is the entire benefit over uninformed search. The open list grows anyway, and you will find yourself writing more states than you expected. And when a shorter route to an already-generated state appears, you must update that state's cost rather than adding a duplicate, which is the bookkeeping step people omit.

Now the limitation that matters in practice. The method keeps every generated state in memory — the open list of candidates and the closed list of expanded states — and memory runs out long before time does. A search generating a million states a second fills a typical machine in a few minutes, and the failure is abrupt: the algorithm was working correctly, exploring sensibly, making progress, and then it stops. This is the single most common way this algorithm fails in real use, and it surprises people because nothing was wrong.

Three families of response exist, and knowing they exist is enough here. Depth-first variants apply the same scoring within a depth-first search, using a cost threshold that rises on each pass — memory drops to linear, at the price of re-expanding states, which is the same trade iterative deepening made. Memory-bounded variants run normally until memory is full and then discard the worst-scoring candidates, remembering enough about them to regenerate them if needed. And weighted variants multiply the heuristic term by a factor greater than one, which makes the search greedier and much faster, and gives up the optimality guarantee in a bounded way — the solution found is at most that factor worse than the best. In practice this last one is what people reach for when a good-enough answer soon beats the best answer never.

Two closing points that connect this topic forward. The quality of the heuristic decides everything: a heuristic returning zero everywhere reduces the method to uniform-cost search, and a perfect heuristic walks straight to the goal expanding nothing else. Everything real sits between, and the effort spent designing a better estimate usually pays more than any change of algorithm. And the guarantee that this method finds the cheapest solution is not unconditional — it holds only when the heuristic satisfies a specific property, which the next topic states, proves, and shows you how to test.

What you should now be able to explain or do

State the common shape of informed search and say where problem knowledge enters. Explain what greedy best-first scores by and construct the case where it fails. Say why ignoring the cost already spent is what causes that failure. Write the combined score in words and keep the two quantities separate while tracing. Work a full trace on a road map, including updating a state when a cheaper route to it is found. Explain why memory rather than time is the binding limit. Name the three families of response and what each trades. Say what a zero heuristic and a perfect heuristic each reduce the method to.

Check yourself