METODE DE ELABORARE A ALGORITMILOR.PROGRAMARE DINAMICA.

Metode de elaborare a algoritmilor.Programare dinamica.

Metoda Programarii dinamice se poate considera ca o imbunatatire a tehnicii Greedy. In cazul metodei Greedy, alegerea unui element se face pe baza unui criteriu de admisibilitate, insa la Programarea dinamica, acest criteriu este cel al optimalitatii; folosind-se de un criteriu mai puternic, rezultatul final oferit de metoda programarii dinamice este intotdeauna optimul global.

Ca si metoda Divide et impera, programarea dinamica presupune impartirea problemei in subprobleme, rezolvarea si combinarea solutiilor acestora pentru a obtine rezultatul final. In situatia in care subproblemele obtinute prin descompunere contin subprobleme comune, este preferabila aplicarea metodei Programarii dinamice.

O particularitate a metodei consta in construirea si utilizarea unor tabele cu informatii. Tabelele sunt construite prin completarea unui element folosind elemente completate anterior. Denumirea metodei provine din maniera de completare dinamica a tabelei de informatii intermediare.

Metoda programarii dinamice se caracterizeaza prin principiile fundamentale:

sunt evitate calculele repetate ale aceluiasi subcaz, rezultatele intermediare obtinute fiind memorate

solutia este construita in maniera bottom-up (de jos in sus): pornind de la solutiile celor mai mici subprobleme, prin combinarea acestora se va ajunge treptat la solutia globala

problema abordata respecta principiul optimalitatii

Programarea dinamica este o metoda de rezolvare a problemelor de optimizare pentru care solutia este rezultatul unui sir de decizii optime. Problema de optimizare rezolvabila prin metoda programarii dinamice este formulata astfel:

Fie un sistem care se poate afla intr-una din starile:

S₀, S₁, S₂ , ., S_n-1, S_n

si fie sirul de decizii

D₁, D₂ , ., D_n-1, D_n

prin care sistemul este trecut prin starile date:

Problema verifica unul dintre principiile optimalitatii:

Varianta 1: Daca sirul de decizii D₁, D₂ , ., D_n-1, D_n duce sistemul din starea initiala S₀ in starea finala S_n in mod optim, atunci:

, secventa de decizii D_k , ., D_n-1, D_n duce sistemul din starea S_k-1 in starea finala S_n in mod optim.

Varianta 2: Daca sirul de decizii D₁, D₂ , ., D_n-1, D_n duce sistemul din starea initiala S₀ in starea finala S_n in mod optim, atunci:

, secventa de decizii D₁ , ., D_k-1, D_k duce sistemul din starea initiala S₀ in starea S_k in mod optim.

In functie de varianta principiului optimalitatii identificata din analiza problemei, metoda de abordare a poate fi:

Metoda inainte - aplicata in cazul verificarii principiului optimalitatii in forma 1.

Metoda inapoi - aplicata in cazul verificarii principiului optimalitatii in forma 2.

Esenta celor doua variante (inainte sau inapoi) este aceiasi si consta in identificarea si rezolvarea relatiilor de recurenta referitoare la criteriul de optimizat sau la valoarea ce se calculeaza.

Metoda inainte opereaza in urmatoarele 4 faze:

prin relatiile de recurenta se vor calcula optimele corespunzatoare starilor indepartate de starea finala in functie de optimele corespunzatoare starilor apropiate de starea finala (practic in aceasta faza se completeaza tabela de informatii intermediare)

se determina deciziile care leaga optimele determinate in faza anterioara

se afla optimul total

se determina solutia problemei reprezentata de un sir de decizii constituit prin compunerea deciziilor de la etapa 2, in mod directe, de la inceput spre sfarsit (inainte)

Metoda inapoi este duala metodei descrise anterior si opereaza in urmatoarele 4 faze:

prin relatiile de recurenta se vor calcula optimele corespunzatoare starilor apropiate de starea finala in functie de optimele corespunzatoare starilor departate de starea finala

se determina deciziile care leaga optimele determinate in faza anterioara

se afla optimul total

se determina solutia problemei reprezentata de un sir de decizii constituit prin compunerea deciziilor de la etapa 2, in mod invers, de la sfarsit spre inceput (inapoi)

