Cours sur la programmtion dynamique

Cours sur la programmtion dynamique

Documents
8 pages
Lire
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

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

Sujets

Informations

Publié par
Nombre de visites sur la page 50
Langue Français

Informations légales : prix de location à la page  €. Cette information est donnée uniquement à titre indicatif conformément à la législation en vigueur.

Signaler un problème
Chapitre
6
ProgrammationDynamique. M´ethodesP.S.E.P.
6.1
Programmationdynamique
6.1.1 Exemple introductif Probl`eme:nmatricesMi(mi, mi+1ilreneima`umtlpilenombrenimisantilumedpitl) cations,variableselonleparenth´esage. Exemple 1On donneM1(100,1), M2(1,100), M3(100,10), M4(10,20)alors (M1M2)(M3M4)prend230000multiplications scalaires :100×1×100pourM12= M1M2,(100,100)et100×10×20pourM34=M3M4,(100,20)puis100×100×20 pourM12M34. M1((M2M3)M4)ations:02o0´prerpne3d1×100×10pourM23=M2M3(1,10), 1×20pourM24=M23M4(1,20)et100×1×20pour le produit final. Moralit´e:ilfautcalculerlemeilleurparenth´esageavantdeselancerdanslescalculs,a` conditionquelecalculduparenthe´sagenesoitpastropcouˆteux. Commeilyaunnombreexponentieldeparenth´esagepossibles,(voirexercice),ilnest pasecacedelese´num´erertous.Onvautiliserlaprogrammation dynamiquepour trouver lemeilleurparenth´esagepossible.
Ge´n´eralisation:gno´ne´lareiseleprobl`emeenrtuoevlrmeiellueuropegase´htnerapr MiMi+1. . . Mjpour tout couplei, jtel que1ijnLaso.nieialtiborpme`lituludno est obtenue pouri= 1, j=n. On calculec(i, jimald)loepnombreminrsqeiuse´aritno pourMiMi+1. . . Mj.
Formulationr´ecursive: c(i, j) =M inip<j(c(i, p) +c(p+ 1, j) +mi×mp+1×mj+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) pourji=k,kune constante qui vaudra 0,1, . . . , n1. 0 – Etape 0 : Pour touti= 1, . . . , n c(i, i) = 0 – Etapek: Pour touti, jdans 1, . . . , ntels queji=k, calculer
k pi jp1 c(i, j) =M inip<j(c(i, p) +c(p+ 1, j) +mi×mp+1×mj+1)
On retient les valeurs depdonnant le minimum. Arrˆetpourk=n1 et solution pouri= 1, j=n.
Remonte´edescalculs:oortnuevutatluse´rudtantemonlenrtimaegpoe`asnehtpnra vers les feuilles en utilisant unputionoptn´elasolyanadtnolami.e Pourlexemplelescalculseectue´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´esestn1 +. . .+ 1 =n(n1)/2. Un terme sur la ligne k=n1 3 correspondanta`ji=kdemandek(multiplications. On fait donc Σ nk)k=O(n) k=0 op´erations.
6.1.2Me´thode Lame´thodeestconcuepourlesproble`mesv´eriantleprincipesuivant.
Principedoptimalite´dessolutionsinduites.Leprobl`emePeruepdestoce´sopm endeuxsousproble`mesP1etP2tels que une solutionSdePe´desneesopmocS1solution deP1etS2solution deP2. Dans ce cas siSest optimale alorsS1etS2sont optimales.
Exemple 2Plus court chemin dans un graphe entrexety: si un cheminx=x1, x2, . . . , xn= yest un chemin de longueur minimale entrexetyalors pour toutzde ce chemin (i) Le cheminx1=x, x2, . . . , xk=zest un chemin de longueur minimale entrexetzet (ii) le cheminxk=z, xk+1, . . . , xn=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´ediairespourneectueruncalcul qu’une seule fois.
Explication:Laformulationre´cursiveconduit`auneexplorationdarbrederecherche quiestinecaceeng´en´eral`acausedesmultiplescalculsredondants(souventlecout est exponentiel, (cf exemple de fibonacci). 4.Retrouverlasolutionenremontantlescalculseectu´es(exigedavoirstock´ea`chaque e´tapela(es)valeur(s)quidonne(nt)lasolutionoptimale.)
6.2
Exemples
6.2.1 Voyageur de commerce Probl`eme.nvillesx0, x1, . . . , xn1sitirenueeutenes`avanevertetnseoiefulnttaarnp dex0et en minimisant le cout du trajet aveccx,yle cout pour aller directement dex`ay. 1.Ge´ne´ralisation.F(y, S)= cout pour aller dey`ax0en passant par toutes les villes de SavecSun sousensemble de villes avecy, x06∈S. 2.Formulationre´cursive.
F(y, S) =M inzS(cy,z+F(z, S− {z})
Lasolutionduprobl`emeinitialestobtenueavecF(x0, S) avecS={x1, . . . , xn1}. 3.Organisationen´etapesparcardinalit´ecroissantedesensemblesS. – Etape 0.F0(y,) =cy,x0(aveccx0,x0= 0) etV0(y,) =. – Etape k. Pour touty,Stel quey, x06∈Set|S|=k, calculer
Fk(y, S) =M inzS(cy,z+Fk1(z, S− {z})) et on se souvient des villes qui donnent le minimum
Vk(y, S) ={z|z realise le minimum dans le calcul de Fk(y, S)}
– Arret pourk=n1 : on calcule doncFn1(x0,{x1, . . . , xn1}) qui donne la solutionduprobl`emeinitial. 4.Remont´eedescalculs. Choisirz1Vn1(x0,{x1, . . . , xn1}te)e´dnirS1={x1, . . . , xn1} − {z1}. Tant queSp6=faire choisirzpVnp(zp, Sp1) Sp=Sp1− {zp}. fait