Embed Size (px)
Citation preview
Exercices série1 Page 1 sur 3
© xicarre.com
Chemin de valeur optimale Algorithmes de Bellman-Kalaba et de Floyd Les corrigés sont donnés en fin de document
Exercice 1Exercice 1Exercice 1Exercice 1 Les sommets représentent des sites. Les arcs représentent des voies de communication. Sur le graphe précédant on peut construire deux situations d'étude: 1) Les valeurs des arcs représentent le nombre de points de vente pouvant être visités par un représentant de commerce. On veut déterminer le parcours du sommet 1 au sommet 8, qui fait visiter le plus grand nombre de points de vente. 2) Les valeurs des arcs représentent les coûts (carburant, péage, etc.) pour parcourir ces voies. On veut déterminer le parcours le plus économique du sommet 1 au sommet 8. Résoudre ces deux problèmes. Solution: Chemin de valeur maximale : valeur 13 chemin: 1 3 4 6 8 Chemin de valeur minimale: valeur 9 chemin: 1 2 5 7 8
Exercice 2Exercice 2Exercice 2Exercice 2 Déterminer un chemin de valeur minimale du sommet 1 au sommet 8 dans le graphe de schéma ci-dessous. Peut-on rechercher un chemin de valeur maximale dans ce graphe ?
1
2
3
4
5
6
7
8
2
5
4
2
3
1 2
1
3
2
4
7 1
2
5
4
6
3
7
8
12 3
2
2
5
3
4
9
2
3 8
10
Exercices série1 Page 2 sur 3
© xicarre.com
Exercice 3Exercice 3Exercice 3Exercice 3 Rechercher un chemin de valeur maximale dans le graphe :
Correction
Exercice 2Exercice 2Exercice 2Exercice 2
6 3 4 3 5 6 7 1 1 2 1 4 4 5
Algorithme de Bellman-Kalaba k
λj : valeur du chemin du sommet 1 au sommet j père du sommet j
j→ 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
0 +∞ +∞ +∞ +∞ +∞ +∞ +∞ 1
0 4 7 +∞ 12 +∞ +∞ +∞ 1 1 1
0 4 7 6 10 16 +∞ 20 1 1 2 3 5 5
0 4 7 6 10 14 16 18 1 1 2 3 5 4 5
0 4 7 6 10 14 16 18 1 1 2 3 5 4 5
p=0
p=1
p=2
p=3
p=4
Chemin de valeur minimale de 1 à 8 : 1 → 3 → 5 → 8 valeur 18
8
1
2
3
4
5
6 9
6
15 8
10
2 3
5 7
7
chemin : )1( −pkλ arc : v[ k,j]
chemin calculé au rang p : 1 k j
on ne calcule ● que si )1( −pkλ ≠ +∞
● et que pour k pour lequel )1( −pkλ a une valeur différente de )2( −p
kλ
on cherche la valeur minimale entre )1( −pjλ et les valeurs )1( −p
kλ + v[ k,j] calculées
la valeur retenue détermine le chemin retenu et le père de j sur ce chemin p=1 112 : 0+4 113 : 0+7 115 : 0+12
p=2 132 : 7+2 124 : 4+2 135 : 7+3 156 : 12+4 158 : 12+8
p=3 143 : 6+3 163 : 16+5 146 : 6+9 156 : 10+4 147 : 6+10 167 : 16+2 158 : 10+8
p=4 163 : 14+5 167 : 14+2 178 : 16+3
arcs du graphe : valeurs ↱ 1 2 3 4 5 6 7 8
1 4 7 12 2 2 3 2 3 4 3 9 10 5 4 8 6 5 2 7 3 8
Exercices série1 Page 3 sur 3
© xicarre.com
Exercice 3Exercice 3Exercice 3Exercice 3
5
4 2 3 4 3 1 1 1 1 2
Algorithme de Bellman-Kalaba k
λj : valeur du chemin du sommet 1 au sommet j père du sommet j j→ 1 2 3 4 5 6 1 2 3 4 5 6
p=0 0 -∞ -∞ -∞ -∞ -∞ 1
p=1 0 8 9 6 8 -∞ 1 1 1 1
p=2 0 8 18 11 11 23 1 2 3 4 5
p=3 0 8 18 20 16 26 1 2 3 4 5
p=4 0 8 18 20 25 31 1 2 3 4 5
p=5 0 8 18 20 25 40 1 2 3 4 5
p=6 0 8 18 20 25 40
1 2 3 4 5
Chemin de valeur maximale de 1 à 6 : 1 → 2 → 3 → 4 → 5 → 6 valeur 40
arcs du graphe : valeurs ↱ 1 2 3 4 5 6 1 8 9 6 8 2 10 7 3 2 3 4 5 7 5 15 6
calculs intermédiaires p=1 112 : 0+8 113 : 0+9 114 : 0+6 115 : 0+8
p=2 123 : 8+10 134 : 9+2 145 : 6+5 126 : 8+7 136 : 9+3 146 : 6+ 7 156 : 8+15
p=3 134 : 18+2 145 : 11+5 136 : 18+3 146 : 11+7 156 : 11+15
p=4 145 : 20+5 146 : 20+7 156 : 16+15
p=5 156 : 25+15
8
1
2
3
4
5
6 9
6
15 8
10
2 3
5 7
7
4
7 1
2
5
4
6
3
7
8
12 3
2
2
5
3
4
9
2
3 8
10
