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
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 26/12/2009 gemaakt, de laatste keer de 16/07/2024 gewijzigd
Bron van het afgedrukte document:https://www.gaudry.be/nl/graphes-bellman-kalaba-exemple.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.
Referenties
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.
