Metoda programarii dinamice

Metoda programarii dinamice

Descrierea metodei

Metoda programarii dinamice se aplica in cazul problemelor de optim in care solutia poate fi privita ca rezultatul unui sir de decizii d₁, d₂, ,d_n, unde alegerea fiecarei decizii d_k depinde de deciziile luate anterior.

Fie s₀ este starea initiala a problemei. Fiecare decizie d_k trece problema din starea s_k-1 in starea s_k. Dupa aplicarea sirului de decizii d₁, d₂, ,d_n problema va ajunge in starea finala s_n.

Metoda programarii dinamice se aplica in problemele de optim care satisfac principiul optimalitatii, ea furnizand intotdeauna solutia optima. Principiul optimalitatii presupune ca optimul global implica optimul local (partial) si este enuntat astfel: daca d₁, d₂, ,d_n este un sir optim de decizii, atunci orice k am considera, sirurile de decizii d₁, d₂, ,d_k , respectiv d_k+1, d_k+2, ,d_n sunt optimale.

In multe situatii practice se utilizeaza conditii "mai slabe", dar suficiente, de optimalitate, atunci cand numai unul din sirurile de decizii d₁, d₂, ,d_k sau d_k, d_k+2, ,d_n este optimal, sau in situatii si mai particulare, in care principiul optimalitatii se verifica numai pentru o anumita valoare a lui k (de exemplu k=1 sau k=n-1). Astfel se disting alte doua forme ale principiului optimalitatii:

• daca d₁, d₂, ,d_n    este un sir optim de decizii, pentru orice k, sirul de decizii d_k, d_k+1, ,d_n este optimal. In acest caz, alegerea deciziei d_k depinde de deciziile d_k+1, d_k+2, ,d_n., ceea ce face ca deciziile se fie luate plecand de la starea finala catre cea initiala: d_n, d_n-1, ,d₁. Verificarea unei astfel de forme a principiului optimalitatii duce la utilizarea unei metode de programare dinamica inainte.
• daca d₁, d₂, ,d_n    este un sir optim de decizii, atunci pentru orice k, sirul de decizii d₁, d₂, ,d_k este optimal. De aceasta data alegerea deciziei d_k va depinde de deciziile d₁, d₂, ,d_k-1, astfel ca deciziile se vor lua plecand de la starea initiala catre cea finala, in ordinea d₁, d₂, ,d_n. Metoda aplicata se va numi programare dinamica inapoi.

De exemplu, considerandu-se un graf etichetat G=(X,A), reprezentand orasele Romaniei si distantele intre ele, se cere sa se gaseasca cel mai scurt drum intre doua orase s si p. Este evident ca se verifica principiul optimalitatii: daca cel mai scurt drum intre Bucuresti si Sibiu trece prin Brasov, atunci (pentru k = Brasov) drumul intre Bucuresti si Brasov, precum si cel dintre Brasov si Sibiu sunt cele mai scurte. Daca ar fi existat altele mai scurte, atunci traseul ales pentru Bucuresti - Sibiu nu ar mai fi fost optim.

Trebuie observat faptul ca rationamentul de mai sus nu are loc si in sens invers, adica daca consideram cel mai scurt drum intre Bucuresti si Rm-Valcea si cel mai scurt drum intre Rm-Valcea si Sibiu, de aici nu putem trage concluzia ca cel mai scurt drum intre Bucuresti si Sibiu trece prin Rm-Valcea. Exista un drum mai scurt prin Brasov.

Cu ajutorul metodei programarii dinamice, problema gasirii drumului cel mai scurt poate fi rezolvata in mai multe variante:

• daca s=s₀,s₁, ,s_n=p este cel mai scurt drum intre s si p, atunci s₁, ,s_n=p este cel mai scurt drum intre s₁ si p, ceea ce ne conduce la relatia de recurenta:

Drum(i,j)=min_i→k

unde am notat prin i→k faptul ca exista arc intre i si k (altfel spus, perechea (i,k)IA), Drum(i,j) este lungimea optima a drumului de la orasul i (nodul i in graf) catre orasul j, iar d[i,j] este distanta intre cele orase (eticheta intre nodurile i si j in graf). Evident Drum(i,i)=0. Aceasta abordare corespunde metodei inapoi.

• daca s=s₀,s₁, ,s_n=p este cel mai scurt drum intre s si p, atunci s=s₀, ,s_n-1 este cel mai scurt drum intre s si s_n-1, ceea ce ne conduce la relatia de recurenta:

Drum(i,j)=min_k→j

cu notatiile de mai sus. Si aici avem Drum(i,i)=0. In acest caz a fost utilizata metoda inainte.

• daca s=s₀,s₁, ,s_n=p este cel mai scurt drum intre s si p si fie

x=s_k=max

