Algorithme A*

Table des matières

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).

Table des matières 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.

Table des matières 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.

Version en cache

21/11/2024 03:24:33 Cette version de la page est en cache (à la date du 21/11/2024 03:24:33) afin d'accélérer le traitement. Vous pouvez activer le mode utilisateur dans le menu en haut pour afficher la dernère version de la page.

Document créé le 02/01/2010, dernière modification le 26/10/2018
Source du document imprimé : https://www.gaudry.be/graphes-heuristique-astar.html

L'infobrol est un site personnel dont le contenu n'engage que moi. Le texte est mis à disposition sous licence CreativeCommons(BY-NC-SA). Plus d'info sur les conditions d'utilisation et sur l'auteur.

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.

Table des matières Haut

Références

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

Ces références et liens indiquent des documents consultés lors de la rédaction de cette page, ou qui peuvent apporter un complément d'information, mais les auteurs de ces sources ne peuvent être tenus responsables du contenu de cette page.
L'auteur de ce site est seul responsable de la manière dont sont présentés ici les différents concepts, et des libertés qui sont prises avec les ouvrages de référence. N'oubliez pas que vous devez croiser les informations de sources multiples afin de diminuer les risques d'erreurs.

Table des matières Haut