Programarea dinamică

Programarea dinamică este o metodă de optimizare propusă inițial de Richard Bellman. În cazul problemelor de progranmare dinamică, se consideră că se pornește dintr-o stare inițială S0 și trebuie să se ajungă într-o stare finală Sn , trecând prin mai multe stări intermediare S1 , S2 , ..., Sn-1 ca urmare a unei succesiuni de decizii d0 , d1 , ..., dn-1 . Fiecare decizie di are ca efect trecerea din starea Si în starea Si+1. Problema constă în stabilirea acelui șir de decizii, pentru care calea parcursă în spațiul stărilor este optimă.
 

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.


- Figura 1 -

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 dinamice

1. Cea mai scurtă cale între două vârfuri ale unui graf orientat

Fie 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.


- Figura 2 -

Î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. 
Conform principiului minimului, orice porțiune a unei căi de cost minim este, de asemenea, o cale de cost minim. În consecință, pornind înapoi de la vârful final R către cel inițial, vom construi un fascicol de căi de cost minim, adică un arbore cu rădăcina în R și cu ramurile orientate către stânga. Calea optimă căutată va fi acea ramură a arborelui, care are ca frunză vârful inițial A.
Observăm că în R se poate ajunge din L, M sau N. Vom nota lângă aceste vârfuri cu culoare roșie costul minim al deplasării din fiecare din aceste vărfuri în R ca în figura 3, în care cea mai scurtă cale din fiecare vârf până la R a fost trasată, de asemenea, cu roșu.


- Figura 3 -

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.


- 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.


- Figura 5 -

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):
 

Origine
A
A
B
B
C
C
D
D
E
E
F
F
G
G
H
H
H
I
I
I
J
J
K
K
L
L
L
M
M
M
N
N
Destinatie
B
C
D
E
E
F
G
H
H
I
I
J
K
L
K
L
M
L
M
N
M
N
O
P
O
P
R
P
R
S
R
S
Lungime
1
2
2
1
1
2
3
3
4
2
3
3
2
4
4
1
6
7
1
6
5
2
1
5
5
2
6
5
1
7
6
1

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:
 

Vârf curent
R
L
M
N
G
H
I
J
D
E
F
B
C
A
Vârf tata
null
R
R
R
L
L
M
M
H
I
I
E
E
B
Nivel
0
1
1
1
2
2
2
2
3
3
3
4
4
5
Distanta
0
6
1
6
10
7
2
6
10
4
5
5
5
6

Algoritmul, pe baza căruia se alcătuiește această listă prin trasare înapoi, poate fi schițat astfel:
 
- Se dau graful G, vârful inițial X și vârful final Y.
- Se fac inițializările: se construiește lista LG, care conține arcele grafului G, și lista LA, care conține inițial numai vârful final Y, de nivel 0 și distanță 0.
- indiceNivel=0;
- cât timp (mai există în LG arce care se termină în unul din vârfurile de nivel indiceNivel) {
      - pentru fiecare arc  LG[k]  care se termină în unul din vârfurile de nivel indiceNivel {
          - se pune în LA un vârf V, a cărui etichetă este cea a vârfului de origine al arcului LG[k];
          - dintre toate vârfurile din LA de nivel indiceNivel, către care pornesc arce din V, ca tată al vârfului V se alege acel vârf T pentru care distanta
                                           d=LG[k].lungime+T.distanta
           este minimă (s-au notat cu LG[k].lungime- lungimea arcului LG[k] si cu T.distanta distanța de la vărful T la vârful final)
         - ca distanță de la vârful V la vârful final se pune d.
         - ca nivel al vârfului V se pune indiceNivel+1.
         - se elimină din LG arcul LG[k]
      }// sfârșit pentru fiecare
     - indiceNivel=indiceNivel+1;
} // sfârșit cât timp

Complexitatea acestui algoritm este O(n3), unde n este numărul de arce ale grafului.
 
Iată și o prezentare mai rafinată a algoritmului de construire a arborelui de acoperire pentru căile de lungime minimă prin parcurgere înapoiȘ