cel mai mare nod al secventei considerate, atunci drumurile s=s₀,s₁, ,s_k=x, respectiv x=s_k,s_k+1, ,s_n=p sunt cele mai scurte intre s=s₀ si x=s_k respectiv x=s_k si p=s_n si, in plus, trec prin noduri intermediare cu indici mai mici decat x. Atunci, putem considera:

Drum^k(i,j)=Drum^k-1 (i,x)+Drum^k-1(x,j)

unde Drum^k(i,j) este drumul cel mai scurt intre i si j ce trece prin noduri cu indici mai mici decat k.

Verificarea principiului optimalitatii, sub oricare dintre formele sale, ne poate conduce la solutia optima generand si retinand, in mod progresiv, optimele partiale, pana cand ajungem la optimul global.

Practic, aplicarea metodei de programare dinamica presupune parcurgerea urmatorilor pasi:

se verifica daca (si sub ce forma) este satisfacut principiul optimalitatii;

plecand de la forma principiului optimalitatii se deduc relatiile recurente intre optimul global si cele partiale;

se implementeaza relatiile recurente obtinute anterior.

Timpul de calcul

Esential pentru metoda programarii dinamice este faptul ca solutiile bazate pe recursivitate conduc, in marea parte a cazurilor, la recursivitate in cascada, prin recalcularea repetata a unor stari ale problemei, ceea ce face ca timpul de calcul sa sporeasca semnificativ. Pentru a evita acest neajuns se va utiliza metoda tabelarii: starile intermediare ale problemei (obtinute in urma aplicarii unui sir optim partial de decizii) vor fi retinute in masive de date si astfel nu se vor calcula decat componentele neinitializate. In acest context, metoda programarii dinamice va duce, in cea mai mare parte a cazurilor, la timpi de calcul de ordin polinomial.

I.1.1         Exemplu - Inmultirea optima a unui sir de matrice

Fie A(m,n) si B(n,p) doua matrice bidimensionale de dimensiuni m*n, respectiv n*p. Inmultirea lor are ca rezultat o a treia matrice de dimensiuni m*p: C(m,p), unde fiecare element c_ij se poate obtine cu ajutorul formulei:

Utilizand formula de mai sus, inmultirea dintre A si B va necesita un numar de m*n*p inmultiri intre elemente ale celor doua matrice.

Sa presupunem ca dispunem de un sir de matrice A₁, A₂, ,A_n, fiecare matrice A_i are dimensiunile (l_i, l_i+1), astfel ca numarul de coloane al fiecarei matrice sa fie egal cu numarul de linii ale matricei urmatoare. Astfel, produsul sirului de matrice este definit: C= A₁*A₂* *A_n.

Daca am dispune de un operator supraincarcat pentru inmultirea matricelor, acesta va efectua inmultirile de la stanga la dreapta, astfel:

