programare dinamica - ginfo

8/13/2019 Programare dinamica - Ginfo

1/6

f o c u s

G I n f o n r . 1 5

/ 4 -

a p r i l i e 2 0 0 5

29

Folosirea tehnicii programrii dina-mice presupune intuiie i abilitimatematice. De multe ori rezolvriledate prin aceast tehnic au ordin decomplexitate polinomial.

La un nivel superior, toate tehni-cile de programare pot fi privite caparticularizri ale programrii dina-mice.

Consideraii teoreticeTehnica programrii dinamice seaplic problemelor de optim referitorla un anumit criteriu dat n enun. ncele mai multe cazuri soluia care sa-tisface acest optim nu este unic. nliteratura de specialitate exist douvariante de prezentare general aacestei tehnici. Prima dintre ele estemai degrab de natur deductiv pe

cnd a doua folosete gndirea in-ductiv.n prima variant apare concep-

tul desubproblem . Sunt considerateurmtoarele dou aspecte care carac-terizeaz o rezolvare prin programa-re dinamic: Problema se poate descompune re-

cursiv n mai multe subproblemecare sunt caracterizate de optimepariale, iar optimul global se obi-

ne prin combinarea acestor optimepariale.

Subproblemele respective se supra-pun. La un anumit nivel, dou saumai multe subprobleme necesit,pentru a fi rezolvate, rezolvarea uneiaceeai subprobleme. Pentru a evitarisipa de timp rezultat n urmaunei implementri recursive, opti-mele pariale se vor reine treptat, n maniera bottom-up, n anumitestructuri de date (tabele).

Fie urmtoarea problem:Consi-derm o reea de orae legate prin o-sele. Se cere determinarea pentru fie-care pereche de orae A, B a drumu-lui de lungime minim care le unete.

Problema se poate aborda folo-

sind metoda programrii dinamice.Dac drumul minim care leag orae-le A i B trece prin oraulC , atuncii subdrumurile: A C i C Bsunt de lungime minim, afirmaiecare poate fi demonstrat folosindmetoda reducerii la absurd.

Am descompus astfel problema n subprobleme. Mai departe, dacavem drumuri minime de forma A C B1 i A C B2, atunci sub-

problemele ( A, B1) i ( A, B2) necesitrezolvarea aceleai subprobleme ( A,C ). Ca urmare, problema satisface icel de-al doilea aspect general.

A doua variant de prezentare fa-ce apel la conceptele intuitive de sis-tem, stare i decizie. O problem es-te abordabil folosind tehnica progra-mrii dinamice dac satisface princi-piul de optimalitate sub una din for-mele prezentate n continuare.

Fie secvena de striS0, S1, ,Snale sistemului. Dacd 1, d 2,,d n este un ir optim

de decizii care duc la trecerea siste-mului din stareaS0 n stareaSn,atunci pentru oricei (1 i n) d i+1,d i+2,d n este un ir optim de deci-zii care duc la trecerea sistemuluidin stareaSi n stareaSn. Astfel, de-

ciziad i depinde de deciziile ante-rioared i+1,d n. Spunem c se apli-c metodanainte .

Dacd 1, d 2,,d n este un ir optimde decizii care duc la trecerea siste-mului din stareaS0 n stareaSn,atunci pentru oricei (1 i n) d 1,d 2 ,d i este un ir optim de deciziicare duc la trecerea sistemului dinstareaS0 n stareaSi. Astfel, deciziad i+1depinde de deciziile anterioare

Programare dinamic

Programare DINAMIC .TEORIEi APLICAIIRadu Viinescu, Violeta Viinescu

n acest articol propunem o prezentare a tehnicii programrii dinamice, urmat de o serie de aplicaii cu grad mic de dificultate, care pot fi folositepentru iniierea elevilor n rezolvarea acestor tipuri de probleme.


2/6

G I n f o n r .

1 5 / 4 -

a p r i

l i e

2 0 0 5

30

f o c u s

d 1,d i. Spunem c se aplic meto-danapoi .

Dacd 1, d 2,,d n este un ir optimde decizii care duc la trecerea siste-mului din stareaS0 n stareaSn,atunci pentru oricei (1 i n) d i+1,d i+2,d n este un ir optim de deci-zii care duc la trecerea sistemuluidin stareaSi n stareaSn i d 1, d 2 ,d i este un ir optim de decizii careduc la trecerea sistemului din stareaS0 n stareaSi. Spunem c se aplicmetodamixt .