1. Se dau graful G, vârful inițial X și vârful final Y.
2. Se creează lista LG, care conține arcele grafului G.
3. Se creează lista vidă LA care va conține vârfurile arborelui de acoperire.
4. Se pune în LA elementul corespunzător vârfului Y, cu tată null și distanță la rădăcină 0. Acesta este rădăcina arborelui.
5. Inițializări: indiceNivel=0; inceputNivel=0; sfarsitNivel=0; epuizatArce=false;
6. cât timp (epuizatArce==false) {
      6.1. indiceNivel = indiceNivel+1; // se trece la nivelul următor
      6.2. epuizatArce=true; // se face ipoteza că nu mai există arce care se termina in unul din varfurile nivelului curent
      6.3. pentru i=inceputNivel pana la i=sfarsitNivelpas1 {
             6.3.1.  varfTinta=LA[i]; // i este indicele vârfului din LA în care se termină arcul
             6.3.2.  k=-1; // k este indicele arcului curent din LG
             6.3.3. cât timp (există în LG arce neparcurse) { // se extrag din LG toate arcele care se termină în LA[i]
                   6.3.3.1. k=k+1; // se trece la arcul următor
                   6.3.3.2. dacă (arcul curent LG[k] se termină în vârful LA[i] atunci
                         6.3.3.2.1. epuizatArce=false; // s-a găsit un arc care se termină în unul din vărfurile nivelului curent
                         6.3.3.2.2. Se caută în LA vârful de origine al arcului curent LG[k], fie acesta LA[j]
                         6.3.3.2.3. dacă s-a găsit un LA[j]atunci {
                            6.3.3.2.3.1. dacă (LG[k].lungime+LA[i].distanta < LA[j].distanta) atunci {// distanta noua este mai mica decat ceda veche
                               6.3.3.2.3.1.1. LA[j].distanta=LG[k].lungime+LA[i].distanta; 
                               6.3.3.2.3.1.2. LA[j].tata=LA[i];   // calea cea mai scurta trece prin LA[i] }
                               6.3.3.2.3.1.3. } sfârșit atunci 6.3.3.2.3.1.
                            6.3.3.2.3.2. sfârșit dacă 6.3.3.2.3.1.
                         6.3.3.2.4. altfel { // originea arcului curent LG[k] nu exista in LA
                             6.3.3.2.4.1. se pune în LA un vârf nou, având eticheta originii arcului LG[k], tatăl LA[i] 
                                                și distanța egala cu LG[k].lungime+LA[i].distanta
                         6.3.3.2.5. } sfârșit altfel 6.3.3.2.4
                         6.3.3.2.6. } sfârșit dacă 6.3.3.2.3.
                         6.3.3.2.7. se elimină din LG arcul LG[k]
                   6.3.3.3. } sfârșit dacă 6.3.3.2.
             6.3.4. } sfârșit cât timp 6.3.3.
             6.3.5. // se trece la un nivel nou, recalculand indicii din LG ai ultimului nivel
                   inceputNivel=sfarsitNivel+1;
                   sfarsitNivel=LG.lungime-1;
       6.4. } sfarsit pentru 6.3.
 7. } sfarsit cat timp 6.
 8. Sfarsit

La incheierea executarii acestui algoritm, lista LA conține arborele de acoperire cu rădăcina în vârful final Y, pentru care calea de la fiecare nod la rădăcina arborelui (la vârful final Y) are lungimea minimă. Reconstituirea căii de lungime minimă de la vârful inițial X la vârful final Z se face simplu: 
    - se caută în LA vârful inițial X
    - se urmează calea de la X spre tatăl acestuia și așa mai departe, până se ajunge la vârful final Y.

În fișierul DynamicProg1.java este definită clasa DynamicProg1, care conține metoda statică trasareInapoi pentru obținerea celei mai scurte căi între două vârfuri date ale unui graf orientat prin trasare înapoi, respectând algoritmul de mai sus. Metoda primește ca argumente graful dat (sub forma de listă de arce) și cele două etichete ale vârfului inițial și vârfului final. Soluția obținută constă din arborele de acoperire rezultat și calea de la vârful inițial la cel final. Arborele de acoperire se obține sub formă de listă de vârfuri, în care rădăcina este nodul final, iar fiecare vârf conține distanța cea mai scurtă până la rădăcină și o referință către vârful tată.

În fișierul TestDynProg1.java este dat programul de testare a clasei DynamicProg1, folosindu-se ca test graful din figura 2.

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.


- 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:
   - la inițializarea listei LA, ca rădăcină a arborelui se pune vărful inițial X;
   - parcurgerea nivelurilor se face de la vârful inițial X către cel final.
 
