Algorithme A*

Inhaltsverzeichnis

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

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

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

Deutsche Übersetzung

Sie haben gebeten, diese Seite auf Deutsch zu besuchen. Momentan ist nur die Oberfläche übersetzt, aber noch nicht der gesamte Inhalt.

Wenn Sie mir bei Übersetzungen helfen wollen, ist Ihr Beitrag willkommen. Alles, was Sie tun müssen, ist, sich auf der Website zu registrieren und mir eine Nachricht zu schicken, in der Sie gebeten werden, Sie der Gruppe der Übersetzer hinzuzufügen, die Ihnen die Möglichkeit gibt, die gewünschten Seiten zu übersetzen. Ein Link am Ende jeder übersetzten Seite zeigt an, dass Sie der Übersetzer sind und einen Link zu Ihrem Profil haben.

Vielen Dank im Voraus.

Dokument erstellt 02/01/2010, zuletzt geändert 26/10/2018
Quelle des gedruckten Dokuments:https://www.gaudry.be/de/graphes-heuristique-astar.html

Die Infobro ist eine persönliche Seite, deren Inhalt in meiner alleinigen Verantwortung liegt. Der Text ist unter der CreativeCommons-Lizenz (BY-NC-SA) verfügbar. Weitere Informationen auf die Nutzungsbedingungen und dem Autor.

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

Inhaltsverzeichnis Haut

Referenzen

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

Diese Verweise und Links verweisen auf Dokumente, die während des Schreibens dieser Seite konsultiert wurden, oder die zusätzliche Informationen liefern können, aber die Autoren dieser Quellen können nicht für den Inhalt dieser Seite verantwortlich gemacht werden.
Der Autor Diese Website ist allein dafür verantwortlich, wie die verschiedenen Konzepte und Freiheiten, die mit den Nachschlagewerken gemacht werden, hier dargestellt werden. Denken Sie daran, dass Sie mehrere Quellinformationen austauschen müssen, um das Risiko von Fehlern zu reduzieren.

Inhaltsverzeichnis Haut