The encyclopedia · R&D & Science · Technical decision · 1968
A* used an admissible heuristic to find a shortest path without exploring everything
Hart, Nilsson and Raphael's 1968 A* search combined cost so far and an admissible heuristic, guaranteeing a shortest path while expanding few nodes.
Stanford Research Institute
the move
Finding a cheapest route through a large graph is a classic problem. Breadth-first is guaranteed but explores everything; greedy best-first is fast but can find a path that is not cheapest.
The 1968 paper by Hart, Nilsson and Raphael defined A*: expand the node with smallest f = g + h, where g is the cost so far and h is a heuristic estimate of the rest. If h is admissible, meaning it never overestimates, A* is guaranteed to return an optimal path.
The paper proved A* expands the fewest nodes of any optimal algorithm with that heuristic. The trade is precise: a good h buys speed without giving up the guarantee, which is why A* is the standard for route and game planning.
why it works
- An admissible heuristic focuses the search without ever ruling out the true optimum.
- The f = g + h score balances how far we've gone against how far is left.
- A* is provably optimal yet expands far fewer nodes than uninformed search.
- It is a template, so a domain just supplies the right heuristic.
what transfers
Do not only expand the cheapest known path or greedily chase the goal. Score each option as cost so far plus an estimate that never overstates, which keeps you optimal and fast.
what came after
A* became the backbone of pathfinding in games, robots, maps and route planners, and the starting point for a large family of heuristic search algorithms. Its optimality proof and the notion of an admissible heuristic remain central.
references
spotted an error? The archive wants to know.