A Formal Basis for the Heuristic Determination of Minimum Cost Paths
Peter E. Hart, Nils J. Nilsson, Bertram Raphael · 1968 · IEEE Transactions on Systems Science and Cybernetics, SSC-4(2), 100–107
Summary
Introduces the A* algorithm, which orders search by the sum of the cost already incurred and a heuristic estimate of the cost remaining, and proves it optimal when the heuristic never overestimates.
Why it matters
It put heuristic search on a rigorous footing by identifying admissibility as the precise condition under which using a heuristic costs nothing in solution quality. A* remains the default informed search algorithm in routing, planning, and games.