Desi pare o metoda generala de rezolvare a problemelor de optim, aplicabilitatea programarii dinamice este restransa doar la acele probleme pentru care se poate demonstra principiul optimalitatii.

Problema 1 Subsir crescator de lungime maxima (metoda inainte)

Se da o multime (sir) neordonata de elemente.

Se cere determinarea lui B, , sir ordonat crescator, de lungime maxima.

Exemplu: in sirul 7 1 4 2 5 3, cel mai lung subsir crescator este 1,2,3

Rezolvarea naiva a acestei probleme ar aceea prin care se vor determina toate subsirurile crescatoare urmand ca ulterior sa se extraga acela care are lungime maxima. Rezolvarea aceasta este corecta, insa neeficienta prin necesitatea de a construi si retine toate subsirurile lui sirului dat.

O solutie ingenioasa are fi sa se calculeze si sa se retina intr-o tabela doar lungimile tuturor subsirurilor crescatoare, fara a le genera si pe acestea.

In exemplul anterior, subsirurile crescatoare si lungimile acestora sunt:

Se poate observa ca daca subsirul 3 are lungime 1, subsirul care il contine are lungimea mai mare cu 1, respectiv 2 (1+1) si subsirul maximal 1 2 3 are lungime 3 (2+1).

Astfel: Daca subsirul 1 2 3 este subsirul optimal crescator de lungime maxima (3), care incepe cu 1, atunci:

3 este subsirul optimal crescator de lungime maxima (2) care incepe cu 2 si

este subsirul optimal crescator de lungime maxima (1) care incepe cu 3

Generalizand, daca este subsirul optimal crescator de lungime n care incepe cu : atunci:

- este subsirul optimal optimal de lungime n-1 care incepe cu i₂

- este optimal de lungime n-2 care incepe cu i₃

- ...

- este subsirul optimal de lungime maxima care incepe cu i_k,

Prin reformularea observatiilor anterioare se identifica principiul optimalitatii in varianta 1, fapt pentru care se va aplica metoda inainte:

Etapa_1&2: se vor calcula pe baza relatiilor de recurenta, pentru fiecare element al sirului initial lungimea celui mai mare subsir crescator care se poate forma incepand de la el.

Notam L(k) lungimea celui mai mare subsir crescator care se poate forma incepand elementul de pe pozitia k din sirul dat. Relatia de recurenta este urmatoarea:

L(k):=} si k }

Algoritm Determinare_Lungimi este:

L(n)=1

Pentru k=n-1 la 1 cu pas -1

L(k)=1

Cauta i>k astfel incat si

Daca s-a gasit (i) atunci

L(k)=L(i)+1

SfDaca

SfPentru

SfAlgoritm

Etapa3: Se determina maximul din tabela lungimilor L. Fie acesta L(imax). In acest caz:

L(imax) - reprezinta lungimea subsirului crescator de lungime maxima (lungimea solutiei)

imax - reprezinta indicele din sirul initial de la care incepe subsirul solutie

Etapa4: Se determina solutia problemei (subsirul crescator de lungime maxima), prin construire, pornind de la elementul de pe pozitia imax pana la elementul de pe pozitia n, retinandu-se doar elementele care verifica relatia de ordine.

Problema 2: Problema Robotului (metoda inapoi)

Se da o tabla impartita in m linii si n coloane:

Fiecare casuta a tablei contine obiecte de valori diferite (numere naturale): .

Un robot situat in casuta de start va traversa tabla pentru a ajunge la casuta finala realizand doar miscarile posibile:

la dreapta cu o casuta: ()

in jos cu o casuta: ()

si colecteaza obiectele din casutele traversate.

Sa se determine secventa de miscari (drumul) a robotului astfel incat suma valorilor colectate la iesire sa fie maxima.

Exemplu

Pentru urmatorul caz:

Solutia imediata este parcurgerea casutelor: (1,1)-(2,1)-(2,2)-(3,2)-(4,2)-(4,3)-(4,4), robotul colecteaza obiecte de valoare totala: 18 reprezentand suma maxima a sumelor colectate prin parcurgerea oricaror drumuri de la casuta initiala la casuta finala.

