Algorithme A*
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

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 (La planification est la programmation d'actions et d'opérations à mener), un domaine de l'intelligence artificielle (L'intelligence artificielle ou informatique cognitive est la « recherche de moyens susceptibles de doter les systèmes informatiques de capacités intellectuelles comparables à celles des êtres...). 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 (La vidéo regroupe l'ensemble des techniques, technologie, permettant l'enregistrement ainsi que la restitution d'images animées, accompagnées ou non de son, sur un support adapté à l'électronique...) privilégiant le temps (Le temps est un concept développé par l'être humain pour appréhender le changement dans le monde.) de calcul à l'exactitude des résultats.

Présentation

L'algorithme A* est un algorithme de recherche (En informatique, un algorithme de recherche est un type d'algorithme qui, pour un domaine, un problème de ce domaine et des critères donnés, retourne...) de chemin dans un graphe (Le mot graphe possède plusieurs significations. Il est notamment employé :) entre un nœud initial et un nœud final. Il utilise une évaluation heuristique (L'heuristique (du grec heuriskêin, « trouver ») est l'utilisation de règles empiriques :) 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 (D'une manière générale, la mémoire est le stockage de l'information. C'est aussi le souvenir d'une information.).

Intuition

Commençons par un exemple de motivation (La motivation est, dans un organisme vivant, la composante ou le processus qui règle son engagement dans une action ou expérience. Elle en détermine le déclenchement dans une certaine direction avec l'intensité...). On se trouve à l'intersection A et on veut se rendre à l'intersection B dont on sait qu'elle se trouve au nord (Le nord est un point cardinal, opposé au sud.) 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 (La recherche scientifique désigne en premier lieu l’ensemble des actions entreprises en vue de produire et de développer les connaissances scientifiques. Par extension métonymique, la...) en largeur (La largeur d’un objet représente sa dimension perpendiculaire à sa longueur, soit la mesure la plus étroite de sa face. En géométrie...) comme le réalise l'algorithme de Dijkstra (L'algorithme de Dijkstra sert à résoudre le problème du plus court chemin entre deux sommets d'un graphe connexe dont le poids lié aux arêtes est positif ou nul.), on rechercherait tous les points dans un rayon circulaire fixe, augmentant graduellement ce cercle (Un cercle est une courbe plane fermée constituée des points situés à égale distance d'un point nommé centre. La valeur de cette distance est appelée rayon du...) pour rechercher des intersections de plus en plus loin de notre point (Graphie) de départ. Ceci pourrait être une stratégie (La stratégie - du grec stratos qui signifie « armée » et ageîn qui signifie « conduire » - est :) 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 mot « route » dérive du latin (via) rupta, littéralement « voie brisée », c'est-à-dire creusée dans la roche, pour ouvrir le chemin.) 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*.

Un labyrinthe simple, où l'algorithme A* ne sera pas très efficace
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é ( En mathématique, l'opposé d’un nombre est le nombre tel que, lorsqu’il est à ajouté à n donne zéro. En botanique, les organes d'une plante sont dits opposés lorsqu'ils...) de la position de la destination, et les nœuds les plus proches de cette destination pouraient 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 (Le chiffre zéro (de l’italien zero, dérivé de l’arabe sifr, d’abord transcrit zefiro en italien) est un symbole marquant une position vide dans l’écriture des...), qui n'est jamais une surestimation, alors, A* exécutera une implémentation (Le mot implantation peut avoir plusieurs significations :) 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 (L´informatique - contraction d´information et automatique - est le domaine d'activité scientifique, technique et industriel en rapport avec le traitement...) 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 prioritaire (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 (Le vide est ordinairement défini comme l'absence de matière dans une zone spatiale.), 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 cela 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 (En géographie, la situation est un concept spatial permettant la localisation relative d'un espace par rapport à son environnement proche ou non. Il inscrit un lieu dans un cadre plus...) 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.

Pseudocode

Exemple d'un traitement mettant en évidence les coûts g et h
Exemple d'un traitement mettant en évidence les coûts g et h

Paramètres :

START : nœud de départ
GOAL : nœud d'arrivée
OPEN : liste des nœuds à traiter (en général : représenté comme une file de priorité)
CLOSED : liste des nœuds traités
N : nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) de nœuds
h(i) : distance estimée d'un nœud i au nœud d'arrivée (i ∈ {1, 2, ..., N})
g(i) : distance réelle d'un nœud i au nœud de départ (i ∈ {1, 2, ..., N})
f(i) : somme des distances h(i) et g(i)
parent() : parent d'un nœud i (parent(x) donne la position dans parent() du nœud précédant x))
  • Initialiser la liste OPEN à vide
  • Initialiser la liste CLOSED à vide
  • Ajouter START à la liste OPEN
  • Tant que la liste OPEN n'est pas vide
  • Retirer le nœud n de la liste OPEN tel que f(n) soit le plus petit
  • Si n est le GOAL retourner la solution ;
  • Sinon ajouter n a CLOSED
  • Pour chaque successeur du nœud n
  • Heuristique H = estimation du coût de au GOAL
  • Stocker dans G_tmp g(n´), le coût g(n) + le coût pour aller de n à
  • Stocker dans F_tmp f(n´), g(n´) + H ; c'est l'heuristique
  • Si se trouve déjà dans OPEN avec un f(n´) meilleur on passe au point suivant
  • Si se trouve déjà dans CLOSED avec un f(n´) meilleur on passe au point suivant
  • Mettre n dans parent(n')
  • Mettre G_tmp dans g(n')
  • Mettre F_tmp dans f(n´)
  • Retirer des deux listes OPEN et CLOSED
  • Ajouter à la liste OPEN

Exemples

Page générée en 0.168 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique