Résolution des problèmes de plus court chemin

Le problème du plus court chemin /exercices/corrigé/p1 Le problème du plus court chemin : exercices- corrigé I 0 0 1 0 2 0 3 0 4 0 1 2 1 1 2 2 2 1 3 2 3 1 Les sommets correspondent à l'état du stock à la fin de chaque période : par hypothèse, il peut être de 0, 1 ou 2 Les arcs sont associés aux décisions Initialement, le stock est

TD n o 8 - Recherche de plus courts chemins 1 Lalgorithme de

Les notations sont les suivantes : π[v] contient le prédécesseur de v sur le chemin (NIL s'il n'y en a pas), δ(u,v) est le poids du plus court chemin de u vers v ( ∞s'il n'existe pas), d[v] est une ariablev qui est une borne supérieure du poids du plus court chemin de s vers v (cf question 4) On dé nit le poids d'un chemin p = hv 0,v

TD d’algorithmique avanc ee Corrig e du TD 11 : Plus courts

Comme nous l’avons remarqu e en cours, tout sous-chemin d’un plus court chemin est lui-m^eme un plus court chemin et le probl eme des plus courts chemins v eri e bien la propri et e de sous-structure optimale : nous pouvons donc essayer de le r esoudre par programmation dynamique 1 On note d(m)

Plus courts chemins: algorithme de Floyd-Warshall

du plus court chemin entre i et j (s’il existe, D ij = +1sinon) et R ij est une table de routage Exercice 1: Algorithme de Warshall Dans un premier temps, on s’int eresse a calculer la cl^oture transitive, c’est a dire d eterminer s’il existe un chemin allant de i a j pour tout couple de sommets (i;j) 2X2 Les chemins de G peuvent

Résolution des problèmes de plus court chemin – exercices

Résolution des problèmes de plus court chemin – exercices- corrigé I Le graphe qui permet de modéliser ce problème est analogue à celui vu dans le cours C'est un graphe de 7 sommets numérotés de 0 à 6

SUJET + CORRIGE

Exercice 4: Variantes plus court chemin à origine unique (8 points) L’algorithmedeDijkstra Initialisation (G, s){ // G(S,A,w) oriente pour u dans S faire

Algorithmique — L3 — TD 9 Plus courts chemins : la méthode

Exercice 5 : Quelle est la complexité de cet algorithme (au mieux, au pire, en moyenne)? Exercice 6 : A quoi sert la dernière boucle? Donnez un exemple de graphe où la valeur FAUX est retournée Exercice 7 : Prouvez l’invariant S’il existe un plus court chemin de s à u de k arcs,

Correction sujet du bac en mathématiques, Inde, Pondichéry 2018

reemaths r Corrigé - Bac - Mathématiques - 2018 Déterminons le chemin le plus court qui permet à Louis de relier son domicile à son travail: Notons que: Louis souhaite aller de A à G Après recours à l’algorithme de Dijkstra, nous trouvons comme trajet que Louis doit suivre pour aller de A à G, tout en minimisant la distance ( chemin

Algorithmes de Graphes, HLIN501 Ann ee 2016-2017 L3 Info, L3

- Exercice 4 - Vrai/Faux Con rmer (et prouver) ou in rmer (et donner un contre-exemple) les propri et es suivantes : a Un sous-chemin d’un plus court chemin est un plus court chemin b Si r est un sommet d’un graphe orient e D pond er e par des longueurs positives toutes distinctes,

Universit´e Paris 7 - Master 1 Informatique - Intelligence

Exercice 1 Algorithmes de recherche (8 points) Consid´erez la carte suivante Le but est de trouver le chemin le plus court de A vers I A D E C H F G B I 5 5 6 2 5

L'arc (i, j) correspond à l'acquisition d'un véhicule en début de période i+1 et à sa revente en fin de

période j. Le coût correspondant à cet arc est donné par : Prix d'achat + entretien sur les périodes i+1, ..., j - Revente en fin de période j Compte tenu des valeurs numériques les coût cij des arcs (i, j) sont donnés dans le tableau suivant :

(Il suffit de calculer la première ligne qui correspond à ce qu'il en coûte de garder le véhicule 1, 2 ...ou

6 ans puisque les coûts ne dépendent pas de la période)

1 2 3 4 5 6

0 6600 9 600 15 200 19 600 24 800 31 200 1 6600 9 600 15200 19600 24800

2 6600 9 600 15200 19600 3 6600 9 600 15200

4 6600 9 600 5 6 600

6 Le graphe obtenu est sans circuit. Pour résoudre le problème on peut appliquer l'algorithme de

Bellman.

Sommet 0 : 0 ) = 0

Sommet 1 : 1 ) = 6600 père(1) = 0

