Solu tions des exer cices du cha pitre 1
449
© Dunod – Toute reproduction non autorisée est un délit.
Manifestement désormais F'≤ 0 . La deuxième phase s’achève sans qu’on n’ait trouvé une
meilleure solution que notre « bonne » solution de la phase 1, qui s’avère ici être optimale :
F
x x
x x
*
,
,
=
= =
= =
5
1
′
0
1
4
2
4
En revenant à F = F′ – 4, on obtient la valeur optimale F* = 1.
6
0
3
4
6
6
6
5
x 2 = 1
x 2 = 0
x 4 = 0
x 1 = 0
x 1 = 1
x 3 = 0
x 4 = 1
NB : la gestion de cette arborescence peut s’effectuer à l’aide d’une pile.
449
© Dunod – Toute reproduction non autorisée est un délit.
Manifestement désormais F'≤ 0 . La deuxième phase s’achève sans qu’on n’ait trouvé une
meilleure solution que notre « bonne » solution de la phase 1, qui s’avère ici être optimale :
F
x x
x x
*
,
,
=
= =
= =
5
1
′
0
1
4
2
4
En revenant à F = F′ – 4, on obtient la valeur optimale F* = 1.
6
0
3
4
6
6
6
5
x 2 = 1
x 2 = 0
x 4 = 0
x 1 = 0
x 1 = 1
x 3 = 0
x 4 = 1
NB : la gestion de cette arborescence peut s’effectuer à l’aide d’une pile.