Considerm o a doua problem:Se consider un triunghi format dinN linii ( 1 N 100 ), fiecare linieconinnd numere ntregi din dome-niul {1, 2, ..., 99}.

Exemplu 73 8

8 1 0

2 7 4 4

4 5 2 6 5

Determinai cea mai mare sum de numere aflate pe un drum ntrenumrul de pe prima linie i unul dintre numerele de pe ultima linie.Succesorii posibili ai unui numr peacest drum sunt situai sub acesta, o poziie la stnga sau o poziie ladreapta.

Sistemul este reprezentat de struc-tura de date corespunzatoare proble-mei, iar decizia este reprezentat dealegerea de a merge la un anumit pasla stnga sau la dreapta.

Problema ndeplinete criteriulde optimalitate n prima sa form:dac suntem pe un nivelk + 1 i amluat toate deciziile de a ajunge n mod

optim la toate elementele de pe acestnivel, atunci deciziad k corespunz-toare niveluluik se construiete de lastnga la dreapta n modul urmtor:pentru fiecare element xde pe nive-lulk se consider cei doi succesoriaflai pe nivelulk + 1 deja procesat ieste ales acela pentru care suma pn n acel moment este maxim.

Indiferent de varianta de prezen-tare, rezolvarea prin programare di-

namic presupune gsirea i rezolva-rea unui sistem de recurene.

n prima variant avem recurene ntre subprobleme, n a doua avemvariant recurene n irul de decizii.Deoarece rezolvarea prin recursivita-te duce de cele mai multe ori la ordinde complexitate exponenial, se aleganumite tabele auxiliare pentru rei-nerea optimelor pariale i spaiul desoluii se parcurge n ordinea cresc-toare a dimensiunilor subproblemelor.

Folosirea acestor tabele d i nu-mele tehnicii respective.

Pentru prima problem folosim omatrice auxiliarCOST n care vomcalcula costurile minime ntre oricareperechi de orae. Sistemul derecurene este urmtorul:

COST ( A, B) =D( A, B)pentru C = 0; COST ( A, B) =

min({COST ( A, B),COST ( A, C ) +COST (C , B) |

pentru C = 1, 2, ,N }).

Pentru a doua problem, triun-ghiul va fi memorat n matricea Asub diagonal, stnga poziiei (P, Q)va fi (P + 1,Q), iar dreapta va fi (P +1,Q + 1). Folosim o matrice auxilia-rS iar sistemul de recurene va fi:

S(P, N ) = A(P, N )pentru 1 P N

S(P, Q) =max{S(P + 1,Q),S(P +1 ,Q+1)}+ A(P, Q)

pentruP COST (I , K ) +COST ( K , J ).

Pentru oraele A i B, un drumde cost minim care le unete va fi datde valorile succesive:B, PRED( A,B),PRED( A, PRED( A, B)),PRED( A, PRED( A, PRED( A, B))), , A.

Acest algoritm este cunoscut nliteratura de specialitate drept algo-ritmulRoy-Floyd .


3/6

f o c u s

G I n f o n r . 1 5

/ 4 -

a p r i l i e 2 0 0 5

31

Aplicaiin cele ce urmeaz vom prezentaenunurile mai multor probleme ivom arta, pentru fiecare dintre aces-tea, modul n care pot fi aplicate cu-notinele teoretice prezentate.

Problema #1

Fie un irX = ( x1, x2, , xn) de lun-gimeN ale crui elemente sunt nu-mere ntregi.

Numim subir al iruluiX o suc-cesiune de elemente dinX , n ordi-nea n care acestea apar nX : X i1, X i2,,X ik unde 1 i1 < i2 < K

avemX K >X P ,SUCC K = un indiceP care maxi-

mizeaz formula anterioarsau

SUCC K = 0, dacL K = 1.

Prezentm versiunea n pseudo-cod a algoritmului prin care se con-struiesc vectoriiL i SUCC :

LN 1

SUCCN 0

pentru K N - 1, 1 pas -1execut

MAX 1pentru P K + 1, N execut

dac XK XP atunciMAX LP + 1

POZ P

sfrit dacLK MAX

dac MAX = 1 atunciSUCCK 0

altfelSUCCK POZ

sfrit dac