Sommet 2 : 2 prédécesseurs 0 et 1 2) = Min ( 9600, 6600+6600 ) = 9600 père(2) = 0

Sommet 3 : 3 prédécesseurs, 3) = Min ( 15 200, 6 600+ 9 600 , 9 600 + 6 600) = 15 200 père(3) = 0

Sommet 4 : 4 prédécesseurs , 4) = Min ( 19 600, 6600 + 15 200, 9 600 + 9600, 15 200 + 6 600 ) = 19 200

père(4) = 2

Sommet 5 : 5 prédécesseurs

5) = Min ( 24 800 , 6 600 + 19 600, 9600 + 15 200, 15 200 + 9 600, 19 200 + 6 600 ) = 24 800

Père (5) = 0, 2 ou 3

Sommet 6 : 6 prédécesseurs

6) = Min ( 31200, 6 600 + 24 800, 9 600 + 19 600, 15 200 + 15 200, 19 200 + 9 600 , 24 800 + 6 600 )

= 28 800

Père(6) = 4

Par exemple, pour le sommet 3, on calcule :

Min( (0) +l(0,3) , (1) +l(1,3) , (2) +l(2,3) )

(0) (1 ) (2) ont été calculés auparavant. (0) = 0 (1) = 6600 (2)= 9 600

Les longueurs l(i,j) sont lues dans le tableau.

Finalement le coût minimal est de 28 800.

Pour cela il faut garder le dernier véhicule 2 ans (père(6) =4) , le précédent 2 ans ( père(4) = 2) et le

premier 2 ans.

Donc la politique optimale sur 6 ans, avec cette structure de coût, est de remplacer le véhicule tous les

2 ans.

Résolution de problèmes de plus court chemin/exercices/corrigé/p2

II Dans le cas a) comme dans le cas b) le graphe est sans circuit. Pour résoudre le problème on utilise

l'algorithme de Bellman. On passe les sommets dans l'ordre chronologique, ce qui fait que chacun est examiné après ses prédécesseurs. Dans le premier cas le calcul est fastidieux. Il est beaucoup plus rapide dans le second. Il faut d'abord calculer le coût associé à chaque arc.

01 23410+210+4 + 4

10+2 10+4 10 + 410 + 4 + 4

10 + 8 + 4

Par exemple pour (1,3) :

Coût fixe 10

Coût variable : 4 unités avec un coût unitaire de production de 1 Coût de stockage : 2 unités avec un coût unitaire de stockage de 2 Pour (2,4 ) : idem sauf que le coût unitaire de production est passé à 2.

Application de l'algorithme de Bellman :

(0 ) = 0

(1 ) = 12 père(1) = 0

(2 ) = Min ( 12 + (1 ), 18 ) = Min ( 24, 18) = 18 père(2) = 0 (3 ) = Min ( 18+ (1 ), 14 2 )) = Min ( 30, 32 ) = 30 père(3) = 1

4) = Min (22+ (2 ), 14 + (3 )) = Min ( 40 , 44 ) = 40 père(4) = 2

Le coût de la politique optimale est de 40.

4 a pour père 2 qui a pour père 0.

Le plus court chemin de 0 à 4 est le chemin 0 - 2 - 4. Il faut produire 4 unités en période 1 et 4 unités en période 3. III Les longueurs sont positives, on pourrait appliquer l'algorithme de Moore Dijkstra, mais on peut

vérifier que ce graphe est sans circuit auquel cas il vaut mieux appliquer l'algorithme de Bellman qui

est plus performant.

L'ordre d'examen des sommets est :

s, a, d, g, b, e, h, p (Conseil : indiquer à côté de chaque sommet les différentes étiquettes)

On trouve :

s a d g b e h p x)

0 1 2 4 4 6 6 7

Père(x) // s s s a d g h

2 - Pour déterminer le plus long chemin, il faut remplacer max par min. On trouve :

s a d g b e h p x)

0 1 3 6 10 14 16 17

Père(x) // s a d d b e e ou h

Résolution de problèmes de plus court chemin/exercices/corrigé/p3

