Caracteristicile problemelor de programare dinamicăProblemele de programare dinamică au următoarele caracteristici:1. Obținerea soluției se face în etape, iar în fiecare etapă trebuie luată o decizie. 2. Cu fiecare etapă sunt asociate un număr oarecare de stări. 3. Decizia luată în fiecare etapă provoacă trecerea din starea curentă în una din stările asociate etapei următoare. 4. Decizia care se ia într-o stare dată depinde numai de starea curentă și de scopul urmărit, dar nu depinde de deciziile anterioare. |
Rezolvarea problemelor de programare dinamică se bazează pe principiul optimului, care poate fi formulat astfel:
O tactică optimă are proprietatea că, oricare ar fi starea inițială și deciziile inițiale, restul deciziilor trebuie să constituie o tactică optimă pornind din starea curentă.Când optimizarea constă în căutarea unui minim (cost minim, consum minim, lungime minimă etc), principiul optimului se transformă în principiul minimului, care poate fi formulat astfel:
Orice subtraiectorie a unei traiectorii optime între două stări date este, de asemenea, o traiectorie optimă între stările de la capetele sale.
În graful neorientat din figura 1, lanțul de lungime
minimă între nodurile B și D este B-A-E-D, având lungimea 58. Remarcăm
ca B-A-E este lanțul de lungime minimă între nodurile B și E. În mod
similar, A-E-D, B-A, A-E, E-D sunt lanțuri de lungime minimă
între nodurile de la capetele lor, ceeace ilustrează principiul
minimului.
Să considerăm acum că dorim să determinăm lanțul de lungime maximă între două noduri ale aceluiași graf. Lanțul de lungime maximă între nodurile B și D este B-C-D (lungime 75). Remarcăm, însă, că lanțul de lungime maximă între punctele B și C nu este muchia B-C, ci lanțul B-A-E-D-C. Constatăm, deci, că subtraiectoriile unei traiectorii de lungime maximă nu sunt, ele însele, traiectorii de lungime maximă. |
Ca și în metoda Greedy, în metoda programării dinamice soluția problemelor de programare dinamică se obține sub forma unui șir de decizii. Spre deosebire de metoda Greedy, în care soluția este construită direct de la starea inițială la cea finală, fără a se analiza căi alternative, în metoda programării dinamice se construiesc simultan mai multe căi, cu memorarea stărilor și deciziilor intermediare, astfel încât să se obțină în final calea optimă.
O altă caracteristică a programării dinamice este că soluția
se construiește "de jos în sus" ("bottom up", de la
soluții ale subproblemelor la soluția finală), folosindu-se rezultatele
intermediare dintr-o etapă la obținerea celor din etapa următoare.
Această caracteristică este atât de importantă, încât în prezent mulți
autori consideră drept metodă de programare dinamică orice metodă în
care soluția unei probleme se face prin calcularea unor soluții parțiale
și combinarea acestora, astfel încât să fie satisfăcut un criteriu de
optimizare.
Exemple de proiectare a algoritmilor prin tehnica programării dinamice1. Cea mai scurtă cale între două vârfuri ale unui graf orientatFie graful orientat fără cicluri din figura 2, în care se cere să se determine calea de cost minim între vârfurile A și R. Conform acestui graf, în starea A se există două decizii posibile care conduc, respectiv, în stările B și C. Pe arce sunt notate costurile executării deciziilor respective. Dacă s-a ajuns în starea B, se pot lua iarăși două decizii, care conduc respectiv în stările G și H. Din starea H se pot lua trei decizii, care conduc în K, L sau M. Se cere să stabilim succesiunea optimă de decizii, astfel încât costul deplasării din A în R să fie minim.
În metoda programării dinamice, soluția se poate construi în
etape, pornind fie de la A și deplasându-ne înainte către
R, fie pornind de la vârful R și deplasându-ne înapoi
către A. Vom folosi aici deplasarea înapoi, construind în
paralel toate căile prin care se poate ajunge la vârful final R.
Deocamdată, nu se poate ști care din aceste arce aparține celui mai scurt drum de la A la R, dar se știe că, fiecare din ele, constituie cel mai scurt drum de la nodul lor de origine la R. În etapa următoare, trebuie stabilit care sunt căile cele mai scurte de la fiecare din vârfurile penultimului nivel, până la R. Din vârful G există o singură cale către unul din nodurile marcate cu roșu de pe nivelul următor, respectiv arcul G-L. În G vom pune costul căii G-L-R, respectiv 4+6=10. Din vârful H există un arc spre L și altul spre M. Constatăm că, pe ambele căi, sumele costurilor sunt identice, respectiv 1+6=6+1=7. Vom alege una dintre ele, de exemplu H-L-R, iar în vârful H vom pune costul acesteia, respectiv 7. Din vârful I pornesc trei arce, către L, M și N. Adunând costurile acestor arce cu costurile atașate vârfurilor de destinație obținem: 7+6=13, 1+1=2, 6+6=12. Dintre acestea, distanța minimă este 2, deci alegem calea I-M-R, cu costul 2. Din vârful J, pornesc două arce, către M și N. Costurile căilor respective sunt: pentru J-M-R 5+1=6, iar pentru J-N-R 2+6=8. Calea optimă este, deci, J-M-R. Marcând cu roșu traseele optime și costurile căilor optime de la vărfurile din penultimul nivel la R se obține graful din figura 4.
Procedând în același mod și în celelalte etape, se obține graful din figura 5. După cum se poate constata din această figură, calea optimă de la A la R este A-B-E-I-M-R, costul ei fiind 6. În dreptul fiecărui vârf este scris cu roșu costul căii de la vârful respectiv la R.
Datorită faptului că s-a construit calea optimă înapoi de la vârful final, R, către cel inițial, A, am obținut și toate căile optime de la alte vârfuri ale grafului până la R Pentru a algoritmiza aceest procedeu, este necesar sa adoptam
structurile de date prin care se reprezintă graful și arborele de
acoperire de distanță minimă. Vom considera ca graful se reprezintă
printr-o listă a arcelor, în care fiecare element de listă conține
vârful de origine, vârful de destinație și lungimea. Se obține astfel
lista următoare (implementată sub formă de tablou, în care fiecare
coloana este un element al listei):
Arborele de acoperire rezultat la parcurgerea înapoi poate fi
pus, de asemenea, sub forma unei liste, în care fiecare element
reprezintă un vârf al arborelui, conținănd eticheta vârfului curent, o
referință la tată și distanța de la vârful curent la vârful final. În
exemplul nostru, această listă (reprezentată tabelar) este dată mai jos:
Algoritmul, pe baza căruia se alcătuiește această listă prin
trasare înapoi, poate fi schițat astfel:
Complexitatea acestui algoritm este O(n3),
unde n este numărul de arce ale grafului.
Dacă se proceda invers, construind calea optimă de la A la R, s-ar fi obținut și căile optime de la A către alte vârfuri ale grafului, ca în figura 6.
În figura 6, în dreptul fiecărui vârf este scris cu
roșu costul căii optime de la A la vârful respectiv (calea trasată cu
roșu). Să considerăm, de exemplu, vârful L. Către acest vârf conduc trei
arce, respectiv de la H, I și J. Costurile căilor de la A la M prin
vârfurile respective sunt: 6+6=12 pentru calea prin H, 4+1=5 pentru
callea prin I și, respectiv, 7+5=12 pentru calea prin J. Dintre
acestea, s-a ales calea optimă A-B-E-I-M, de cost 5. Calea de cost minim
între vârfurile A și R obținută prin construire înainte,
respectiv A-B-E-I-M-R este aceeași ca și în cazul construirii înapoi.
Algoritmul folosit în acest scop este similar cu cel folosit la
parcurgerea înapoi, cu următoarele deosebiri:
2. Ordinea optimă de calculare a unui produs de matriciSe cere să se calculeze produsul M0[d0,d1] x M1[d1,d2] x M2[d2,d3] x ... x Mn-1[dn-1,dn], în care M0, M1, ..., Mn-1 sunt matrici, iar d0, d1, d2, ..., dn sunt dimensiunile acestora. Se observă că este respectată regula conform căreia, la înmulțirea a două matrici, numărul de coloane al matricei din stânga trebuie să fie același cu numărul de linii al matricei din dreapta. Aceste dimensiuni pot fi păstrate în vectorul d=[d0, d1, d2, ..., dn].Când se înmulțesc două matrici, M0[d0,d1] x M1[d1,d2], numărul de operații de înmulțire este d0.d1.d2. Se poate constata cu ușurință că ordinea, în care se efectuează operațiile de înmulțire, nu este indiferentă. De exemplu, în cazul produsului de matrici M0[5, 100]xM1[100, 200]xM2[200, 1] dacă matricile se grupează sub forma ((M0 x M1) x M2), se calculează mai întâi produsul M0xM1 se fac 5x100x200=100000 înmulțiri, obținând o matrice de dimensiuni [5, 200]. Înmulțind apoi această matrice cu M2 se mai fac 5x200x1=1000 înmulțiri. În total se efectuează, deci, 101000 înmulțiri. Să schimbăm acum ordinea înmulțirilor, grupând matricile sub forma (M0 x (M1 x M2)). Produsul M1xM2 necesită 100x200x1=20000 înmulțiri, obținându-se o matrice de dimensiuni [100, 1]. Înmulțirea matricei M0 cu rezultatul înmulțirii precedente necesită 5x100x1=500 înmulțiri. Se fac, deci, în total 20500 înmulțiri, adică de aproape 5 ori mai puține decât în cazul precedent. Se pune problema găsirii ordinii optime în care se fac cele n-1 operații de înmulțire dintre n matrici. Vom considera că este optimă acea ordine a efectuării operațiilor, pentru care numărul de înmulțiri între elementele matricilor este minim. O modalitate este de a calcula numărul de înmulțiri pentru toate cele (n-1)! permutări posibile. Este evident că, pentru n mare, volumul de calcul este foarte mare. Complexitatea poate fi redusă prin aplicarea metodei programării dinamice. Fie produsul de matrici (MixMi+1x...xMk-1)x(Mkx...Mj).
Conform principiului minimului, dacă această ordine a
calculelor (în care se fac mai întăi înmulțirile dininteriorul
perechilor de paranteze și apoi înmulțirea dintre cele două matrici
astfel obținute) este optimă (necesită număr minim de înmulțiri), atunci
și calcularea fiecăreia dintre cele două paranteze este efectuată în
ordinea optimă. Notăm cu Cij costul minim al calculării
produsului MixMi+1x...xMj.
Observăm că, Algoritmul folosit pentru completarea matricei C este următorul: - Se dă vectorul d=(d0, d1, ..., dn). Complexitatea acestui algoritm este O(n3), ceeace, pentru n>5 este sensibil mai mică decât n!,cât ar fi dacă s-ar încerca toate variantele posibile. Ca aplicație, vom considera produsul de matrici M0[20,30]xM1[30,3]xM2[3,5]xM3[5,50]xM4[50,12]. Vectorul de dimensiuni corespunzător este d=(20, 30, 3, 5, 50, 12). Dacă s-ar calcula acest produs de matrici de la stânga la dreapta, ar fi necesare 19100 înmulțiri. Aplicând algoritmul de mai sus pentru obținerea ordinii optime
a înmulțirilor se obține următoarea matrice C:
Costul minim C[0,4] al calculării întregului produs
de matrici este 5070 (sensibil mai mic decât 19100) și corespunde
efectuării calculelor în următoarea ordine: (M0xM1)x((M2xM3)xM4).
Această ordine de calcul a fost stabilită în modul următor: Stabilirea ordinii efectuării înmulțirilor poate fi exprimată
printr-un algoritm exprimat de următoarea procedură recursivă: În fișierul DynamicProg2.java este dată o aplicație java în care se aplică algoritmii de mai sus pentru calculul matricei costurilor și determinarea ordinii înmulțirilor matricilor. Aplicația se lansează în execuție dându-i ca parametri în linia de comandă elementele vectorului d al dimensiunilor matricelor care se înmulțesc. |