Voir la source de Algorithme A*

{{Voir homonymes|A*}}
{{Infobox Algorithme}}
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 [[Théorie des graphes|graphe]] entre un [[Sommet (théorie des graphes)|nœud]] initial et un nœud final tous deux donnés<ref>{{lien web|langue=en|url=http://www.cs.ualberta.ca/~mmueller/ps/hpastar.pdf|titre=Near Optimal Hierarchical Path-Finding}}</ref>. En raison de sa simplicité il est souvent présenté comme exemple typique d'algorithme de [[planification (intelligence artificielle)|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<ref>{{article|langue=en
 | prénom = P. E.
 | nom1 = Hart
 | prénom2 = N. J.
 | nom2 = Nilsson
 | prénom3 = B.
 | nom3 = Raphael
 | titre = A Formal Basis for the Heuristic Determination of Minimum Cost Paths
 | journal = [[Institute of Electrical and Electronics Engineers|IEEE]] Transactions on Systems Science and Cybernetics SSC4
 | numéro = 2
 | pages = 100–107
 | année = 1968
 | doi = 10.1109/TSSC.1968.300136
 | volume = 4
 }}
</ref>. Il s'agit d'une extension de l'[[algorithme de Dijkstra]] de 1959 (p. 30-31 dans<ref>{{Ouvrage|prénom1=Steven M.|nom1=LaValle|titre=Planning Algorithms|date=2004|lire en ligne=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.1.7086|consulté le=2019-10-14}}</ref>).