C=((.((A₁*A₂)*A₃)**A_n)

ceea ce, dupa cum vom observa mai jos, poate sa nu fie optim din punctul de vedere al numarului de operatii efectuate, intrucat ordinea de grupare (asociere) a matricelor poate influenta semnificativ numarul total de inmultiri efectuate. Pentru ca inmultirea matricelor este asociativa, matricea-rezultat va fi aceeasi, indiferent de ordinea de inmultire aleasa. Problema care se pune in scopul inmultirii optime de matrice este stabilirea ordinii de inmultire, fara a incerca toate posibilitatile.

Sa consideram un exemplu extrem de simplu: presupunem ca avem 4 matrice de dimensiuni (100,1), (1,100), (100,1), (1,100). Asadar, n=4 si l=(100,1,100,1,100). Iata trei modalitati de asociere:

(((A₁*A₂)*A₃)*A₄), asocierea implicita de la stanga la dreapta. Ea presupune efectuarea urmatoarelor inmultiri:

(A₁*A₂), care necesita 100*1*100=10000 inmultiri si rezulta o matrice C₁ de dimensiuni (100,100)

C₁*A₃, matricea C₁ de dimensiuni (100,100) obtinuta la pasul anterior este inmultita cu A₃, rezultand matricea C₂ de dimensiuni (100, 1). Au fost efectuate 100*100*1=10000 de inmultiri.

C₂*A₄, fiind ultima inmultire de matrice necesita 100*1*100=10000 de operatii.

In total, asocierea stanga-dreapta necesita, in exemplul considerat, 30.000 de inmultiri.

Fig. V . Numarul de inmultiri efectuate prin asocierea stanga-dreapta

((A₁*A₂)*(A₃*A₄)), necesita, in urma unui rationament similar celui de mai sus, 100*1*100 + 100*1*100 + 100*100*100 = 10000 + 10000 + 1000000 = 1.020.000 de operatii

Fig. V . Numarul de inmultiri efectuate prin asocierea matricelor extreme

((A₁*(A₂*A₃))*A₄), necesita 1*100*1 + 100*1*1 + 100*1*100 = 100 + 100 + 10000 = 10.200 de operatii

Fig. V . Numar de inmultiri

Se observa asadar ca dintre cele trei modalitati ultima asociere presupune cel mai mic numar de inmultiri.

Pentru rezolvarea problemei vom utiliza metoda programarii dinamice introducand o matrice de costuri, unde fiecare element cost[i,j] cu 1 i j n reprezinta numarul minim de operatii necesare pentru a efectua produsul A_i*A_i+1* *A_j.

Daca A_i*A_i+1* *A_j este un produs optim, atunci exista un i k<j astfel ca secventele A_i*A_i+1* *A_k si A_k+1*A_k+2* *A_j sa fie optimale. In urma inmultirii secventei A_i*A_i+1* *A_k , respectiv A_k+1*A_k+2* *A_j se obtin doua matrice de dimensiuni (l_i, l_k+1), respectiv (l_k+1, l_j+1), care inmultite intre ele necesita l_i* l_k+1*l_j+1 operatii. Dintre toate valorile posibile ale lui k intre i si j se alege aceea care minimizeaza totalul comparatiilor. Asadar, in mod natural, deducem urmatoarea formula, care ne arata ca se verifica principiul optimalitatii:

cost[i,j]=min_i<=k<j, cand j>i.

Conditia initiala este evidenta: cost[i,i]=0, pentru orice i=1..n.

Am obtinut astfel o definitie recursiva a elementelor matricei cost. Este evident ca numarul minim de inmultiri pentru a obtine produsul de matrice A₁, A₂, ,A_n este dat de valoarea elementului cost[1,n].

Mai mult, daca la fiecare evaluare a elementului cost[i,j], pentru j>i, retinem valoarea lui k pentru care a fost realizat minimul, atunci vom putea deduce asocierea matricelor. Pentru ca numai jumatate din matricea de costuri este utilizata, vom incarca valoarea k care minimizeaza numarul de operatii necesar inmultirii A_i*A_i+1* *A_j in elementul cost[j,i].

Pentru exemplul considerat anterior, unde n=4 si l=(100,1,100,1,100), matricea de costuri este:

Tabel V . Matricea de costuri

unde elementele cost[i,j], cu i j, au fost calculate in ordinea crescatoare a diferentei j-i:

• cost[i,i] = 0, orice i=1..n
• cost[1,2] = 0+0+10.000 = 10.000 , k=1, deci cost[2,1]=1
• cost[2,3] = 0+0+100 = 100 , k=2, deci cost[3,2]=2
• cost[3,4] = 0+0+10.000 = 10.000 , k=3, deci cost[4,3]=3
• cost[1,3] = min = min =200 , k=1, deci cost[3,1]=1
• cost[2,4] = min=min=200 , k=3, deci cost[4,2]=3
• cost[1,4] = min =    min=10.200 , k=1 sau 3, deci cost[4,1]=1sau 3

Un algoritm iterativ de populare a matricei cost este:

Procedeul poate fi imaginat astfel - vom construi un arbore binar cu proprietatile:

radacina arborelui este etichetata (1,n);

fiecare nod etichetat (i,j), cu i<j, are doi fii etichetati (i,k) si (k+1,j), unde k este valoarea retinuta in cost[j,i], care a realizat minimul pentru secventa A_i*A_i+1* *A_j;

nodurile etichetate (i,i) sunt noduri terminale ale arborelui.

Fig. V . Reprezentarea unei asocieri optime ca arbore binar

Parcurgerea in postordine (SDR) a nodurilor neterminale va genera modul de grupare a matricelor: un nod etichetat (i,j) va semnifica gruparea minimala a secventei A_i*A_i+1* *A_j.

In exemplul de mai sus, parcurgerea SDR a nodurilor neterminale va genera: [2,3], [2,4],[1,4], cu semnificatia: o pereche de paranteze incepe inainte de A2 si se termina dupa A3, alta pereche incepe inainte de A2 si se termina dupa A4 si ultima pereche de paranteze incepe inainte de A1 si se termina dupa A4, altfel spus:

(A₁*((A₂*A₃)*A4))

Se observa ca valoarea minima elementului cost[1,4] putea fi obtinuta si pentru k=3, aceasta ar fi dus la generarea unei alte grupari optime, corespunzatoare arborelui:

Fig. V . Reprezentarea unei asocieri optime ca arbore binar

si anume: ((A1*(A2*A3))*A4), care necesita acelasi numar minim de inmultiri, 10.200.

I.1.2         Aplicatii

I.1.2.1   Problema inmultirii optime a unui sir de matrice

Se cere generarea unei modalitati de asociere a unui sir de matrici A₁, A₂, ,A_n, fiecare matrice A_i avand dimensiunile (l_i, l_i+1), in vederea obtinerii produsului lor cu un numar minim de inmultiri de elemente.

Indicatie: Se va utiliza functia cost definita mai sus. Aceasta poate fi implementata fie iterativ, determinandu-i valorile cost[i,j] in ordinea crescatoare a diferentei j-i, fie recursiv, evitand insa recalcularea valorilor sale. Am ales varianta recursiva datorita simplitatii sale.

Inmultirea optima a unui sir de matrice

#include<iostream.h>

int n,//numar matrice de inmultit

*l,//vector dimensiuni

**cost;//matrice costuri

int COST(int i,int j)

}

