Algorithme A*

Contents

Fonctionnalités de l'algorithme A*

  • L'algorithme A* est un algorithme de recherche de chemin extrême.
  • A* est utilisé sur des graphes pondérés1
  • Nous pouvons utiliser l'algorithme A* (se prononce A Star) sur des graphes aux pondérations quelconques, et des graphes avec circuits ou sans circuits.
  • L'efficacité de A* repose sur la définition de bornes (par exemple des distances à vol d'oiseau).
  • L'algorithme A* est plus rapide que Ford-Bellman et Moore-Dijkstra, si le choix heuristique2 des bornes est judicieux (dans ce cas, la première solution trouvée est une des meilleures solutions possibles).

Contents Haut

Caractéristiques de l'algorithme A*

Nous parlons d'algorithme heuristique2 A* car l'égalité triangulaire entre les bornes n'est pas toujours vérifiée. Si certaines bornes ne respectent pas cette égalité triangulaire, A* donne un chemin qui n'est pas optimum.

Dans certains cas, l'algorithme A* peut toutefois se révéler plus lent à trouver le chemin, même si le choix heuristique est correct. Ces cas se présentent lorsque le chemin à emprunter doit d'abord "s'éloigner" de la destination, par exemple dans le cas d'un labyrinthe dans lequel le chemin qui part dans la direction de la destination est une "voie sans issue".

L'exemple du labyrinthe montre bien que le choix de l'algorithme en fonction de la situation est très important.

Contents Haut

Code de l'algorithme A*

Nous pouvons décomposer notre algorithme en deux phases : une phase d'initialisation des valeurs, et une phase d'exécution qui décrit ce qui se passe lorsque l'algorithme est exécuté.

Les explications suivantes sont identiques à celles que nous avons vu lors de l'algorithme de Moore-Dijkstra. La seule différence est que nous travaillons ici avec une fonction heuristique qui retourne la borne associée aux deux sommets évalués pour un arc.

Variables

Dans cette approche, nous utilisons des collections indexées (par exemple des tableaux) pour maintenir les différentes informations relatives aux états de chaque objet Sommet. Dans une approche "orienté-objet", nous pouvons maintenir ces informations par exemple dans l'objet Sommet lui même.

  • verticesLabels est le tableau qui contient les étiquettes. L'étiquette d'un sommet x est l'indice du sommet y précédent de x dans le chemin optimum de la racine vers le sommet x.
  • pathMinWeights est le tableau du coût (poids) des chemins depuis la racine jusqu'aux différents sommets.
    pathMinWeights[i] est le poids du chemin entre la racine et le sommet X[i].
  • definedVertices est le tableau qui contient les sommets traités (définis comme ∈ au chemin à renvoyer).

Nous utiliserons aussi certaines variables supplémentaires :

  • X est l'ensemble des sommets du graphe
  • n est le nombre de sommets du graphe (la cardinalité de X).

arrayFirstIndex : indice du premier élément dans un tableau3.

Phase d'initialisation

  • k := arrayFirstIndex // Le compteur pointe sur le premier élément d'un tableau.
  • j := indice_de_la_racine // indice (dans X) du sommet racine (départ du chemin).
  • Sommets traités :
    • definedVertices[k] := j //la racine fait d'office partie du chemin, car elle est le point de départ4. Nous pouvons donc stocker au premier emplacement de definedVertices l'indice (dans X) du sommet de départ.
    • ∀(i > k) : definedVertices[i] := arrayFirstIndex-1 // Initialisation du tableau avec une valeur hors des limites du tableau5.
  • Poids (r->x) :
    • pathMinWeights[definedVertices[k]] := 0 // Le chemin de la racine vers la racine a un poids égal à zéro.
    • ∀(i > k) pathMinWeights[i] := 2maxCost // Valeur hors des limites du possible (double de maxCost6).
  • Étiquettes :
    • verticesLabels[definedVertices[k]] := arrayFirstIndex // Étiquette de la racine. Pointe vers un emplacement non valide car la racine n'a pas de précédent.
    • ∀(i > k) verticesLabels[i] := arrayFirstIndex-1 // Initialisation du tableau avec une valeur hors des limites du tableau5.