sfrit pentrusfrit pentru

Lungimea optim o reprezintvaloarea maxim din vectorulL. Da-c aceast valoare se afl pe poziiaPOZ, atunci soluia optim este ob-inut cu ajutorul vectoruluiSUCC .Varianta n pseudocod este:

MAX -1

pentru K 1, N executdac LK > MAX atunci

MAX LKPOZ K

sfrit dacsfrit pentruscrie MAXct timp POZ 0 execut

scrie X POZPOZ SUCCPOZ

sfrit ct timp

Problema se poate rezolva i fo-losind metoda napoi. n ambele si-

tuaii ordinul de complexitate al al-goritmului de rezolvare esteO(N 2).

Problema #2Se consider o cldire cuN niveluri.n interiorul acesteia se aflM lifturi.Fiecare liftLi face legtura ntre ni-velul de plecarePi i nivelul de sosireU i. Avem ntotdeauna relaiaPi


4/6

G I n f o n r .

1 5 / 4 -

a p r i

l i e

2 0 0 5

32

f o c u s

Problema a fost propus spre re-zolvare elevilor din clasele a XI-a i aXII-a la ediia 2005 aOlimpiadei Lo-cale de Informatic din judeulPra-hova.

RezolvareDacL1, L2,L K -2, L K -1, L K este unir optim de lifturi pentru care avemU L K =N , atunciL1, L2,L K -2, L K -1,este un ir optim pn la nivelulU L K-1=PL K , L1, L2,L K -2 este un ir optimde lifturi pn la nivelulU L K-2 .a.m.d.Folosim doi vectori auxiliariNRi PREDcare memoreaz numrulminim de lifturi, respectiv predece-sorul unui lift n irul de lifturi. Pre-zentm rezolvarea n pseudocod:

NR1 0

PRED1 0

pentru I 2, N executMIN

pentru J 1, I - 1 executpentru K 1, M execut

dac P K = J i UK = Iatunci

dac MIN > NRJ iNRJ 0 atunci

MIN NRJPOZ K

sfrit dacsfrit dac

sfrit pentrusfrit pentrudac MIN atunci

NRI MIN + 1

PRED I POZ

altfelNRI -1

PRED I 0

sfrit dacsfrit pentrudac NRN = -1 atunci

scrie -1

altfelscrie NRNdrum(N)

sfrit dac

subalgoritm drum(NIV)dac PREDNIV > 0 atunci

drum(PRED NIV )

scrie PREDNIV sfrit dacsfrit subalgoritm

Algoritmul are ordinul de com-plexitate O(N 2 M) datorit faptuluic am memorat proprietile lifturi-lor sub forma unei liste de perechi.

Propunem refacerea algoritmului,memornd lifturile care ajung la eta-julI ntr-o list.

Ordinul de complexitate ar tre-bui s devin O(N +M).Problema #3Se consider un teren denivelat, co-dificat cu ajutorul unei matrice A,care conineN linii iM coloane, alecrei elemente sunt numere naturale.

Se numete drumEst-Sud o suc-cesiune de celule ale matricei care n-deplinesc condiia ca, la fiecare pas,dup o celul de coordonate (I , J ) surmeze fie celula dinspreEst(I + 1,

J ), fie celula dinspreSud (I , J + 1).Determinai un drumEst-Sud delungime maxim avnd n plus pro-prietatea c valorile situate n celulelesale sunt n ordine cresctoare.

Date de intrareFiierul de intraredrum.in are ur-mtoarea structur: pe prima linie se afl valorileN i

M, separate printr-un spaiu; pe urmtoareleN linii, se afl valo-

rile corespunztoare ale matricei,cteM numere pe o linie, separate ntre ele prin cte un spaiu.

Date de ieireFiierul de ieiredrum.out trebuies aib urmtoarea structur: pe prima linie valoareaL, lungimea

maxim a drumului. pe urmtoareleL linii, perechiI, J

de coordonate care identific celu-lele care alctuiesc drumul.

Restricii i precizari: 1 N ; M 100; 0 AIJ 1000

Exempludrum.in4 4

1 20 3 10

4 5 6 6

1 7 3 1

drum.out5

1 1

2 1

2 2

2 3

3 4

