Exemple d'algorithme de Bellman-Kalaba
Légende & situation
Le tableau de départ contient les sommets suivants :
- "Sommet 2" à l'indice 0.
- "Sommet 4" à l'indice 1.
- "Sommet 6" à l'indice 2.
- "Sommet 5" à l'indice 3.
- "Sommet 1" à l'indice 4.
- "Sommet 3" à l'indice 5.
[Étape 0-0] Initialisation des valeurs
Les variables utilisées ici les mêmes que lors des explications sur l'algorithme Bellman-Kalaba, sauf pour le tableau definedVertices qui est réduit dans les images à la lettre D :
- k := arrayFirstIndex // Le compteur pointe sur le premier élément d'un tableau.
- definedVertices[k] := indice_de_la_racine //la racine fait d'office partie du chemin, car elle est le point de départ. Nous pouvons donc stocker au premier emplacement de definedVertices l'indice (dans X) du sommet.
- pathMinWeights[definedVertices[k]] := 0 // Le chemin de la racine vers la racine a un poids égal à zéro.
- verticesLabels[definedVertices[k]] := arrayFirstIndex]-1 // Étiquette de la racine. Pointe vers un emplacement non valide car la racine n'a pas de précédent.
Recherche du 1e sommet pour le chemin optimum
[Étape 1-0] Rejet du sommet 3
Les sommets candidats au chemin optimum sont {2,3}. Nous ne pouvons sélectionner le sommet 3 car le sommet 2 précédent de 3 n'est pas présent dans definedVertices, ce qui signifie qu'il existe un chemin non traité qui passe par le sommet 2.
i := choisir x ∈ {3 | (3 ∈ X\definedVertices) ∧ (Γ-1(3) ⊂ definedVertices ≠ ∅)};
[Étape 1-1] Sélection du sommet 2
definedVertices[k] := i; devient definedVertices[0] := 0; et X[0] = sommet 2.
Le sommet 2 est sélectionné pour le chemin optimum.
Recherche du 2e sommet pour le chemin optimum
[Étape 2-0] Rejet du sommet 4
Les sommets candidats au chemin optimum sont {4,3}. Nous ne pouvons sélectionner le sommet 4 car le sommet 3 précédent de 4 n'est pas présent dans definedVertices, ce qui signifie qu'il existe un chemin non traité qui passe par le sommet 3.
i := choisir x ∈ {4 | (4 ∈ X\definedVertices) ∧ (Γ-1(4) ⊂ definedVertices ≠ ∅)};
[Étape 2-1] Sélection du sommet 3
definedVertices[k] := i; devient definedVertices[0] := 5; et X[5] = sommet 3.
Le sommet 3 est sélectionné pour le chemin optimum.
Recherche du 3e sommet pour le chemin optimum
[Étape 3-0] Rejet du sommet 6
Les sommets candidats au chemin optimum sont {4,5,6}. Nous ne pouvons sélectionner le sommet 6 car le sommet 5 précédent de 6 n'est pas présent dans definedVertices, ce qui signifie qu'il existe un chemin non traité qui passe par le sommet 5.
i := choisir x ∈ {6 | (6 ∈ X\definedVertices) ∧ (Γ-1(6) ⊂ definedVertices ≠ ∅)};
[Étape 3-1] Recherche du minimum entre {4 (avec un poids de 6),5 (avec un poids de 9)}
Les sommets candidats au chemin optimum sont {4 (avec un poids de 6),5 (avec un poids de 9)} Nous devons sélectionner le sommet 4 car il possède le poids le moins élevé (6) parmi les candidats.
pathMinWeights[i] := minimum{ pathMinWeigths[j]+weight(j,i)∀j∈&Gamma-1(x)};
[Étape 3-2] Sélection du sommet 4
definedVertices[k] := i; devient definedVertices[0] := 1; et X[1] = sommet 4.
Le sommet 4 est sélectionné pour le chemin optimum.
Recherche du 4e sommet pour le chemin optimum
[Étape 4-0] Rejet du sommet 6
Les sommets candidats au chemin optimum sont {5,6}. Nous ne pouvons sélectionner le sommet 6 car le sommet 5 précédent de 6 n'est pas présent dans definedVertices, ce qui signifie qu'il existe un chemin non traité qui passe par le sommet 5.
i := choisir x ∈ {6 | (6 ∈ X\definedVertices) ∧ (Γ-1(6) ⊂ definedVertices ≠ ∅)};
[Étape 4-1] Sélection du sommet 5
definedVertices[k] := i; devient definedVertices[0] := 3; et X[3] = sommet 5.
Le sommet 5 est sélectionné pour le chemin optimum.
Dernier sommet pour le chemin optimum (arrivée)
[Étape 5-0] Sélection du sommet 6
definedVertices[k] := i; devient definedVertices[0] := 2; et X[2] = sommet 6.
Le sommet 6 est sélectionné pour le chemin optimum.
Chemin optimum trouvé par l'algorithme de Bellman-Kalaba
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 26/12/2009, zuletzt geändert 16/07/2024
Quelle des gedruckten Dokuments:https://www.gaudry.be/de/graphes-bellman-kalaba-exemple.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.
Referenzen
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.