return cost[i][j]=cost_min;

void SDR(int i, int j)

int main()

cout<<'Nr. minim de inmultiri: '<<COST(0,n-1)<<endl;

cout<<'Matricea de costuri:';

for(i=0;i<n;i++)

cout<<endl<<'Perechile de paranteze: '; SDR(0,n-1);

delete []l;

for(i=0;i<n;i++)

delete[]cost[i];

delete []cost;

return 0;

I.1.2.2   Algoritmul Roy-Warshall

Metoda programarii dinamice are multe aplicatii in prelucrarea grafurilor.

Se considera un graf orientat, definit prin matricea de adiacente A, se cere sa se determine matricea existentei drumurilor intre noduri.

Indicatie: Matricea B a existentei drumurilor va avea forma:

Daca exista drum de la i la j, atunci pentru orice nod k al drumului, va exista drum de la i la k si de la k la j. Asadar, principiul optimalitatii este indeplinit in forma generala. Pentru a scrie relatiile de recurenta, trebuie stabilita mai intai o modalitate de alegere a nodului intermediar k: fie acesta nodul cu indicele cel mai mare din drumul ce leaga i de j. Prin urmare, drumurile [i,k], respectiv [k,j] trec numai prin noduri de indici mai mici decat k.

Ideea algoritmului Roy-Warshall este de a construi recurent un sir de matrice ale drumurilor astfel:

Evident, matricea drumurilor ceruta este B_n.

Exemplu:

Fie graful orientat:

Fig. V . Retea drumuri

definit de matricea de adiacente:

Tabel V . Matricea de adiacente

Vom avea succesiv matricele:

Tabel V . Matricele drumurilor

De exemplu, elementul B₁[3,3] a fost evaluat astfel:

B₁[3,3]= B₀[3,3] or (B₀[3,1] and B₀[1,3])=0 or 1 and 1= 0 or 1 = 1

Observand faptul ca:

,

deducem ca in implementarea recursiva a algoritmului putem utiliza o singura matrice B.

Solutie

Algoritmul Roy-Warshall - determinarea matricei existentei drumurilor

#include<iostream.h>

void AfisMat(int **A, int n)

void RoyWarshall(int **A, int n, int **B)

main()

RoyWarshall(A,n,B);

cout<<'Matricea drumurilor:'<<endl;

AfisMat(B,n);

delete[]A;

delete[]B;

return 0;

Algoritmul are un timp de calcul de ordin O(n³), cauzat de cele 3 instructiuni if imbricate.

I.1.2.3   Algoritmul Roy-Floyd

Se considera un graf orientat ponderat definit prin matricea costurilor A,. Se cere sa se determine matricea costurilor drumurilor minime intre oricare doua noduri.

Indicatie:

Problema este similara celei anterioare. Daca [i,j] este un drum de lungime minima de la i la j, atunci oricare ar fi k, apartinand acestui drum, drumurile [i,k] si [k,j] sunt de lungime minima (altfel, daca cel putin unul dintre ele nu ar fi, atunci nici drumul [i,j] nu este minim). Cum se verifica principiul optimalitatii, vom utiliza metoda programarii dinamice, alegand acel nod k de indice maxim, ca si la problema precedenta. Asadar drumurile [i,k] si [k,j] sunt de lungime minima si trec prin noduri cel mult egale cu k-1 (este evident ca nodul k nu poate exista de doua ori in drum, acesta avand cost minim, iar costurile, prin definitie, sunt valori strict pozitive). Vom considera ca daca nu exista arc de la i la j, atunci costul corespunzator in matricea costurilor este o valoare mare (infinit). Vom defini recurent sirul de matrice:

Evident, B_n este matricea cautata.

In implementarea recursiva a algoritmului vom utiliza o singura matrice B, deoarece avem ca:

,

Solutie

Algoritmul Roy-Floyd -Determinarea matricei costurilor minime ale drumurilor

#include<iostream.h>

void AfisMat(int **A, int n)

void Cost(int **A, int n, int **B)

main()

Cost(A,n,B);

cout<<'Matricea drumurilor:'<<endl;

AfisMat(B,n);

delete[]A;

delete[]B;

return 0;

Algoritmul are un timp de calcul de ordin O(n³), cauzat de cele 3 instructiuni if imbricate.