Se observa ca suma maxima cu care ajunge robotul in casuta finala poate fi obtinuta fie prin mutarea anterioara de pe coloana din stanga (n-1), fie prin mutarea anterioara din celula de pe linia (m-1). Astfel, daca suma finala a valorilor este maxima, atunci prin scaderea valorii comune continuta in , inseamna ca si drumurile partiale efectuate pana in celula sau sunt de suma maxima partiala.

Generalizand:

Daca in celula robotul a ajuns cu transport maxim de la celula initiala , efectuand ultima mutare dreapta (robotul ajunge in celula din celula ) atunci in celula robotul a ajuns cu suma maxima posibila de la la .

Daca in celula robotul a ajuns cu transport maxim de la celula initiala , efectuand ultima mutare jos (robotul ajunge in celula din celula ) atunci in celula robotul a ajuns cu suma maxima posibila de la la .

Observatie: Ultima formulare este chiar Principiul optimalitatii exprimat in varianta 2:

Daca secventa de celule parcurse de la celula : (1,1) la celula (m,n) este de transport maxim: , .,,,, . ,

Atunci , secventa de celule parcurse de la (1,1) la (,) este de transport maxim: , .,,,

Din observatiile anterioare, se poate deduce o relatie de recurenta prin care pot fi determinate sumele maxime cu care robotul poate ajunge in oricare celula a tablei A:

, si

Pe baza relatiei de recurenta se va construi o tabela suplimentara care retine valorile sumelor maxime pe care le poate colecta robotul pana in fiecare celula a tablei initiale:

Algoritm DeterminareSumeMaxime este:

S(0,1):=0

S(1,0):=0

Pentru i de la 1 la m

Pentru j de la 1 la n

Daca S(i-1,j)> S(i,j-1) atunci

S(i,j):= S(i-1,j)+ a_i,j

Altfel

S(i,j):= S(i,j-1)+ a_i,j

SfDaca

SfPentru

SfPentru

SfAlgoritm

Se constata ca ultima valoare determinata, reprezinta chiar suma maxima a drumului complet al robotului, iar solutia problemei-vectorul format din casutele (i,j) traversate cu transport maxim, poate fi determinata printr-o parcurgerea inversa a matricei S :

Algoritm RefacereDrum este:

Vector(1) (m,n) // Retine casuta finala (m,n)

Fie i=m, j=n, k=2

Cattimp ((i,j)≠(1,1))

Daca > atunci

Vector(k) (i-1,j) //Retine casuta (i-1,j),

i=i-1

k=k+1

Altfel

Vector(k) (i,j-1) //Retine casuta (i,j-1)

j=j-1

k=k+1

SfDaca

SfCattimp

//Vectorul de casute parcurs invers este solutia problemei.

Pentru i de la k la 1 cu pas -1

Tipareste Vector(i)

SfPentru

SfAlgoritm

Observatie: Tehnica descrisa pentru rezolvarea problemei robotului este Programarea dinamica, varianta metodei inapoi.

Probleme:

1. Scrieti un program de rezolvare a problemei robotului.
2. Scrieti programul de rezolvare a problemei 1: Subsir crescator de lungime maxima.
3. Scrieti un program care determina cel mai lung subsir comun al doua siruri date.

BIBLIOGRAFIE:

1. Liviu Negrescu, Limbajele C si C++ pentru incepatori Vol. I (p.1 si 2) - Limbajul C , Editura Albastra, Cluj-Napoca,    2002.
2. Brian Kernighan, Dennis Ritchie, The C Programming Language, Second Edition, Prentice Hall, 1988.
3. Bazil Parv, Alexandru Vancea, Fundamentele limbajelor de programare, Editura Albastra, Cluj Napoca, 1996.
4. Knuth, Donald E., Arta programarii calculatoarelor: Algoritmi fundamentali. vol.1 , Editura Teora, Bucuresti, 1999.
5. Doina Logofatu, Algoritmi fundamentali in C++. Aplicatii, Editura Polirom, Iasi, 2007.
6. Frentiu M, Parv B., Elaborarea programelor. Metode si tehnici moderne, Editura PROMEDIA, Cluj-Napoca, 1994.
7. Petrovici V., Goicea F., Programare in limbajul C, Editura Tehnica, Bucuresti, 1993.