Algorithme A*
Un article de Wikipédia, l'encyclopédie libre.
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 exhibé comme un exemple typique d'algorithme de planification, un 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 le temps de calcul à l'exactitude des résultats.
Sommaire |
[] Présentation
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.
[] 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 sur lequel l'algorithme va travailler représente la carte, où ses arcs représentent les chemins et ses 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*.
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.
[] 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 de la ligne directe au but sur la carte.
On peut démontrer que 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 l'heuristique assignée au chemin menant à ce n?ud. Le n?ud est alors ajouté à une file d'attente prioritaire, couramment appelée open list.
L'algorithme retire le premier n?ud de la file d'attente prioritaires (dû au 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 sauvées dans la liste communément appelé 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.
[] Liens externes
- (en) Une implementation et visualisation de l'algorithme A* - Implémentation en PHP et visualisation utilisant Google Map API, par Tarik ATTAR
- (en) Un article sur gamedev.net pour comprendre le fonctionnement de l'algorithme A*
- (en) Un article décrivant l'algorithme HPA* qui permet d'optimiser la recherche dans les graphes de grande taille
- (fr) Recherche de chemin par l'algorithme A*, par Pierre Schwartz
- (fr) Exemple d'un programme simple de recherche de plus court chemin par l'algorithme A*
Le Texte ci-dessus est disponible sous GNU Free Documentation License.
La source est wikipedia http://fr.wikipedia.org/wiki/Algorithme A*