Phase d'exécution

  1. //Il reste des sommets non traités
  2. tant_que k < n faire
  3.  
  4. 	/*i est l'indice de x, j est l'indice de y
  5. 	x est non traité, et le chemin(r,x) est le plus court
  6. 	de tous les chemins de r vers un sommet non traité */
  7. 	i := choisir x ∈ {y |&thinsp;(y ∈ X\definedVertices) ∧
  8. 		(pathMinWeights[i]=minimum{
  9. 			(pathMinWeights[j]+heuristic(i,j))∀j∈ X\definedVertices
  10. 			})};
  11.  
  12. 	//k pointe à présent sur le prochain emplacement libre de definedVertices
  13. 	k := k+1;
  14.  
  15. 	//i est défini comme étant traité
  16. 	definedVertices[k] := i;
  17.  
  18. 	//vérifier si ce chemin est le meilleur
  19. 	pour_tout y ∈ X\definedVertices faire
  20.  
  21. 		/*si x est un précédent de y sur un chemin
  22. 		plus court que le meilleur chemin actuel...*/
  23. 		si pathMinWeights[i]+weight(i,j) < pathMinWeights[j] alors
  24.  
  25. 			//le poids du chemin vers "y" est mis à jour
  26. 			pathMinWeights[j] := pathMinWeights[i]+weight(i,j);
  27.  
  28. 			//j est l'indice du sommet précédent de "x"
  29. 			verticesLabels[i] := j;
  30.  
  31. 		fin si
  32. 	fin pour_tout
  33. fin tant_que

A* vs Moore-Dijkstra

Le fait d'inclure notre fonction heuristique (ligne 9) dans le choix du sommet nous permet de prendre en compte une borne qui limitera les recherches en direction de la destination si les bornes sont judicieusement établies. L'amélioration est remarquable en pratique, bien que la complexité théorique reste identique.

English translation

You have asked to visit this site in English. For now, only the interface is translated, but not all the content yet.

If you want to help me in translations, your contribution is welcome. All you need to do is register on the site, and send me a message asking me to add you to the group of translators, which will give you the opportunity to translate the pages you want. A link at the bottom of each translated page indicates that you are the translator, and has a link to your profile.

Thank you in advance.

Document created the 02/01/2010, last modified the 26/10/2018
Source of the printed document:https://www.gaudry.be/en/graphes-heuristique-astar.html

The infobrol is a personal site whose content is my sole responsibility. The text is available under CreativeCommons license (BY-NC-SA). More info on the terms of use and the author.

Notes
  1. ↑ pondération : La pondération est une valeur associée à un arc (ou une arête), et correspond au coût du passage par cet arc. Par exemple, il peut s'agir d'une distance entre deux villes représentées chacune par un sommet du graphe.

  2. ↑a,b Heuristique : En optimisation combinatoire et en théorie des graphes, le terme "heuristique" est utilisé pour décrire le fait que cet algorithme soit approximatif, et pas nécessairement optimal.

  3. ↑ arrayFirstIndex : Ce n'est pas à proprement parler une variable, mais cela me permet d'éviter d'écrire 0 ou 1 dans le pseudo-code de l'algorithme selon le type de langage utilisé.
    Selon l'implémentation choisie, la collection utilisée peut démarrer son indexation à 0 (ex : tableau en Java) ou à 1 (ex : tableau en Pascal). Par exemple, en Java nous initialisons avec ∀i : previousVertices[i] = 0

  4. ↑ definedVertices[k] := indice_de_la_racine : Idem Moore-Dijkstra et Bellman-Kalaba.

  5. ↑a,b arrayFirstIndex-1 : Comme nous sélectionnons une valeur qui précède le premier indice du tableau, cela signifie que la valeur n'est pas encore significative.

  6. ↑ maxCost : La majorité des pseudo codes utilisent le symbole ∞ (infini) pour représenter une valeur hors des limites du possible, et dont les variations sont insignifiantes. JP Leclercq nous propose donc de travailler avec une valeur qui correspond à la somme des poids des arcs du graphe, car l'infini est une notion qui existe en mathématiques, mais qui ne correspond pas toujours à la réalité de la programmation. Nous utiliserons la notation maxCost, ou même 2maxCost dans les algorithmes pour lesquels cette valeur n'est pas suffisante.

Contents Haut

References

  1. book Language of the document:fr INFOB321 - Théorie des graphes : JP Leclercq, Cours de Théorie des Graphes et réseaux de Petri (September 2008)
  2. View the html document Language of the document:uk A* Pathfinding : Patrick Lester, A* Pathfinding for Beginners (version 30/12/09)
  3. View the html document Language of the document:fr Developpez.com : khayyam90, Recherche de chemin par l'algorithme A* (version 30/12/09)

These references and links indicate documents consulted during the writing of this page, or which may provide additional information, but the authors of these sources can not be held responsible for the content of this page.
The author This site is solely responsible for the way in which the various concepts, and the freedoms that are taken with the reference works, are presented here. Remember that you must cross multiple source information to reduce the risk of errors.

Contents Haut