L'algorithme de recherche
A* (qui se prononce
A étoile, ou
A star à l'anglaise) est un algorithme de
recherche de chemin dans un
graphe entre un
nœud initial et un nœud final tous deux donnés. De par sa simplicité il est souvent présenté comme exemple typique d'algorithme de
planification, domaine de l'
intelligence artificielle. L'algorithme A* a été créé pour que la première solution trouvée soit l'une des meilleures, c'est pourquoi il est célèbre dans des applications comme les jeux vidéo privilégiant la vitesse de calcul sur l'exactitude des résultats. Cet algorithme a été proposé pour la première fois par , et en 1968. Il s'agit d'une extension de l'
algorithme de Dijkstra de 1959.