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
Résumé
Introduit l’algorithme A*, qui ordonne la recherche par la somme du coût déjà engagé et d’une estimation heuristique du coût restant, et démontre son optimalité lorsque l’heuristique ne surestime jamais.
Pourquoi c’est important
Il a mis la recherche heuristique sur des bases rigoureuses en identifiant l’admissibilité comme la condition précise sous laquelle l’usage d’une heuristique ne coûte rien en qualité de solution. A* reste l’algorithme de recherche informée par défaut en routage, en planification et dans les jeux.