Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Algorithme A*
Résumé
En informatique, plus précisément en intelligence artificielle, l'algorithme de recherche A* (qui se prononce A étoile, ou A star en anglais) est un algorithme de recherche de chemin dans un graphe entre un nœud initial et un nœud final tous deux donnés. En raison de 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 Peter E. Hart, Nils John Nilsson et Bertram Raphael en 1968. Il s'agit d'une extension de l'algorithme de Dijkstra de 1959 (p. 30-31 dans ).
vignette|L'algorithme A* a été inventé par des chercheurs qui travaillaient sur la planification du robot Shakey.
En 1968, le chercheur en intelligence artificielle Nils Nilsson essayait d'améliorer la planification de Shakey le robot, un robot prototype qui se déplace dans une pièce avec des obstacles. L'algorithme pour trouver un chemin, que Nilsson appelait A1, était une version plus rapide que la méthode la plus connue à l'époque, l'algorithme de Dijkstra, pour trouver des plus courts chemins dans un graphe. Bertram Raphael a suggéré des améliorations, donnant lieu à la version révisée A2. Puis, Peter E. Hart a apporté des améliorations mineures à A2. Hart, Nilsson et Raphael ont alors montré que A2 est optimal pour trouver des plus courts chemins sous certaines conditions.
L'algorithme A* est un algorithme de recherche de chemin dans un graphe entre un nœud initial et un nœud final. Il utilise une évaluation heuristique sur chaque nœud pour estimer le meilleur chemin y passant, et visite ensuite les nœuds par ordre de cette évaluation heuristique. C'est un algorithme simple, ne nécessitant pas de prétraitement, et ne consommant que peu de mémoire.
Commençons par un exemple de motivation.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.