3 - Pour déterminer le chemin dont la difficulté maximale est la plus faible possible, on utilise le

même type de raisonnement que dans les 2 cas précédents.

Par exemple, si on a un chemin dont la difficulté maximale pour arriver en b est de 3 , la difficulté

maximale pour arriver jusqu'en p en passant par b sera de max( 3, 5).

On prendra bien sûr pour arriver en b le chemin dont la difficulté maximale est la plus faible possible.

Pour calculer la difficulté maximale la plus faible possible (x) pour arriver à un sommet, il suffit de

connaître la difficulté maximale la plus faible possible (y) pour arriver à chacun de ses prédécesseurs

et comparer avec la difficulté du dernier arc.

D'où la formule à appliquer :

(x) = min ( max((y), l(y,x) ) le min étant pris sur tous les prédécesseurs y de x. On a remplacé la somme de (y) et l(y,x) par le max de (y) et l(y,x).

On obtient :

s a d g b e h p x)

0 1 2 3 3 4 3 3

Père(x) // s s ou a d a d ou b g h

Par exemple, on peut arriver en p avec une difficulté qui ne dépasse pas 3. Pour arriver en p, il faut venir de h , puis de g , puis de d puis de s ou de a. s d g h p est un chemin dont la difficulté maximale est de 3 et c'est la plus faible possible. IV Le graphe possède un circuit et des arcs de longueur négative.

On peut appliquer l'algorithme de Ford-Bellman.

a b c d e f

Initialisation 0 + + + + +

Itération1 // 4(a) 1(a) 2(b) 5(b) 5(d)

Itération 2 // 2(c) -- 0(b) 3(b) 3(d)

Itération 3 // -- -- -- -- --

A chaque itération on passe en revue tous les sommets et on compare leur marque à celle de leurs

prédécesseurs. On s'arrête lorsqu'aucune marque n'est modifiée.quotesdbs_dbs7.pdfusesText_13

[PDF] Résolution des problèmes de plus court chemin – exercices

6 ans puisque les coûts ne dépendent pas de la période)

1 2 3 4 5 6

0 6600 9 600 15 200 19 600 24 800 31 200 1 6600 9 600 15200 19600 24800

2 6600 9 600 15200 19600 3 6600 9 600 15200

4 6600 9 600 5 6 600

Bellman.

Sommet 0 : 0 ) = 0

Sommet 1 : 1 ) = 6600 père(1) = 0

Sommet 5 : 5 prédécesseurs

5) = Min ( 24 800 , 6 600 + 19 600, 9600 + 15 200, 15 200 + 9 600, 19 200 + 6 600 ) = 24 800

Père (5) = 0, 2 ou 3

Sommet 6 : 6 prédécesseurs

6) = Min ( 31200, 6 600 + 24 800, 9 600 + 19 600, 15 200 + 15 200, 19 200 + 9 600 , 24 800 + 6 600 )

Père(6) = 4

Par exemple, pour le sommet 3, on calcule :

Min( (0) +l(0,3) , (1) +l(1,3) , (2) +l(2,3) )

Les longueurs l(i,j) sont lues dans le tableau.

Finalement le coût minimal est de 28 800.

2 ans.

01 23410+210+4 + 4

10+2 10+4 10 + 410 + 4 + 4

10 + 8 + 4

Par exemple pour (1,3) :

Coût fixe 10

Application de l'algorithme de Bellman :

4) = Min (22+ (2 ), 14 + (3 )) = Min ( 40 , 44 ) = 40 père(4) = 2

Le coût de la politique optimale est de 40.

4 a pour père 2 qui a pour père 0.

L'ordre d'examen des sommets est :

On trouve :

0 1 2 4 4 6 6 7

Père(x) // s s s a d g h

2 - Pour déterminer le plus long chemin, il faut remplacer max par min. On trouve :

0 1 3 6 10 14 16 17

Père(x) // s a d d b e e ou h

3 - Pour déterminer le chemin dont la difficulté maximale est la plus faible possible, on utilise le

D'où la formule à appliquer :

On obtient :

0 1 2 3 3 4 3 3

Père(x) // s s ou a d a d ou b g h

On peut appliquer l'algorithme de Ford-Bellman.

Initialisation 0 + + + + +

Itération1 // 4(a) 1(a) 2(b) 5(b) 5(d)

Itération 2 // 2(c) -- 0(b) 3(b) 3(d)

Itération 3 // -- -- -- -- --