Cours sur la programmtion dynamique

Chapitre 6Programmation Dynamique.M´ethodes P.S.E.P.6.1 Programmation dynamique6.1.1 Exemple introductifProbl`eme : n matrices M (m,m ) `a multiplier en minimisant le nombre de multipli-i i i+1cations, variable selon le parenth´esage.Exemple 1 On donne M (100,1),M (1,100),M (100,10),M (10,20) alors1 2 3 4– (M M )(M M ) prend 230000 multiplications scalaires : 100×1×100 pour M =1 2 3 4 12M M ,(100,100) et 100×10×20 pour M = M M ,(100,20) puis 100×100×201 2 34 3 4pour M M .12 34– M ((M M )M ) prend 3200 op´erations : 1 × 100× 10 pour M = M M (1,10),1 2 3 4 23 2 31×20 pour M =M M (1,20) et 100×1×20 pour le produit final.24 23 4Moralit´e : il faut calculer le meilleur parenth´esage avant de se lancer dans les calculs, a`condition que le calcul du parenth´esage ne soit pas trop couˆteux.Comme il y a un nombre exponentiel de parenth´esage possibles, (voir exercice), il n’estpasefficacedeles´enum´erertous.Onvautiliserlaprogrammation dynamiquepourtrouverle meilleur parenth´esage possible.G´en´eralisation : on g´en´eralise le probl`eme en trouver le meilleur parenth´esage pourM M ...M pour tout couple i,j tel que 1 ≤ i≤ j ≤ n. La solution du probl`eme initiali i+1 jest obtenue pour i = 1,j = n. On calcule c(i,j) le nombre minimal d’op´erations requispour M M ...M .i i+1 jFormulation r´ecursive :c(i,j) = Min (c(i,p)+c(p+1,j)+m ×m ×m )i≤p