Cours sur la programmtion dynamique

Description

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

Informations

• Publié par: Shuwyeng
• Nombre de lectures: 51
• Langue: Français

Extrait

Chapitre

6

ProgrammationDynamique. M´ethodesP.S.E.P.

6.1

Programmationdynamique

6.1.1 Exemple introductif Probl`eme:nmatricesM i (m i , m i+1 ilreneima`umtlpilenombrenimisantilumedpitl) cations,variableselonleparenth´esage. Exemple 1On donneM 1 (100,1), M 2 (1,100), M 3 (100,10), M 4 (10,20)alors –(M 1 M 2 )(M 3 M 4 )prend230000multiplications scalaires :100×1×100pourM 12 = M 1 M 2 ,(100,100)et100×10×20pourM 34 =M 3 M 4 ,(100,20)puis100×100×20 pourM 12 M 34 . –M 1 ((M 2 M 3 )M 4 )ations:02o0´prerpne3d1×100×10pourM 23 =M 2 M 3 (1,10), 1×20pourM 24 =M 23 M 4 (1,20)et100×1×20pour le produit final. Moralit´e:ilfautcalculerlemeilleurparenth´esageavantdeselancerdanslescalculs,a` conditionquelecalculduparenthe´sagenesoitpastropcouˆteux. Commeilyaunnombreexponentieldeparenth´esagepossibles,(voirexercice),iln’est pasefficacedelese´num´erertous.Onvautiliserlaprogrammation dynamiquepour trouver lemeilleurparenth´esagepossible.

Ge´n´eralisation:gno´ne´lareiseleprobl`emeenrtuoevlrmeiellueuropegase´htnerapr M i M i+1 . . . M j pour tout couplei, jtel que1≤i≤j≤nLaso.nieialtiborpme`lituludno est obtenue pouri= 1, j=n. On calculec(i, jimald)’loepnombreminrsqeiuse´aritno pourM i M i+1 . . . M j .

Formulationr´ecursive: c(i, j) =M in i≤p<j (c(i, p) +c(p+ 1, j) +m i ×m p+1 ×m j+1 ) Pouravoiraussileparenth´esageonserappellelespqui donnent le minimum.

1

2

CHAPITRE 6.

PROGRAMMATION DYNAMIQUE.

´ METHODES P.S.E.P.

Organisationdescalculsdemani`ereit´erative:ieelau`vesinndo´relrucefaLumro unarbredecalculscontenantbeaucoupderedondance.Poure´vitercescalculsredondants on effectue les calculs en partant des feuilles de l’arbre, en calculant successivement les c(i, j) pourj−i=k,kune constante qui vaudra 0,1, . . . , n−1. 0 – Etape 0 : Pour touti= 1, . . . , n c(i, i) = 0 – Etapek: Pour touti, jdans 1, . . . , ntels quej−i=k, calculer

k p−i j−p−1 c(i, j) =M in i≤p<j (c(i, p) +c(p+ 1, j) +m i ×m p+1 ×m j+1 )

On retient les valeurs depdonnant le minimum. –Arrˆetpourk=n−1 et solution pouri= 1, j=n.

Remonte´edescalculs:oortnuevutatluse´rudtantemonlenrtimaegpoe`asnehtpnra vers les feuilles en utilisant unputionoptn´elasolyanadtnolami.e Pourl’exemplelescalculseffectue´sdonnent:

0 0 0 0 k= 0c(1,1) = 0c(2,2) = 0c(3,3) = 0c(4,4) = 0 1 1 1 k= 1c(1,2) = 10000c(2,3) = 1000c(3,4) = 20000 3 3 k= 2c(1,3) = 2000c(2,4) = 1200 4 k= 3c(1,4) = 3200 Lenombredetermescalcul´esestn−1 +. . .+ 1 =n(n−1)/2. Un terme sur la ligne k=n−1 3 correspondanta`j−i=kdemandek(multiplications. On fait donc Σ n−k)k=O(n) k=0 op´erations.

6.1.2Me´thode Lame´thodeestconcuepourlesproble`mesv´erifiantleprincipesuivant.

Principed’optimalite´dessolutionsinduites.Leprobl`emePeruepdestoce´sopm endeuxsousproble`mesP 1 etP 2 tels que une solutionSdePe´desneesopmocS 1 solution deP 1 etS 2 solution deP 2 . Dans ce cas siSest optimale alorsS 1 etS 2 sont optimales.

Exemple 2Plus court chemin dans un graphe entrexety: si un cheminx=x 1 , x 2 , . . . , x n = yest un chemin de longueur minimale entrexetyalors pour toutzde ce chemin (i) Le cheminx 1 =x, x 2 , . . . , x k =zest un chemin de longueur minimale entrexetzet (ii) le cheminx k =z, x k+1 , . . . , x n =yest un chemin de longueur minimale entrezety.

Leprincipedelame´thodeestlesuivant: 1.Chercheruneformulationr´ecursive. 2.Si´echecen(1)alorsge´ne´raliseretalleren(1)sinonalleren(3). 3.Organiserlescalculsdemani`ereite´rativedesfeuillesverslaracine.

6.2.

EXEMPLES

3

(a)Organisationdescalculsen´etapes. (b)Stockage(tabulation)desr´esultatsinterm´ediairespourn’effectueruncalcul qu’une seule fois.

Explication:Laformulationre´cursiveconduit`auneexplorationd’arbrederecherche quiestinefficaceeng´en´eral`acausedesmultiplescalculsredondants(souventlecout est exponentiel, (cf exemple de fibonacci). 4.Retrouverlasolutionenremontantlescalculseffectu´es(exiged’avoirstock´ea`chaque e´tapela(es)valeur(s)quidonne(nt)lasolutionoptimale.)

6.2

Exemples

6.2.1 Voyageur de commerce Probl`eme.nvillesx 0 , x 1 , . . . , x n−1 sitirenueeutenes`avanevertetnseoiefulnttaarnp dex 0 et en minimisant le cout du trajet avecc x,y le cout pour aller directement dex`ay. 1.Ge´ne´ralisation.F(y, S)= cout pour aller dey`ax 0 en passant par toutes les villes de SavecSun sousensemble de villes avecy, x 0 6∈S. 2.Formulationre´cursive.

F(y, S) =M in z∈S (c y,z +F(z, S− {z})

Lasolutionduprobl`emeinitialestobtenueavecF(x 0 , S) avecS={x 1 , . . . , x n−1 }. 3.Organisationen´etapesparcardinalit´ecroissantedesensemblesS. – Etape 0.F 0 (y,∅) =c y,x 0 (avecc x 0 ,x 0 = 0) etV 0 (y,∅) =∅. – Etape k. Pour touty,Stel quey, x 0 6∈Set|S|=k, calculer

F k (y, S) =M in z∈S (c y,z +F k−1 (z, S− {z})) et on se souvient des villes qui donnent le minimum

V k (y, S) ={z|z realise le minimum dans le calcul de F k (y, S)}

– Arret pourk=n−1 : on calcule doncF n−1 (x 0 ,{x 1 , . . . , x n−1 }) qui donne la solutionduprobl`emeinitial. 4.Remont´eedescalculs. Choisirz 1 ∈V n−1 (x 0 ,{x 1 , . . . , x n−1 }te)fie´dnirS 1 ={x 1 , . . . , x n−1 } − {z 1 }. Tant queS p 6=∅faire choisirz p ∈V n−p (z p , S p−1 ) S p =S p−1 − {z p }. fait