În clasa DynamicProg1 din fișierul DynamicProg1.java există și metoda statică trasareInainte, prin care se poate obține calea cea mai scurtă cale între două vârfuri date prin trasare înainte. Comparând-o cu metoda trasareInapoi din aceeași clasă, prezentată anterior, se poate constata că sunt aproape identice.
În fișierul TestDynProg1.java, deja prezentat, se face și testarea acestei metode.

Algoritmii și programele prezentate aici funcționează nu numai pentru determinarea căilor celor mai scurte în grafuri aciclice, ca cel din figura 2, ci și în cazul grafurilor orientate cu cicluri. Ca exemplu, în programul din fișierul TestDynProg1a.java se face testarea pentru graful orientat tare conex din figura 7.


- Figura 7 -

Dacă se caută în acest graf calea cea mai scurtă între vârfurile A și D, arborele obținut la trasare înapoi este trasat cu roșu în figura 8, în care lângă fiecare vârf este scrisă cu roșu distanța minimă până la vârful D.


- Figura 8 -

Arborele obținut prin trasare înainte este trasat cu roșu în figura 9, în care lângă fiecare vârf este scrisă cu roșu distanța cea mai scurtă de la vârful A.


- Figura 9 -

În ambele cazuri, cea mai scurtă cale este A-C-D, de lungime 17. 

2. Ordinea optimă de calculare a unui produs de matrici

Se 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ă, 
           Cij=min(k)(Ci,k-1+Ck,j+di.dk.dj+1) , unde k=i+1, i+2, ..., j-1.
Grupăm mai întâi matricile câte două, apoi câte trei, etc., luând în considerație de fiecare dată ordinea optimă (de cost minim) a efectuării înmulțirilor. Rezultatele calculului vor fi puse într-o matrice C, în care fiecare element Cij de deasupra diagonalei principale reprezintă costul optim al calculării lanțului Mix...xMj, calculat cu formula de mai sus. Considerăm că Cii=0. Ordinea de calcul va fi pe diagonalele matricei:
      - lanturile de lungime 2: C0,1, C1,2, C2,3, ..., Cn-2,n-1
      - lanțurile de lungime 3: C0,2, C1,3, C2,4, ..., Cn-3,n-1
      - etc. 
Triunghiul inferior al matricei poate fi folosit pentru păstrarea valorilor optime ale lui k. Astfel, Cji va fi valoarea lui k pentru care se obține costul Cij.

Algoritmul folosit pentru completarea matricei C este următorul:

  - Se dă vectorul d=(d0, d1, ..., dn).
  - Se construiește matricea C[n,n] cu toate elementele nule.
  - pentru m de la 1 la n-1pas1repetă {  // m este numărul de ordine al codiagonalei
       pentru i de la 0 la n-m-1 pas 1repetă {
           j=i+m;
          C[i,j]=min(i<k<j)(C[i,k-1]+C[k,j]+di.dk.dj+1)
          C[j,i]=valoarea lui k pentru care se obține minimul lui C[i,j].
      } // sfârșit pentru i
    }// sfârșit pentru m

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:
 

0
1800
 2100
 5550
 5070
1
0
450
 5250
 3630
2
2
0
750
 2550
 2
3
0
3000
 2
4
0

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:
    - La calcularea elementului C[0,4] valoarea optimă a lui k a fost C[4,0]=2. În consecință, calculul s-a făcut sub forma C[0,4]=C[0,1]+C[2,4], iar gruparea corespunzătoare a matricilor este (M0xM1)x(M2xM3xM4).
   - La calcularea costului C[2,4] valoarea optimă a lui k este C[4,2]=4. În consecință, calculul s-a făcut sub forma C[2,4]=C[2,3]+C[4,4], iar gruparea corespunzătoare a matricilor este (M0xM1)x((M2xM3)xM4).

Stabilirea ordinii efectuării înmulțirilor poate fi exprimată printr-un algoritm exprimat de următoarea procedură recursivă:
    Fie i, j - indici întregi, c - matricea costurilor, lista - o listă inițial vidă (c și lista sunt variabile externe față de procedură)
    procedura ordine(i, j)  {
      dacă (i<j) atunci {
          k=c[j,i];
          ordine(i, k-1);
          ordine(k, j);
          adaugă k ca element în lista;
      } // sfârșit dacă
    } // sfârșit procedură
Procedura se apelează inițial cu argumentele (0, n-1), unde n este dimensiunea matricei C.

Î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.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunărea de Jos" din Galați