Heuristic Search

Heuristic search is the family of search methods that use problem-specific knowledge, in the form of an evaluation function, to decide which candidate to explore next, instead of expanding states in a fixed blind order. Where breadth-first and depth-first search treat every unexplored state as equally promising, heuristic search ranks them: it keeps a frontier of states waiting to be expanded, always takes the one that looks best, and thereby concentrates effort near the likely solution. The central trade-off is between the quality of the guidance and its cost: a better estimate shrinks the number of states examined, but an estimate that is expensive to compute, or that misleads the search, can erase the gain.

Best-first search is the general scheme, and it differs from one variant to the next only in what the evaluation function f(n) measures. The frontier is a priority queue ordered by f(n), and the node with the lowest value is expanded first. Greedy best-first search sets f(n) = h(n), the estimated remaining cost to the goal, and so chases whatever looks closest. It is often very fast, but it is neither complete on graphs with loops unless repeated states are handled, nor optimal: it can march confidently toward a goal along an expensive route because it ignores the cost already paid. Uniform-cost search, which Edsger Dijkstra's 1959 shortest-path algorithm resembles, makes the opposite choice, f(n) = g(n), the cost accumulated so far; it is optimal but has no sense of direction, so it expands in widening rings around the start.

A-star, published by Peter Hart, Nils Nilsson and Bertram Raphael in 1968, combines the two by ranking nodes by f(n) = g(n) + h(n). Their paper, A Formal Basis for the Heuristic Determination of Minimum Cost Paths in IEEE Transactions on Systems Science and Cybernetics, grew out of work at the Stanford Research Institute on Shakey, the mobile robot that had to plan routes through rooms of obstacles. Here g(n) is the actual cost of the best known path from the start to n, h(n) is the heuristic estimate of the cost from n to the goal, and so f(n) estimates the cost of the cheapest solution passing through n. The authors proved that if h never overestimates the true remaining cost, a property called admissibility, then A-star returns an optimal path whenever one exists. A short erratum in 1972 clarified that the stronger condition of consistency is what guarantees that a node never needs to be reopened once expanded. Setting h = 0 recovers uniform-cost search, and setting g = 0 recovers greedy search, so both are special cases of one idea.

The optimality argument is short and worth knowing. Suppose A-star is about to expand a goal node reached by a suboptimal path with cost C. Some node on the true optimal path must still be on the frontier, and its f value, by admissibility, is at most the optimal cost, which is less than C. That node would have been chosen first, so the suboptimal goal cannot be selected. Dechter and Pearl later showed, in 1985, that among algorithms using the same heuristic information A-star is optimally efficient: no other optimal algorithm is guaranteed to expand fewer nodes. The practical limit is therefore not time but space, since A-star remembers every frontier node. Korf's iterative-deepening A-star (IDA-star, 1985) trades some repeated work for memory that grows only linearly with solution depth, and weighted A-star, which inflates h by a factor, accepts a bounded loss in solution quality for a large speedup.

The most common misconception is that A-star is simply a smarter shortest-path algorithm than Dijkstra's, always to be preferred. It is better only when a good, cheap, admissible h is available; with a poor heuristic it degenerates toward uniform-cost search with extra overhead, and an overestimating heuristic silently destroys the optimality guarantee. A second pitfall is conflating the evaluation function f with the heuristic h: h is the knowledge about the problem, while f is the ordering rule built on top of it. Choosing between greedy and A-star is a decision about whether optimality or speed matters.

A-star is still everywhere that an agent must find a cheap route through a known space. Video-game pathfinding, robot navigation, logistics and mapping systems rely on it or its descendants, often with extras such as precomputed landmarks for the heuristic or hierarchical maps. Automated planners derive h automatically from relaxed versions of the problem, and sliding-tile puzzles and Rubik's Cube have been solved optimally with IDA-star and pattern databases. In game playing the same pattern, a learned or hand-built evaluation steering a selective search, runs through chess engines and through AlphaGo's use of neural networks to guide Monte Carlo tree search. Many of these systems replace a hand-written h with a learned one, which keeps the architecture while giving up the formal guarantee unless it is separately checked.

Read heuristic search as informed ordering of the frontier: the search is the same, but the evaluation function decides what is examined first, and when that function is admissible, as in A-star, the shortcut costs nothing in correctness.