Algorithme de Bellman-Kalaba

Sommaire du document

Fonctionnalités de l'algorithme de Bellman-Kalaba

  • Bellman-Kalaba est un algorithme de recherche de chemin extrême.
  • Bellman-Kalaba est utilisé sur des graphes pondérés[1]
  • Bellman-Kalaba accepte le mélange de pondérations positives et négatives[2].
  • Bellman-Kalaba ne donne pas de résultat pour la recherche de chemins extrémaux si le graphe possède un ou plusieurs circuits[3].

 

Caractéristiques de l'algorithme de Bellman-Kalaba

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.

Si nous sommes certains que notre graphe ne présente pas de circuit, nous pouvons appliquer l'algorithme de Bellman-Kalaba qui nous permet une exploration progressive, sans back-tracking (retours en arrière)[4].

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

A chaque étape, si le degré extérieur du sommet en cours est > 1 (donc si plusieurs arcs partent du sommet en cours) nous éliminerons les arcs dont certains sommet précédents ne sont pas présents dans l'ensemble D.
Ensuite, nous comparerons les poids des arcs restants afin de sélectionner le poids le plus faible.

 

Exemple de recherche de chemin minimum par Bellman-Kalaba

Légende Bellman-Kalaba en action

 

Code de l'algorithme de Bellman-Kalaba

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).
  • k est le compteur utilisé pour trouver le prochain emplacement libre dans le tableau definedVertices.
  • i est l'indice dans X du sommet en cours d'évaluation.

arrayFirstIndex : indice du premier élément dans un tableau[5].

Phase d'initialisation

Nous devons initialiser les tableaux avec une taille correspondant à n.

Nous emploierons j pour raccourcir la notation (j ≥ arrayFirstIndex) ∧ (j < n+arrayFirstIndex), ce qui signifie pour tout emplacement du tableau.

  • k := arrayFirstIndex // Le compteur pointe sur le premier élément d'un tableau.
  • Sommets traités :
    • 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 de départ.
    • (i > k) : definedVertices[i] := arrayFirstIndex-1 // Initialisation du tableau avec une valeur hors des limites du tableau[6].
  • Poids :
    • pathMinWeights[definedVertices[k]] := 0 // Le chemin de la racine vers la racine a un poids égal à zéro.
    • (i > k) pathMinWeights[i] := ?[7] //.
  • É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 tableau[6].

Phase d'exécution


Code (Pseudo-code de Bellman-Kalaba) (19 lignes) :
  1. //Il reste des sommets non traités
  2.  
  3. /*i est l'indice de x
  4. x est non traité mais tous ses précédents le sont*/
  5. i := choisir x {;|&thinsp;(;∈ ;X\definedVertices) (&Gamma;<sup>-1</sup>(y) &sub; ;definedVertices ;&ne; ;&empty;)};
  6.  
  7. //trouver le coût minimum
  8. pathMinWeights[i] := minimum{ pathMinWeigths[j]+weight(j,i)j&Gamma<sup>-1</sup>(x)};
  9.  
  10. //j est l'indice du sommet qui a satisfait le test du minimum
  11. verticesLabels[i] := j;
  12.  
  13. k := k+1;
  14.  
  15. //i est défini comme ∈ au chemin de poids minimum
  16. definedVertices[k] := i;
  17.  

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.

Les instructions des lignes 9 et 12 (recherche du sommet suivant parmi les candidats) peuvent être détaillées comme le montre le bloc de code suivant.


Code (Pseudo-code du bloc minimum) (20 lignes) :
  1. /* ∃ j précédent de i
  2. i est l'indice de x dans X*/
  3. tant_que j : (i,j) &Gamma<sup>-1</sup>(i)
  4.  
  5. //on évite de faire calcul plusieurs fois
  6. temp := pathMinWeights[j] + weight(j,i);
  7.  
  8. //le résultat est meilleur
  9. si temp < tempMin alors
  10.  
  11. //mémoriser comme meilleur candidat au minimum
  12. tempMin := temp;
  13. //indice du sommet meilleur candidat
  14. tempVertrex := j;
  15.  
  16.  
  17. pathMinWeights[i] := pathMinWeigths[j]+weight(j,i);
  18. verticesLabels[i] := i;

Complexité de l'algorithme de Bellman-Kalaba

Selon les implémentations possibles, nous pouvons descendre jusqu'à une complexité de Ordre de grandeur(n) pour le choix de x. La complexité générale est donc de Ordre de grandeur(n2).

Avertissement : Erreur de lecture

Sommaire du document

Erreur de lecture dans la base de données

La page en cours n'a pas été correctement chargée... Vous pouvez essayer d'actualiser la page, ce problème devrait avoir disparu.

De nombreuses fonctions ne sont donc pas accessibles (par exemple les liens de navigation, les sommaires, etc.) et que l'affichage des pages est beaucoup plus lent.

Veuillez réessayer dans quelques minutes (les tests automatiques sont effectués toutes les 15 minutes).

Je vous présente mes excuses pour le désagrément que cela engendre.

Steph.

 

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.

 

Notes

  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.  Type de pondération : Le type de pondération sans impact pour l'algorithme de Bellman-Kalaba, car nous ne sommes pas en présence de circuit gràce à notre classification préliminaire.

  3.  Circuits & Bellman-Kalaba : Cette situation ne devrait normalement pas se présenter si les données de départ permettent un choix de l'algorithme. La présence d'un circuit nous incite à opter pour Moore-Dijkstra.

  4.  retour en arrière : Les résultats sont acquis au fur et à mesure, et ne sont plus mis en doute par la suite

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

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

  7.  pathMinWeights[i] := ? : Le tableau pathMinWeights est rempli au fur et à mesure de l'exécution de l'algorithme, depuis le premier indice jusqu'au dernier, sans retour en arrière. Peu importe donc la valeur contenue lors de l'initialisation.

 

Références

  1. livre Langue du document: fr INFOB321 - Théorie des graphes : JP Leclercq, Cours de Théorie des Graphes et réseaux de Petri (Septembre 2008)
  2. Consulter le document pdf Langue du document: uk Shortest paths in graphs : Zoltan KASA

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-11318
Document créé le 01/01/70 02:00, dernière modification le Vendredi 17 Juin 2011, 12:11
Source du document imprimé : http://www.gaudry.be/
St.Gaudry©07.01.02
Outils (masquer)
||
Recherche (afficher)
Recherche :

Navigation (masquer)
Apparence (afficher)
Stats (afficher)
867 documents
astuces.
niouzes.
definitions.
membres.
2290 messages.

Document genere en :
0,08 seconde
Citation (masquer)
 
l'infobrol
Nous sommes le Mercredi 22 Octobre 2014, 08:20, toutes les heures sont au format GMT+1.00 Heure, heure d'été (+1)