== Histoire ==
[[Fichier:SRI Shakey with callouts.jpg|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 John Nilsson|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é qu'A2 est ''optimal'' pour trouver des plus courts chemins sous certaines conditions.

== Présentation ==
L'algorithme A* est un [[algorithme de recherche]] de chemin dans un [[graphe (théorie des graphes)|graphe]] entre un [[Nœud (mathématiques)|nœud]] initial et un nœud final. Il utilise une évaluation [[heuristique (mathématiques)|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.

== Intuition ==
Commençons par un exemple de motivation. On se trouve à l'intersection A et on veut se rendre à l'intersection B dont on sait qu'elle se trouve au nord de notre position actuelle. Pour ce cas classique, le [[graphe (théorie des graphes)|graphe]] sur lequel l'algorithme va travailler représente la carte, où ses arcs représentent les chemins et ses [[Nœud (mathématiques)|nœuds]] les intersections des chemins.

Si on faisait une recherche en largeur comme le réalise l'[[algorithme de Dijkstra]], on rechercherait tous les points dans un rayon circulaire fixe, augmentant graduellement ce cercle pour rechercher des intersections de plus en plus loin de notre point de départ. Ceci pourrait être une stratégie efficace si on ne savait pas où se trouve notre destination, comme la police recherchant un criminel en planque.

Cependant, c'est une perte de temps si on connaît plus d'informations sur notre destination. Une meilleure stratégie est d'explorer à chaque intersection la première directement qui va vers le nord, car le chemin le plus court est la ligne droite. Tant que la route le permet, on continue à avancer en prenant les chemins se rapprochant le plus de l'intersection B. Certainement devra-t-on revenir en arrière de temps en temps, mais sur les cartes typiques c'est une stratégie beaucoup plus rapide. D'ailleurs, souvent cette stratégie trouvera le meilleur [[itinéraire]], comme la recherche en largeur le ferait. C'est l'essence de la recherche de chemin A*.

[[Image:Schema Astar labyrinthe.png|vignette|260px|Un labyrinthe simple, où l'algorithme A* ne sera pas très efficace]]
Toutefois, comme pour tous les algorithmes de recherche de chemin, leur efficacité dépend fortement du problème que l'on souhaite résoudre (c'est-à-dire : du graphe). Ainsi l'algorithme A* ne garantit pas de trouver un itinéraire plus rapidement qu'un autre algorithme, et dans un [[labyrinthe]], la seule manière d'atteindre la destination pourrait être à l'opposé de la position de la destination, et les nœuds les plus proches de cette destination pourraient ne pas être sur le chemin le plus court, ce qui peut coûter beaucoup de temps de calcul.
{{Clr}}

== Propriété ==
Un algorithme de recherche qui garantit de toujours trouver le chemin le plus court à un but s'appelle « algorithme admissible ». Si A* utilise une heuristique qui ne surestime jamais la distance (ou plus généralement le coût) du but, A* peut être avéré admissible. Une heuristique qui rend A* admissible est elle-même appelée « heuristique admissible ».

Si l'évaluation renvoie simplement toujours zéro, qui n'est jamais une surestimation, alors, A* exécutera une implémentation possible de l'algorithme de Dijkstra et trouvera toujours la solution optimale. La meilleure heuristique, bien qu'habituellement impraticable pour calculer, est la distance minimale réelle (ou plus généralement le coût réel) au but. Un exemple d'une heuristique admissible pratique est la distance à vol d'oiseau du but sur la carte.

On peut démontrer qu'A* ne considère pas plus de nœuds que tous les autres algorithmes admissibles de recherche, à condition que l'algorithme alternatif n'ait pas une évaluation heuristique plus précise. Dans ce cas, A* est l'algorithme informatique le plus efficace garantissant de trouver le chemin le plus court.

== Description ==

A* commence à un nœud choisi. Il applique à ce nœud un « coût » (habituellement zéro pour le nœud initial). A* estime ensuite la distance qui sépare ce nœud du but à atteindre. La somme du coût et de l'évaluation représente le coût [[Heuristique (mathématiques)|heuristique]] assigné au chemin menant à ce nœud. Le nœud est alors ajouté à une [[File de priorité|file d'attente prioritaire]], couramment appelée ''open list''.

L'algorithme retire le premier nœud de la file d'attente prioritaire (en raison du fonctionnement d'une file d'attente, le nœud à l'heuristique la plus basse est retiré en premier). Si la file d'attente est vide, il n'y a aucun chemin du nœud initial au nœud d'arrivée, ce qui interrompt l'algorithme. Si le nœud retenu est le nœud d'arrivée, A* reconstruit le chemin complet et s'arrête. Pour cette reconstruction on se sert d'une partie des informations sauvegardées dans la liste communément appelée ''closed list'' décrite plus bas.

Si le nœud n'est pas le nœud d'arrivée, de nouveaux nœuds sont créés pour tous les nœuds contigus admissibles ; la manière exacte de faire dépend du problème à traiter. Pour chaque nœud successif, A* calcule son coût et le stocke avec le nœud. Ce coût est calculé à partir de la somme du coût de son ancêtre et du coût de l'opération pour atteindre ce nouveau nœud.

L'algorithme maintient également la liste de nœuds qui ont été vérifiés, couramment appelée ''closed list''. Si un nœud nouvellement produit est déjà dans cette liste avec un coût égal ou inférieur, aucune opération n'est faite sur ce nœud ni sur son homologue se trouvant dans la liste.

Après, l'évaluation de la distance du nouveau nœud au nœud d'arrivée est ajoutée au coût pour former l'heuristique du nœud. Ce nœud est alors ajouté à la liste d'attente prioritaire, à moins qu'un nœud identique dans cette liste ne possède déjà une heuristique inférieure ou égale.

Une fois les trois étapes ci-dessus réalisées pour chaque nouveau nœud contigu, le nœud original pris de la file d'attente prioritaire est ajouté à la liste des nœuds vérifiés. Le prochain nœud est alors retiré de la file d'attente prioritaire et le processus recommence.

Les deux structures ''open list'' et ''closed list'' ne sont pas nécessaires si on peut garantir que le premier chemin produit à n'importe quel nœud est le plus court. Cette situation surgit si l'heuristique est non seulement admissible mais aussi « monotone », signifiant que la différence entre l'heuristique de deux nœuds quelconques reliés ne surestime pas la distance réelle entre ces nœuds. Ce n'est possible que dans de très rares cas.

== Pseudo-code ==
Voici une implémentation possible de l'algorithme, en pseudo-code, pour une recherche de chemin dans une carte qui est un tableau à deux dimensions tel que chaque case contient un état: traversable ou non.

    '''Structure''' nœud = {
       x, y: Nombre
       cout, heuristique: Nombre
    }

    depart = Nœud(x=_, y=_, cout=0, heuristique=0)

    '''Fonction''' compareParHeuristique(n1:Nœud, n2:Nœud)
        '''si''' n1.heuristique < n2.heuristique 
            retourner 1
        '''ou si''' n1.heuristique == n2.heuristique 
            retourner 0
        '''sinon'''
            retourner -1

    '''Fonction''' cheminPlusCourt(g:Graphe, objectif:Nœud, depart:Nœud)
        closedList = File()
        openList = FilePrioritaire(comparateur = compareParHeuristique)
        openList.ajouter(depart)
        '''tant que''' openList n'est pas vide
            u = openList.defiler()
            '''si''' u.x == objectif.x '''et''' u.y == objectif.y
                reconstituerChemin(u)
                terminer le programme
            '''pour chaque''' voisin v de u dans g
                '''si''' non(   v existe dans closedList
                             ou v existe dans openList avec un coût inférieur)
                     v.cout = u.cout +1 
                     v.heuristique = v.cout + distance([v.x, v.y], [objectif.x, objectif.y])
                     openList.ajouter(v)
            closedList.ajouter(u)
        terminer le programme (avec erreur)

== Variantes ==
[[File:Weighted_A_star_with_eps_5.gif|alt=|vignette|WA* avec un poids w = 5. On obtient un chemin sous-optimal.]]
WA* (weighted A*) est l'algorithme A* dans lequel l'heuristique h est multipliée par un poids w. L'algorithme est alors généralement plus rapide mais au prix de la garantie. Le poids du chemin trouvé est cependant au plus w multiplié par le poids minimal<ref name="pearl84">{{Ouvrage|langue=en|prénom1=Judea|nom1=Pearl|titre=Heuristics|sous-titre=Intelligent Search Strategies for Computer Problem Solving|éditeur=Addison-Wesley|année=1984|pages totales=382|isbn=978-0-201-05594-8|isbn10=0-201-05594-5}}</ref>. Il existe d'autres variantes :

* Dynamic Weighting<ref>{{lien conférence|prénom=Ira|nom=Pohl|titre=The avoidance of (relative) catastrophe, heuristic competence, genuine dynamic weighting and computational issues in heuristic problem solving|titre livre=Proceedings of the Third International Joint Conference on Artificial Intelligence (IJCAI-73)|volume=3|pages=11–17|lieu=California, USA|date=août 1973|url=https://www.cs.auckland.ac.nz/courses/compsci709s2c/resources/Mike.d/Pohl1973WeightedAStar.pdf}}</ref>
* Sampled Dynamic Weighting<ref>{{lien conférence|prénom=Andreas|nom=Köll|auteur2=Hermann Kaindl|titre=A new approach to dynamic weighting|titre livre=Proceedings of the Tenth European Conference on Artificial Intelligence (ECAI-92)|pages=16–17|lieu=Vienna, Austria|date=août 1992}}</ref>
* <math>A^*_\varepsilon</math><ref>{{article|prénom=Judea|nom=Pearl|auteur2=Jin H. Kim|titre=Studies in semi-admissible heuristics|journal=IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI)|volume=4|numéro=4|pages=392–399|année=1982}}</ref>
* AlphA*<ref>{{lien web | langue=en | prénom=Bjørn|nom=Reese|titre=AlphA*: An ''ε''-admissible heuristic search algorithm| année=1999| url=http://home1.stofanet.dk/breese/astaralpha-submitted.pdf.gz |archive-url=https://web.archive.org/web/20160131214618/http://home1.stofanet.dk/breese/astaralpha-submitted.pdf.gz | éditeur=Systematic Software Engineering A/S}}</ref>

== Notes et références ==
{{Références}}

== Annexes ==
{{autres projets|wikibooks=Implémentation d'algorithmes classiques/Algorithmes de pathfinding/A*|wikibooks titre=implémentation de l'algorithme A*}}

=== Articles connexes ===
* {{Lien|langue=en|fr=Any-angle path planning}} ;
* [[Jump point search]], une optimisation d'A* pour les grilles à coût uniforme, réduisant son temps d'exécution d'un ordre de magnitude ;
* {{Lien|langue=en|fr=Rapidly-exploring random tree}}.

{{Palette|Algorithmes sur les graphes}}
{{Portail|informatique théorique}}

[[Catégorie:Algorithme de la théorie des graphes|A*]]
[[Catégorie:Algorithme de recherche]]
[[Catégorie:Intelligence artificielle]]