Algorithme de Moore-Dijkstra

Inhaltsverzeichnis

Fonctionnalités de l'algorithme de Moore-Dijkstra

  • Moore-Dijkstra est un algorithme de recherche de chemin extrême.
  • Moore-Dijkstra est utilisé sur des graphes pondérés1
  • Moore-Dijkstra s'applique aux graphes dont toutes les pondération sont positives ou nulles2. Il n'accepte pas les pondérations négatives2.
  • Moore-Dijkstra donne un résultat erroné pour la recherche de chemins extrémaux si le graphe ne possède pas de circuit.

Inhaltsverzeichnis Haut

Caractéristiques de l'algorithme de Moore-Dijkstra

Nous sommes à la recherche du chemin le plus court. Cela signifie que la somme des poids des arcs du chemin sélectionné doit être le plus faible possible.

L'algorithme de Moore-Dijkstra est une amélioration de l'algorithme de Floyd. Il est plus complexe que ce dernier, mais son exécution est beaucoup plus rapide.

Si nous sommes certains que notre graphe présente un ou plusieurs circuits, nous pouvons appliquer l'algorithme de Moore-Dijkstra qui nous permet une exploration progressive, sans back-tracking (retours en arrière)3.

Nous utiliserons un ensemble D (definedVertices) qui contiendra les sommets traités.
Au départ, definedVertices contient seulement le sommet racine4.

Principe de relâchement

Nous allons fixer une valeur tellement haute5 que tout au long de l'exécution de l'algorithme nous ne devrons jamais définir de nouvelles valeurs qui lui soient égales ou supérieures.

Le principe de relâchement nous permet d'utiliser cette borne supérieure sur le poids du plus court chemin, et de diminuer progressivement cette borne.

A chaque étape, nous devons choisir le sommet x à traiter parmi les sommets non encore traités, avec le chemin de poids le plus faible depuis le sommet précédent (x->y).
Il s'agit d'un choix glouton6, qui dans ce cas se révèle optimal.

Nous retirons ensuite x des sommets à traiter (en ajoutant son indice dans definedVertices).

Nous devons maintenant consulter les poids de x vers tout sommet non traité.
Pour tous les sommets non traités restants, nous comparons le poids du chemin (r->x->y) entre la racine r et ce sommet y en passant par x.

Si le poids du nouveau chemin est inférieur au poids précédent (dans pathMinWeights), il est retenu comme meilleur chemin, et la valeur de pathMinWeights est remplacée par ce meilleur chemin, et donc diminuée (relâchement).

Inhaltsverzeichnis Haut

Code de l'algorithme de Moore-Dijkstra

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

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

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 tableau8.
  • 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 maxCost5).
  • É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 tableau8.

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{pathMinWeights[j]∀j∈ X\definedVertices})};
  9.  
  10. 	//k pointe à présent sur le prochain emplacement libre de definedVertices
  11. 	k := k+1;
  12.  
  13. 	//i est défini comme étant traité
  14. 	definedVertices[k] := i;
  15.  
  16. 	//vérifier si ce chemin est le meilleur
  17. 	pour_tout y ∈ X\definedVertices faire
  18.  
  19. 		/*si x est un précédent de y sur un chemin
  20. 		plus court que le meilleur chemin actuel...*/
  21. 		si pathMinWeights[i]+weight(i,j) < pathMinWeights[j] alors
  22.  
  23. 			//le poids du chemin vers "y" est mis à jour
  24. 			pathMinWeights[j] := pathMinWeights[i]+weight(i,j);
  25.  
  26. 			//j est l'indice du sommet précédent de "x"
  27. 			verticesLabels[i] := j;
  28.  
  29. 		fin si
  30. 	fin pour_tout
  31. fin tant_que

Remarques

A la ligne 2, le test de comparaison k < n s'applique aux langages pour lesquels le premier indice d'un tableau est 0. Dans le cas où le premier indice est 1, nous devons remplacer le test par k ≤ n.

