4.1 Notions de pro gram ma tion dyna mique (PRD)
101
© Dunod – Toute reproduction non autorisée est un délit.
4.1.1 Équa tions de récur rence
Appe lons f
*
k 1 x k 2 la valeur opti male des che mins entre A et cha cun des som mets x k de
l’ensemble X k ; soit v k11 1 x k , x k11 2 la valeur de l’arc (x k , x k11 2 pour tout x k11 PX k11 .
On a la for mule d’opti mi sation séquen tielle (récur rence) :
f
*
k11 (x k11 ) 5 OPT
x k PX k
3 f
*
k (x k ) 1 v k11 (x k , x k11 ) 4.
Reve nant à l’exemple, pour la pre mière phase, aucun cal cul n’est néces saire pour
obte nir f
*
1 1 x 1 2 . En effet :
f
*
1 1 B 2 5 8 ; f
*
1 1 c2 5 5 ; f
*
1 1 D2 5 7.
Cherc hons main te nant, pour chaque x 2 P5E, F, G, H6, les valeurs opti males
f
*
2 1 x 2 2 . Il vient :
f
*
2 1 E2 5 OPT
x 1 PX 1
3 f
*
1 1 x 1 2 1 v 2 1 x 1 , E2 4
5 OPT 3 f
*
1 1 B 2 1 v 2 1 B, E2 ; f
*
1 1 C2 1 v 2 1 C, E2 ; f
*
1 1 D2 1 v 2 1 D, E2 4
5 OPT38 1 3 ; 5 1 5 ; 7 1 44 5 10 ,
d’où le choix : (A, C, E) pour la valeur 10 ;
f
*
2 1 F2 5 OPT
x 1 PX 1
3 f
*
1 1 x 1 2 1 v 2 1 x 1 , F2 4
5 OPT 3 f
*
1 1 C2 1 v 2 1 C, F2 4
5 5 1 4 5 9, car F a un seul prédécesseur : C.
d’où le choix : (A, C, F), pour la valeur 9 ;
f 2
*
(G) 5 OPT
x 1 PX 1
3 f
*
1 (x 1 ) 1 v 2 (x 1 , G) 4
5 OPT 3 f
*
1 1 B 2 1 v 2 1 B, G2 ; f
*
1 1 C2 1 v 2 1 C, G2 ; f
*
1 1 D2 1 v 2 1 D, G2 4
5 OPT38 1 4 ; 5 1 6 ; 7 1 24 5 9
d’où le choix : (A, D, G), pour la valeur 9.
Et ainsi de suite.
L’éco no mie de cal cul pro vient de l’affai blis se ment du carac tère com bi na toire
du pro blème. Au lieu d’énu mé rer 64 che mins de quatre arcs, on ne prend en compte
que 3 sous- chemins d’un arc, 9 sous- chemins de deux arcs, dont on ne conserve que
quatre, 7 sous- chemins de trois arcs, dont on ne conserve que deux, 2 sous- chemins
de quatre arcs, dont on ne conserve qu’un. On n’a fait que 18 addi tions de deux
nombres, au lieu de 192.
Dans ce type de pro blème, dit fai ble ment ordonné, le cal cul aurait aussi bien
pu com men cer à par tir du point K en remon tant vers A, ou encore être rela tif à des
groupes de phases conti guës, pris sépa ré ment.
La pré sente méthode s’étend au cas d’autres fonc tions que les fonc tions addi tives ; il
n’est pas néces saire que les ensembles dans les quels s’opèrent les choix soient dis crets,
ils peuvent être conti nus, pourvu qu’ils soient bor nés. En pro gram ma tion dyna mique, on
n’a pas tou jours affaire à un pro blème non ordonné ; sou vent, la décom po si tion et l’opti -
101
© Dunod – Toute reproduction non autorisée est un délit.
4.1.1 Équa tions de récur rence
Appe lons f
*
k 1 x k 2 la valeur opti male des che mins entre A et cha cun des som mets x k de
l’ensemble X k ; soit v k11 1 x k , x k11 2 la valeur de l’arc (x k , x k11 2 pour tout x k11 PX k11 .
On a la for mule d’opti mi sation séquen tielle (récur rence) :
f
*
k11 (x k11 ) 5 OPT
x k PX k
3 f
*
k (x k ) 1 v k11 (x k , x k11 ) 4.
Reve nant à l’exemple, pour la pre mière phase, aucun cal cul n’est néces saire pour
obte nir f
*
1 1 x 1 2 . En effet :
f
*
1 1 B 2 5 8 ; f
*
1 1 c2 5 5 ; f
*
1 1 D2 5 7.
Cherc hons main te nant, pour chaque x 2 P5E, F, G, H6, les valeurs opti males
f
*
2 1 x 2 2 . Il vient :
f
*
2 1 E2 5 OPT
x 1 PX 1
3 f
*
1 1 x 1 2 1 v 2 1 x 1 , E2 4
5 OPT 3 f
*
1 1 B 2 1 v 2 1 B, E2 ; f
*
1 1 C2 1 v 2 1 C, E2 ; f
*
1 1 D2 1 v 2 1 D, E2 4
5 OPT38 1 3 ; 5 1 5 ; 7 1 44 5 10 ,
d’où le choix : (A, C, E) pour la valeur 10 ;
f
*
2 1 F2 5 OPT
x 1 PX 1
3 f
*
1 1 x 1 2 1 v 2 1 x 1 , F2 4
5 OPT 3 f
*
1 1 C2 1 v 2 1 C, F2 4
5 5 1 4 5 9, car F a un seul prédécesseur : C.
d’où le choix : (A, C, F), pour la valeur 9 ;
f 2
*
(G) 5 OPT
x 1 PX 1
3 f
*
1 (x 1 ) 1 v 2 (x 1 , G) 4
5 OPT 3 f
*
1 1 B 2 1 v 2 1 B, G2 ; f
*
1 1 C2 1 v 2 1 C, G2 ; f
*
1 1 D2 1 v 2 1 D, G2 4
5 OPT38 1 4 ; 5 1 6 ; 7 1 24 5 9
d’où le choix : (A, D, G), pour la valeur 9.
Et ainsi de suite.
L’éco no mie de cal cul pro vient de l’affai blis se ment du carac tère com bi na toire
du pro blème. Au lieu d’énu mé rer 64 che mins de quatre arcs, on ne prend en compte
que 3 sous- chemins d’un arc, 9 sous- chemins de deux arcs, dont on ne conserve que
quatre, 7 sous- chemins de trois arcs, dont on ne conserve que deux, 2 sous- chemins
de quatre arcs, dont on ne conserve qu’un. On n’a fait que 18 addi tions de deux
nombres, au lieu de 192.
Dans ce type de pro blème, dit fai ble ment ordonné, le cal cul aurait aussi bien
pu com men cer à par tir du point K en remon tant vers A, ou encore être rela tif à des
groupes de phases conti guës, pris sépa ré ment.
La pré sente méthode s’étend au cas d’autres fonc tions que les fonc tions addi tives ; il
n’est pas néces saire que les ensembles dans les quels s’opèrent les choix soient dis crets,
ils peuvent être conti nus, pourvu qu’ils soient bor nés. En pro gram ma tion dyna mique, on
n’a pas tou jours affaire à un pro blème non ordonné ; sou vent, la décom po si tion et l’opti -