Metoda "programarii dinamice"

Metoda programarii dinamice, asa cum ii arata si numele, permite determinarea unei solutii pentru o problema data, in urma unui sir de decizii si prelucrari ce se conditioneaza reciproc, realizand o "dinamica' continua a procesului de cautare a solutiei.

Ordinul de complexitate al unui astfel de algoritm este conditionat de modul de organizare a datelor initiale, a rezultatelor intermediare si de modalitatea de regasire a rezultatelor intermediare, obtinute anterior momentului unei noi prelucrari a acestora.

Problema Notiunea de algoritm, asa cum a fost prezentata, presupune ca entitati distincte, existenta unui set de date de intrare si a unei metode de transformare succesiva a acestora, in vederea obtinerii unui set coerent de date de iesire ca rezultat al tuturor prelucrarilor. Abordarea celor trei elemente ca un sistem presupune existenta unor interconditionari intre acestea. Ca metoda de elaborare a algoritmilor de rezolvare a unor clase de probleme, programarea dinamica presupune identificarea acestor corelatii, privind problema initiala ca un sistem de miniprobleme care se conditioneaza reciproc.

Solutie. Pentru o problema data, fie S₀ starea sistemului format din datele de intrare si de lucru (intermediare), precum si din corelatiile care exista intre acestea. O decizie d₁ de prelucrare a datelor orientata in directia obtinerii unei solutii optime pentru problema produce o "prelucrare" a starii S₀ determinand transformarea acesteia intr-o noua stare S₁. Suntem in acest moment pusi in fata uneia sau mai multor probleme similare cu cea initiala si care - printr-o noua decizie (comuna) de prelucrare - conduc la o noua stare. Schimbarea starii sistemului va continua pana la obtinerea unei stari finale din care se deduce o solutie optima a problemei initiale.

In general, fiecare noua decizie de transformare a starii sistemului depinde de deciziile luate anterior (acestea au generat starea curenta a sistemului) si nu este unic determinata ca in cazul metodei greedy, de exemplu.

Fie d₁, d₂, , d_n-1, d_n o secventa de decizii optime care determina trecerea succesiva a sistemului din starea initiala S₀ in starea finala S_n, prin intermediul starilor S₁, S₂, , S_n-1

O modalitate naturala de abordare a problemei consta din luarea succesiva de decizii optime de prelucrare in ordinea d₁, d₂, , d_i-1, pornind de la starea initiala S₀. Decizia urmatoare d_i, depinde de sirul de decizii optime deja luate d₁, d₂, , d_i-1. Spunem in acest caz ca se aplica metoda spre inapoi (sfarsitul sirului de decizii).

Daca se poate stabili starea sistemului S_n din care s-ar deduce solutia optima a problemei, este de dorit sa se determine o decizie d_n precum si o stare S_n-1 din care sa se ajunga in starea S_n in urma aplicarii deciziei d_n. Intuitiv spus, se determina inversa unei decizi' si starea sistemului anterioara luarii acestei decizii. Fie secventa de decizii optime d_i+1, d_i+2, , d_n care duc sistemul din starea S_i in starea finala S_n O noua decizie d_i care sa duca sistemul din starea S_i-1 in starea S_i va depinde de sirul de decizii d_i+1, d_i+2, , d_n. Spunem in acest caz ca se aplica metoda spre inainte (inceputul sirului de decizii).

A treia modalitate de abordare sugereaza determinarea unei stari intermediare, S_i , si a doua decizii optime d_i si d_i+1, avand doua subsiruri optime de decizii:

d_i+2, d_i+3, , d_n care duc sistemul din starea S_i+1 in starea finala S_n prin intermediul starilor S_i+1, S_i+2, , S_n-1

d₁, d₂, , d_i-1, sir de decizii optime care determina trecerea sistemului din starea initiala S₀ in starea S_i-1, prin intermediul starilor S₁, S₂, , S_n-2. Spunem in acest caz ca se aplica metoda mixta (exploziva).

Cele trei modalitati de abordare au la baza principiul optimalitatii. Daca d₁, d₂, , d_n este un sir optim de decizii care determina trecerea sistemului din starea initiala S₀ in starea finala S_n, atunci sunt adevarate urmatoarele afirmatii:

- d_i+1, d_i+2, , d_n este un sir optim de decizii care determina trecerea sistemului din starea S_i in starea finala S_n i, 0 i n-1

- d₁, d₂, , d_i este un sir optim de decizii care determina trecerea sistemului din starea initiala S₀ in starea S_i i, 1 i n

- d_i+1, d_i+2, , d_n si d₁, d₂, , d_i sunt siruri optime de decizii care determina trecerea sistemului din starea S_i in starea finala S_n si respectiv din starea initiala S₀ in starea S_i i, 1 i n

Principiul optimalitatii sugereaza stabilirea unor relatii de recurenta.

In concluzie, rezolvarea unei probleme prin metoda programarii dinamice presupune identificarea unor caracteristici ale problemei care o fac rezolvabila prin aceasta metoda:

- problema se poate descompune in subprobleme de acelasi tip cu aceasta;

- subproblemele nu sunt distincte, se interconditioneaza reciproc (altfel s-ar putea aplica tehnica 'divide et impera', mult mai eficienta din punct de vedere al consumului de memorie);

- necesitatea satisfacerii principiului optimalitatii, care implica stabilirea relatiei de recurenta prin care se exprima interconditionarea subproblemelor.

In cele ce urmeaza, vom prezenta un exemplu de abordare a unor probleme prin metoda programarii dinamice. Sunt punctate caracteristicele importante ale metodei, chiar daca problema aleasa poate sa fie considerata drept necaracteristica.

Problema. Sa se determine termenul de rang k din sirul lui Fibonacci, pentru un numar natural k dat.

Intrare k, de la tastatura.

Iesire: pe ecran, de forma: Termenul de rang k din sirul lui Fibonacci este v

Solutie (metoda) In sirul lui Fibonacci, primii doi termeni sunt a₀ = 1 si a₁ = 1. Relatia de recurenta a_k = a_k-1 + a_k-2 , k>2 arata ca un termen se obtine ca suma ultimilor doi termeni anteriori lui.

Vom folosi metoda "inapoi" plecand de la starea initiala u = 1, v = 1 (primii doi termeni), care reprezinta si starea din care se deduce solutia problemei pentru k = 1

Decizia de trecere la o noua stare determina urmatoarele prelucrari:

- aplicarea relatiei de recurenta (calculul sumei s = u + v), care respecta principiul optimalittaii;

- obtinerea noii stari prin atribuirea valorilor u = v si v = s

Se obtine starea u = 1, v = 2

Aceasta este starea nou obtinuta (succesoare).

Sunt respectate caracteristicile problemelor care sunt rezolvabile prin metoda programarii dinamice:

- solutia unei probleme este obtinuta din solutia problemei rezolvate anterior (se determina termenul de rang k din termenii de rang k-1 si k-2

este satisfacut principiul optimalitatii (o solutie optima pentru problema anterioara conduce la solutia optima a problemei curente).

program termen_sir_Fibonacci;

var i,k : byte;

u,v,s : word;

begin

write ('k ');

readln (k);

u := 1;

v := 1;

for i := 2 to k do

begin

s := u + v;

u := v;

v := s;

end;

writeln (' Termenul de rang ',k,' este',v);

readln;

end

Intrare:N = 10

Iesire:Termenul de rang 10 este 89.