Nous pouvons éviter de calculer un certain nombre de fois l'opération pathMinWeigths[j]+weight(j,i) en utilisant une fonction memo qui effectuera seulement les calculs nécessaires.

  1. //vérifier si ce chemin est le meilleur
  2. pour_tout y ∈ X\definedVertices faire
  3.  
  4. 	tempWeight := memo(pathMinWeights[i]+weight(i,j));
  5.  
  6. 	/*si x est un précédent de y sur un chemin
  7. 	plus court que le meilleur chemin actuel...*/
  8. 	si tempWeight < pathMinWeights[j] alors
  9.  
  10. 		//le poids du chemin vers "y" est mis à jour
  11. 		pathMinWeights[j] := tempWeight;
  12.  
  13. 		//j est l'indice du sommet précédent de "x"
  14. 		verticesLabels[i] := j;
  15.  
  16. 	fin si
  17. fin pour_tout

Inhaltsverzeichnis Haut

Pourquoi utiliser l'algorithme de Moore-Dijkstra

Même si nous utilisons une stratégie gloutonne6, l'algorithme de Moore-Dijkstra nous retourne toujours le chemin optimum, pour autant que les hypothèses de départ sur notre graphe s'avérent exactes (notamment le fait que le graphe ne possède aucun arc de poids négatif). L'algorithme de Moore-Dijkstra est plus rapide que l'algorithme de Ford-Bellman.

Lorsque nous sommes en possession de bornes (sommet de départ, sommet d'arrivée, etc.), nous préférerons l'algorithme de l'heuristique A*, qui est plus rapide que l'algorithme de Moore-Dijkstra, car il limitera l'exploration aux sommets qui sont "dans la direction" de l'arivée au lieu d'évaluer les sommets "tout azimut".

Inhaltsverzeichnis Haut

Exemples d'application de l'algorithme de Moore-Dijkstra

Nous pouvons avoir, au lieu d'un graphe, un tableau à double entrée dans lequel chaque sommet est une colonne et une ligne. Chaque cellule contient donc le poids (la distance, le coût, etc.) entre deux sommets (villes).

Ce type de représentation (par exemple les distances entre différentes villes) est totalement identique à un graphe dont les arêtes (trajet entre deux villes) sont pondérées (distance entre deux villes).

Le protocole de routage IP OSPF (Open Shortest Path First) utilise l'algorithme de Dijkstra pour déterminer la route la plus courte vers les différents réseaux.

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 27/12/2009, zuletzt geändert 26/10/2018
Quelle des gedruckten Dokuments:https://www.gaudry.be/de/graphes-moore-dijkstra.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 Moore-Dijkstra & poids négatifs : L'algorithme de Moore-Dijkstra ne permet pas la présence de pondération négative dans notre exemple car nous sommes à la recherche de chemin extrême minimum. Dans le cas de la recherche d'un chemin extrême maximum avec l'algorithme de Moore-Dijkstra le graphe ne peut contenir aucun arc de pondération positive, et nous devons légèrement modifier le pseudo code.

  3. ↑ retour en arrière : Les résultats stockés dans l'ensemble D sont acquis au fur et à mesure, et ne sont plus mis en doute par la suite.

  4. ↑a,b definedVertices[k] := indice_de_la_racine : Dans certains exemples de pseudo code de l'algorithme de Moore-Dijkstra, nous trouvons une initialisation D := ∅ (un ensemble vide pour les sommets déjà traités), contrairement à l'algorithme de Bellman-Kalaba pour lequel D contient seulement le sommet racine.

    Cela impose des contraintes superflues lors de l\implémentation, car il faut alors choisir la racine pour y uniquement lors du premier passage dans la boucle.
    Par rapport à notre pseudo code de l'algorithme de Bellman-Kalaba, l'incrémentation de k se fait alors après avoir marqué le sommet comme "traité", car definedVertices est dans ce cas initialement vide.

    Nous utiliserons donc le même type d'initialisation que pour Bellman-Kalaba pour éviter ces désagréments.

  5. ↑a,b 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.

  6. ↑a,b Choix glouton : L'algorithme de Moore-Dijkstra choisit le plus faible poids sur le moment, en espérant que la succession de choix de meilleure solution à court terme mène à la meilleure solution finale.

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

  8. ↑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.

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:fr Implémentation : Sébastien BOUCLET , Implémentation de l'algorithme de Moore Dijkstra (version 28/12/09)
  3. Zeigen Sie - html-Dokument Sprache des Dokuments:uk Graph Theory Applet : Rensselaer Polytechnic Institute, Démonstration interactive par applet Java (version 28/12/09)
  4. Zeigen Sie - html-Dokument Sprache des Dokuments:fr Applet : Cara Laffra, L'algorithme de Dijkstra (version 28/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