Algorithme A*

Inhoudsopgave

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

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

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

Nederlandse vertaling

U hebt gevraagd om deze site in het Nederlands te bezoeken. Voor nu wordt alleen de interface vertaald, maar nog niet alle inhoud.

Als je me wilt helpen met vertalingen, is je bijdrage welkom. Het enige dat u hoeft te doen, is u op de site registreren en mij een bericht sturen waarin u wordt gevraagd om u toe te voegen aan de groep vertalers, zodat u de gewenste pagina's kunt vertalen. Een link onderaan elke vertaalde pagina geeft aan dat u de vertaler bent en heeft een link naar uw profiel.

Bij voorbaat dank.

Document heeft de 02/01/2010 gemaakt, de laatste keer de 26/10/2018 gewijzigd
Bron van het afgedrukte document:https://www.gaudry.be/nl/graphes-heuristique-astar.html

De infobrol is een persoonlijke site waarvan de inhoud uitsluitend mijn verantwoordelijkheid is. De tekst is beschikbaar onder CreativeCommons-licentie (BY-NC-SA). Meer info op de gebruiksvoorwaarden en de 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.

Inhoudsopgave Haut

Referenties

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

Deze verwijzingen en links verwijzen naar documenten die geraadpleegd zijn tijdens het schrijven van deze pagina, of die aanvullende informatie kunnen geven, maar de auteurs van deze bronnen kunnen niet verantwoordelijk worden gehouden voor de inhoud van deze pagina.
De auteur Deze site is als enige verantwoordelijk voor de manier waarop de verschillende concepten, en de vrijheden die met de referentiewerken worden genomen, hier worden gepresenteerd. Vergeet niet dat u meerdere broninformatie moet doorgeven om het risico op fouten te verkleinen.

Inhoudsopgave Haut