Exemple d'algorithme de Bellman-Kalaba

Sommaire du document

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.
Bellman-Kalaba, légende

[Étape 0-0]  Initialisation des valeurs

Bellman-Kalaba, image 0-0

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

Bellman-Kalaba, image 1-0

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

Bellman-Kalaba, image 1-1

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

Bellman-Kalaba, image 2-0

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

Bellman-Kalaba, image 2-1

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

Bellman-Kalaba, image 3-0

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

Bellman-Kalaba, image 3-1

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

Bellman-Kalaba, image 3-2

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

Bellman-Kalaba, image 4-0

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

Bellman-Kalaba, image 4-1

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

Bellman-Kalaba, image 5-0

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

Graphes : Bellman-Kalaba chemin optimum

 

Réseaux sociaux

Vous pouvez modifier vos préférences dans votre profil pour ne plus afficher les interactions avec les réseaux sociaux sur ces pages.

 

Nuage de mots clés

8 mots clés dont 5 définis manuellement (plus d'information...).

Vous pouvez modifier vos préférences dans votre profil pour ne plus afficher le nuage de mots clés.

 

Références

  1. Consulter le document html Langue du document: fr Bellman-Kalaba : lien interne, L'algorithme de Bellman-Kalaba en détails

Ces références et liens indiquent des documents consultés lors de la rédaction de cette page, ou qui peuvent apporter un complément d'information, mais les auteurs de ces sources ne peuvent être tenus responsables du contenu de cette page.
L'auteur de ce site est seul responsable de la manière dont sont présentés ici les différents concepts, et des libertés qui sont prises avec les ouvrages de référence. N'oubliez pas que vous devez croiser les informations de sources multiples afin de diminuer les risques d'erreurs.

 

Astuce pour imprimer les couleurs des cellules de tableaux : http://www.gaudry.be/ast-rf-450.html
Aucun commentaire pour cette page

© Ce document issu de l′infobrol est enregistré sous le certificat Cyber PrInterDeposit Digital Numbertection. Enregistrement IDDN n° 5329-10856
Document créé le 26/12/09 10:45, dernière modification le Mardi 04 Juillet 2017, 16:04
Source du document imprimé : http:///www.gaudry.be/graphes-bellman-kalaba-exemple.html
St.Gaudry©07.01.02
Outils (masquer)
||
Recherche (afficher)
Recherche :

Utilisateur (masquer)
Apparence (afficher)
Stats (afficher)
15838 documents
455 astuces.
550 niouzes.
3107 definitions.
447 membres.
8121 messages.

Document genere en :
0,09 seconde

Mises à jour :
Mises à jour du site
Citation (masquer)
Les hommes n'ont plus le temps de rien connaître. Ils achètent des choses toutes faites chez les marchands. Mais comme il n'existe point de marchands d'amis, les hommes n'ont plus d'amis.

Antoine de Saint-Exupéry [Extrait de Le petit prince]
 
l'infobrol
Nous sommes le Lundi 24 Juillet 2017, 22:52, toutes les heures sont au format GMT+1.00 Heure, heure d'été (+1)