The A* algorithm
Three SRI researchers described a search combining the cost so far with an estimate of the rest, and proved that with an admissible estimate the path found is optimal.
Why it matters
A heuristic stopped being a guess: under a precise condition on the estimate, the search stays both fast and correct.
The algorithm grew out of route planning for the Shakey robot. Admissibility requires the estimate never to exceed the true cost. A* is still the standard path-planning algorithm, and the same idea of guided search runs through modern methods such as Monte Carlo tree search. In a correction of December 1972 (ACM SIGART Newsletter 37) the authors write that the paper proved A* admissible, that is, finding a minimal-cost path whenever one exists, if the estimate is a lower bound on the true cost, and optimal in the number of nodes expanded under a further consistency assumption; a reader showed that the proof of optimality did not use that assumption, so the result holds more generally, while consistency still lets a closed node stay closed.