Algorithme A*

Pour les articles homonymes, voir A*.

Algorithme A*

Découvreurs ou inventeurs	Peter E. Hart, Nils John Nilsson, Bertram Raphael
Date de publication	1968
Problèmes liés	Algorithme de recherche de chemin (d), algorithme de la théorie des graphes (en), complete search algorithm (d)[1], admissible search algorithm (d)[2]
Structure des données	Graphe
Basé sur	Algorithme de Dijkstra
À l'origine de	Jump point search

Complexité en temps

Pire cas	${\displaystyle O(|E|)=O(b^{d})}$[3]

Complexité en espace

Pire cas	${\displaystyle O(|V|)=O(b^{d})}$[3]

modifier - modifier le code - modifier Wikidata

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^[4]. 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^[5]. Il s'agit d'une extension de l'algorithme de Dijkstra de 1959 (p. 30-31 dans^[6]).