Rezolvare:Dac (I 1, J 1), (I 2, J 2), (I 3, J 3), , (I K , J K )este un drum de lungime maxim ca-re pornete de la celula (I 1, J 1), atunci(I 2, J 2), (I 3, J 3), , (I K , J K ) este un drumde lungime maxim care pornete dela celula ((I 2, J 2), drumul (I 3, J 3), ,(I K , J K ) este un drum de lungime ma-xim care pornete de la celula (I 3, J 3).a.m.d.

Folosim dou matrice auxiliareLi LEG, care vor pstra informaiile

necesare determinrii drumului.ValoareaLIJ reprezint lungimeamaxim a unui drum care pornetedin celula de coordonateI i J , iarLEGIJ poate avea una dintre valorile0 , 1 sau 2.

Valoarea 0 indic faptul c urm-toarea celul care face parte din drumeste nspreSud , valoarea 1 indicfaptul c urmtoarea celul care faceparte din drum este nspreEst, iarvaloarea 2 indic faptul c celula co-respunztoare este ultima celul adrumului.

Algoritmul descris n pseudocodeste:

pentru I 1, N executLIM 1

LEGIM 2

sfrit pentrupentru J 1, M execut

LNJ 1

LEGNJ 2

sfrit pentru

pentru I N - 1, 1 pas -1execut

pentru J M - 1, 1 pas -1execut

dac AIJ AI+1,J atunciL1 LI+1,J +1

altfelL1 0

sfrit dacdac AIJ AI,J+1 atunci

L2 LI,J+1 +1


5/6

f o c u s

G I n f o n r . 1 5

/ 4 -

a p r i l i e 2 0 0 5

33

altfelL2 0

sfrit dacdac L1 > L2 atunci

DIR 0

L0 L1

altfelDIR 1

L0 L2sfrit dacdac L0 = 0 atunci

LIJ 1

LEGIJ 2

altfelLIJ L0

LEGIJ DIR

sfrit dacsfrit pentru

sfrit pentruX 0

Y 0

MAX 0

pentru I 1, N executpentru J 1, M execut

dac LIJ > MAX atunciMAX LIJX I

Y J

sfrit dacsfrit pentru

sfrit pentruscrie MAXI X

J Y

ct timp (LEG IJ 2) executscrie I, Jdac LEGIJ = 0 atunci

I I + 1

altfelJ J + 1

sfrit dacsfrit ct timpscrie I, J

Algoritmul are ordinul de com-

plexitateO(N M).Problema #4Considerm o tabl de joc de formdreptunghiular avndN linii iMcoloane. Piesele jocului se mic n-cepnd de la o poziie iniial aflatpe prima linie pn la o poziie finalaflat pe ultima linie a tablei.

Este dat o list de mutri posi-bile sub forma unor cvadruple:X 1,

Y 1, X 2, Y 2 cu semnificaia c piesa si-tuat n punctul de coordonate (X 1,Y 1) se poate muta n punctul de co-ordonate (X 2, Y 2); n plus de fiecaredat avem relaia:X 1


6/6

G I n f o n r .

1 5 / 4 -

a p r i

l i e

2 0 0 5

34

f o c u s

Problema #5FieX = (X 1, X 2, ,X n) iY = (Y 1,Y 2, ,Y m) dou iruri care coninn,respectivm numere ntregi. Determi-nai un subir comun al acestoriruri, care are lungimea maxim.

ExempluX = (2,7,7,6,2,8,4,1,3,5,6)Y = (10,2,5,6,7,7,4,3,5,8)

O soluie este:Z = (2,7,7,4,3,5)

RezolvareFieZ = (Z1, Z2, ,Zk-1, Zk) un astfelde subir. Exist o pereche (i, j) pen-tru care avemZk =X i i Zk =Y j. nacest cazZ este optim pentru subsec-veneleX 1,,X i iY 1, ,Y j. De ase-menea, exist o pereche (i', j') pentru

care avemZk-1 =X i' i Zk-1 =Y j'. Maimult, vom avea ntotdeaunai' < i i i'< i. n acest cazZ1, ,Zk-1 este op-tim pentru subsecveneleX 1, ,X i'i Y 1, ,Y j'.

Se aplic metoda napoi; trebuies ajungem pas cu pas de la perechea(i', j') la perechea (i, j).

Considerm toate subsecvenelede formaX 1,,X i i Y 1, ,Y j. Rei-nem pentru o pereche de indici (i, j)valoarea Aij care indic lungimea ma-xim a unui subir comun al irurilorX 1,,X i i Y 1, ,Y j.

Pentrui = 0 sau j = 0 vom avea ntotdeauna A0k = Ah0=0, pentru toa-te valorilek i h pentru care 1 k m i 1 h n.

Pe cazul general, dacX i =Y j,atunciZk =X i =Y j i Aij = Ai-1, j-1 + 1,deoarecei' < i - 1 si j' < j - 1.

DacX i Y j trebuie s eliminmunul dintre capete. S-ar putea savemX i =Y j-1 sauY j =X i-1 (este po-sibil ca ambele egaliti s fie adev-

rate simultan). n general, putem con-sidera c Aij =max( Ai, j-1, Ai, j-1).Se observ c matricea A se poate

construi n urma unei parcurgeri pelinii i coloane.

Prezentm n continuare rezolva-rea n pseudocod:

pentru i 1, n executAi0 0

sfrit pentru

pentru j 1, m executA0j 0

sfrit pentrupentru i 1, n execut

pentru j 1, m executdac Xi = Yj atunci

Aij Ai-1,j-1 + 1

altfel

dac Ai-1,j > Ai,j-1 atunciAij Ai-1,j

altfelAij Ai,j-1

sfrit dacsfrit dac

sfrit pentrusfrit pentru

Subirul propriu-zis se constru-iete tot pe baza matricei A. Se par-curge un drum de la punctul de co-

ordonate (n, m) ctre marginile dinstnga i de sus ale matricei. La fie-care pas, dacX i =Y j se reine aceas-t valoare, altfel se merge ctre maxi-mul coordonatelor precedente (I - 1, J ) i (I , J - 1). Prezentm rezolvarea n pseudocod:

i n

j m

ct timp i > 0 i j > 0 executdac Xi = Yj atunci

scrie XiI I - 1J J - 1

altfeldac Ai-1,j = Aij atunci

i i - 1

altfelj j - 1

sfrit dacsfrit dac

sfrit ct timp

Problema #6

Un graf orientat pe niveluri are no-durile mprite nk 2 mulimiV 1,V 2, ,V k.

n prima mulime se afl nodulsurss, n ultima mulime se afl no-dul terminalt. Arcele unesc noduridin mulimi succesive i au costuripozitive.

Se dorete determinarea unuidrum de cost minim de la surs ladestinaie.

ExempluV 1 = {1},V 2 = {2, 3, 4, 5},V 3 = {6, 7,8},V 4 = {9, 10, 11},V 5 = {12}.Arce: (1, 2) cost 9; (1, 3) cost 7; (1, 4)cost 3; (1, 5) cost 2; (2, 6) cost 4; (2,7) cost 2; (2, 8) cost 1; (3, 6) cost 2;(3, 7) cost 7; (4, 8) cost 11; (5, 7) cost11; (5, 8) cost 8; (6, 9) cost 6; (6, 10)cost 5; (7, 9) cost 4; (7, 10) cost 3; (8,10) cost 5; (8, 11) cost 6; (9, 12) cost4; (10,12) cost 2; (11,12) cost 5.

Un drum de cost minim este: 1,2, 7, 10, 12 i are costul 16.

RezolvareSe aplic metoda nainte. Relaia derecurena este:costnivel, J =min{c JL +costnivel +1 , L} pentruL nV nivel +1i ( J ,L) arc. Algoritmul de determinare acostului minim, n pseudocod, este:

cost N 0

pentru J N - 1, 1 pas -1execut

parcurgem lista de adiacent anoduluiJ

fieK nodul pentru care valoareac JK + cost K este minim

cost[J] c JK + cost Kd[J] K

sfrit pentru

Pentru determinarea drumului decost minim putem utiliza algoritmul:

drum 1 1

drum H N

pentru J 2, H - 1 executdrum J d drum J-1

sfrit pentru

Ordinul de complexitate al algo-ritmului esteO(N +M) dac memo-rm graful prin liste de adiacen.Algoritmul se poate generaliza pen-

tru arce ntre mai multe niveluri.Bibliografie1.Ellis Horowitz, Sartaj Sahni, San-

guthevar Rajasekaran, Computer Algorithms,Computer SciencePress 1998.

2.Emanuela Cerchez, Informatic ,Editura Polirom, 2002

3.*** , probleme propuse la concur-surile de programare.

programare dinamica - ginfo

Documents