Recherche A*

Un algorithme de recherche best-first sur graphe qui ordonne l'expansion des nœuds par une fonction de coût f(n)=g(n)+h(n), où g(n) est le coût depuis le départ jusqu'au nœud n et h(n) est une estimation heuristique du coût de n à un but ; avec une heuristique admissible (et de préférence consistante), A* trouve des chemins de coût minimal de manière efficace.