Programarea dinamica

Descrierea metodei

Se aplica atunci cand solutia unei probleme poate fi privita ca rezultat al unei secvente de decizii.

Exemple:

a) Problema rucsacului -- decizia 1 - x_i1 ponderea obiectului i₁

-- decizia 2 - x_i2 ponderea obiectului i_{2 . .}

b) Interclasarea optimala    -- decizia 1 - prima pereche

-- decizia 2 - a doua pereche . .

c) Drumuri minime de la i la celelalte noduri

-- decizia 1 - in S se adauga i

-- decizia 2 - in S se adauga nodul de distanta minima . .

Nu toate problemele permit ca la fiecare pas sa se determine decizia care conduce la solutia optimala.

Ex. drum minim de la i la j

initial : P =

decizia 1 : care din vecinii lui i vor fi pe drumul minim ?

O solutie este a se incerca toate variantele posibile de decizie.

Programarea dinamica reduce numarul de incercari eliminand o serie de secvente care nu pot fi optimale si aceasta apeland la principiul optimalitatii:

' O secventa optimala de decizii are proprietatea ca pornind de la o stare initiala si considerand prima decizie d₁ , secventa de decizii ramase d₂, , d_n trebuie sa fie optimala relativ la starea rezultata din prima decizie.'

Problemele care indeplinesc acest principiu sunt susceptibile de a fi rezolvate prin programare dinamica.

Exemple :

Drum minim de la i la j , doua noduri intr-un graf.

Drumul minim de la i la j este de forma ( i, i₁, i₂, , i_m, j ). Presupunem ca s-a luat decizia ca i₁ este primul nod dupa i in solutia optimala. Secventa ( i₁, i₂, , i_m, j ) trebuie sa fie drum minim de la i₁ la j , altfel, daca (i₁, r₁, r₂, , r_l, j) este drumul minim de la i₁ la j atunci (i, i₁, r₁, r₂, , r_l, j ) este drumul minim de la i la j si nu ( i, i₁, i₂, , i_m, j ).

Problema rucsacului [0,1]

Problema rucsacului 0/1 se enunta in mod identic cu problema generala a rucsacului cu observatia ca obiectele sint indivizibile adica apare restrictia suplimentara asupra ponderilor x_i care trebuie sa fie 0 sau 1.

Formularea problemei:

se cunosc obiectele: i₁ , i₂ , . . . .i_n

obiectele au greutatile: w₁ , w₂ , . . . .w_n

obiectele au valorile (profiturile) p₁ , p₂ , . . . .p_n

se considera o capacitate M.

O alegere de obiecte este un vector X=( x₁ , x₂ , . . . .x_n) unde x_i=1 semnifica faptul ca obiectul i a fost ales iar x_i=0 semnifica faptul ca respectivul obiect nu a fost ales.

Problema consta in determinarea acelei alegeri care nu depaseste capacitatea dar care maximizeaza profitul, adica:

-maxim iar

Problema se noteaza cu : knap(1,n,M). Presupunem ca exista o secventa X=( x₁ , x₂ , . . . .x_n) reprezentind o alegere optimala.

Exista urmatoarele doua variante:

x₁=0 si atunci secventa ( x₂ , x₃ , . . . .x_n) este optimala pentru problema knap(2,n,M).

x₁ =1 si atunci secventa ( x₂ , x₃ , . . . .x_n) este optimala pentru problema knap(2,n,M-w₁).

Se observa ca si in acest caz principiul optimalitatii se respecta

Fie s₀ starea initiala a problemei. Presupunem ca sint necesare n decizii d₁ , d₂ , . . . .d_n. Prima decizie poate lua una din valorile multimii D= . Daca decizia d₁ ia valoarea r_i fie s_i starea problemei dupa aceasta decizie, si fie R_i secventa optimala corespunzatoare subproblemei corespunzatoare starii s_i.. Daca este indeplinit principiul optimalitatii secventa optima globala va fi cea mai buna din secventele: r₁R₁, r₂R₂ , . .., r_kR_k.

Exemple:

Drum minim

Se cauta intr-un graf drumul minim de la nodul i la nodul j. Fie E_i= multimea succesorilor nodului i si fie drumurile minime corespunzatoare de la fiecare din acesti succesori la j, anume R_k= drumul minim de la i_k la j, (k=1, . ,s). Atunci drumul minim de la nodul i la nodul j va fi cel mai mic dintre drumurile (i R_k ), k=1, . ,s.

Problema rucsacului 0/1

Fie problema knap(1,n,.M) si fie p (M) valoarea profitului maxim pentru aceasta problema. In general pentru o problema knap(j+1,n,Y) valoarea profitului maxim se noteaza cu p_j(Y). Deoarece x₁ ia valori din multimea de decizii D₁=, avem:

p (M)= max ( * )

Daca pentru o problema data este valabil principiul optimalitatii in starea initiala, atunci se poate aplica acest principiu si la urmatoarele stari intermediare

Exemple:

Drum minim

Daca (i, i₁, i₂, . ..i_m, j) este drumul minim de la nodul i la nodul j si i_k este un nod intermediar, atunci secventa ( i, i_1, ,i₂, . i_k) este drum minim de la nodul i la nodul i_k iar secventa (i_k,i_k+1, . .j) este drum minim de la nodul i_k la nodul j.

Problema rucsacului 0/1

Fie (x₁,x_2, . . x_n) o secventa alegere optimala pentru problema knap(1,n,M). Atunci pentru orice valoare j ( j=1,n) :

(x₁, x₂, . ..x_j) este solutie optimala pentru problema knap(1,j, )

(x_j+1,x_j+2, . x_n) este solutie optimala pentru problema knap(j+1, n, M-)

Relatia anterioara ( * ) se generalizeaza la

p_j(Y) = max

relatia (**) este o recurenta care se poate calcula stiind ca p_n(Y)=0 pentru orice Y numar real.

Exemplele anterioare evidentiaza recurente de tip "forward" ( in fata). Se pot defini aceste recurente si in mod "backward".

Exemple

Drum minim

Daca (i, i₁, i₂, . ..i_m, j) este drumul minim de la nodul i la nodul j, fie E_j'=, |E|=p multimea predecesorilor nodului j. Pentru fiecare predecesor k fie R_k drumul minim de la nodul i la nodul k. Evident, drumul minim general va fi cel mai scurt drum din drumurile de forma (R_k j) pentru k=1, . ,p

Probelema rucsacului (0/1)

Daca se noteaza cu f_i(x) valoarea optima a problemei knap(1,i,x) se obtin recurentele:

f_i (x)= max i=1,2, . n (*)

Recurentele sint rezolvabile stiind ca f₀(x) = 0 x 0, f₀(x) = x < 0

Modelul metodei

Problemele ale caror solutii se pot obtine prin programarea dinamica sunt probleme de optim. Un prototip de astfel de problema este urmatorul:

Sa se determine determine :    optim R(x₁, . ,x_m) (1)

in conditiile in care acestea satisfac restrictii de forma

g(x₁, . ,x_m) ? 0 (2)

unde ? I

Prin optim se intelege de obicei min sau max iar ecuatia (1) se mai numeste si functie obiectiv. Un alt prototip este furnizat de digrafurile ponderate, unde R(x₁, . ,x_m) exprima suma poderilor arcelor x₁, . ,x_m iar restrictiile impun ca x₁, . ,x_m sa fie drum sau circuit cu anumite proprietati.

Metoda programarii dinamice propune determinarea valorii optime prin luarea unui sir de decizii <d₁, , d_n> numit si politica, unde decizia d_i transforma starea (problemei) s_i-1 in starea s_i , aplicind principiul de optim:

Secventa optima de decizii (politica optimala) care corespunde starii s are proprietatea ca dupa luarea primei decizii, care transforma starea s in starea s₁ , secventa de decizii (politica) ramasa este optima pentru starea s₁

De cele mai multe ori prin stare a problemei se intelege o subproblema. Unei stari i se asociaza o valoare z si se defineste f(z) astfel incit, daca starea s corespunde problemei initiale, atunci:

f(z) = optim R(x₁, . ,x_m) (3)

Principiul de optim conduce la obtinerea unei ecuatii functionale de forma:

f(z)= optim [H(z,y,f(T(z,y)))] (4)

y

unde z este valoarea asociata starii s, T(z,y) calculeaza valoarea asociata starii s' rezultata in urma deciziei y iar H exprima algoritmul de calcul al valorii f(z) data de decizia y care transforma starea s in starea s'. Dintre toate deciziile care se pot lua in starea s (producind s' ) , se alege una care da valoarea optima in conditiile in care politica aplicata in starea s' este si ea optima.

Ex: Problema rucsacului

p_i(Y_i) = max

unde p_i(Y_i ) = valoarea de optim pentru Knap(i+1,n,Y_i), Y_i= M-

Notatiile din (4) conduc la urmatoarele:

z=i , s=s_i , f(i) = optim-Knap(i+1,n,Y_i) = p_i(Y_i). Rezulta: f(i)=f(i+1)+p_i+1x_i+1

y I , T[i,y]=i+1, s'=s_i+1 , H(i,y,f(T(i,y)))=f(i+1)+ p_i+1y

H(i,0,f(T(i,0))) = H(i,0,f(i+1)] = f(i+1) = p_i+1(Y_i+1) = p_i+1(Y_i)

H(i,1 f(T(i,1))) = H(i,1,f(i+1)] = f(i+1)+p_i =p_i+1(Y_i+1)+p_i+1 =p_i+1(Y_i- w_i+1)+p_i+1

Rezulta : f(i)= max

Principiul de optim implica proprietatea de substructura optima a solutiei, care afirma ca solutia optima a problemei include solutiile optime ale subproblemelor sale. Aceasta proprietate este utilizata la gasirea solutiilor corespunzatoare starilor optime. In general, programele care implementeaza modelul dat de programarea dinamica au doua parti:

1. Determinarea valorilor optime date de sirul de decizii optime, prin rezolvarea ecuatiilor (4)

2. Construirea solutiilor (valorilor x_i care dau optimul) corespunzatoare starilor optime pe baza valorilor calculate in prima parte, utilizind proprietatea de substructura optima.

Eficienta metodei

In general, nu se recomanda scrierea unui program recursiv care sa calculeze valorile optime. In cazul programelor recusive, daca in procesul de descompunere problema subproblema, o anumita subproblema apare de mai multe ori, ea va fi rezolvata ori de cite ori apare. Asa se procedeaza in cazul aplicarii metodei Divide-and-Conquer. Este mult mai convenabil ca valorile optime corespunzatoare subproblemelor sa fie memorate intr-un tablou si apoi combinate pe baza ecuatiilor (4) pentru a obtine valoarea optima a unei subprobleme. In acest fel orice subproblema este solutionata o singura data, iar calcularea valorilor optime se face de la subproblemele mai mici la cele mai mari ("bottom-up"). Prin memorarea valorilor optime intr-un tablou se reduce si timpul de calcul pentru optimul unei subprobleme, datorita accesului la un element dintr-un tablou in O(1) timp.

Complexitatea algoritmilor care implementeaza metoda programarii dinamice depinde direct de tipul de recursivitate implicat de recurentele rezultate prin aplicarea principiului optimalitatii. In cazul recursiei liniare valorile optime pot fi calculate in timp liniar. In cazul recursiei in cascada rezulta 2ⁿ subprobleme. De obicei in aceste situatii se studiaza posibilitatea redefinirii starilor astfel incit sa rezulte o recursie liniara

Comparatie intre metoda programarii dinamice si metoda greedy

- Metoda greedy utilizeaza proprietatea alegerii locale: solutia globala optima este construita prin selectii optime locale

- Metoda programarii dinamice utilizeaza proprietatea de substructura optima: solutia optima a unei probleme include in structura sa solutiile optime ale subproblemelor

- Alegerea locala in cazul metodei greedy nu depinde de alegerile ulterioare, deci metoda greedy nu are caracter recursiv.

- Proprietate de substructura optima utilizata in programarea dinamica are un caracter recursiv: pentru a construi solutia optima a problemei este necesara cunoasterea solutiilor subproblemelor. Deci rezolvarea problemei implica rezolvarea subproblemelor.

- Parcurgerea arborelui subproblemelor in cazul metodei greedy se face in maniera top-down

- Parcurgerea arborelui subproblemelor in cazul metodei programarii dinamice este facuta in stil bottom-up

Studii de caz

Problema rucsacului (0/1)

Relatiile de recurenta "backward" rezultate din aplicarea principiului de optim sint urmatoarele:

f_i (x)= max i=1,2, . n (*)

unde f_i(x) este valoarea optima a problemei knap(1,i,x). 

Recurentele sint rezolvabile stiind ca f₀(x) = 0 x 0, f₀(x) = x < 0

Exemplu : n=3, (w₁ , w₂ , w₃) = (2 , 3 , 4), (p₁ , p₂ , p₃) = (1 , 2 , 5), M = 6

f₀(x) = 0    g₁(x) = f₀(x-w₁)+p₁ = f₀(x-2) + 1

f₁(x) = max g₂(x) = f₁(x-w₂) + p₂ = f₁(x-3) + 2

f₂(x) = max    g₃(x) = f₂(x-w₃) + p₃ = f₂(x-4) + 5

f₃(x) = max    g_i(x) -se obtine din f_i printr-o translatie (w_i , p_i)

Se observa ca functia f_i este specificata de perechile (w'_j , p'_j), j = 1,r , unde w'_j sunt abscisele in care f_i are un salt , p'_j = f(w'_j).

Exemplu f₃ caracterizata de (0,0) , (2,1) , (3,2) , (4,5) , (6,6) , (7,7) , (9,8). Se observa ca functia este crescatoare, adica w'_j < w'_j+1 p'_j < p'_j+1 si ca f_i(x) = f_i(w'_j) pentru w'_jx<w'_j+1 j = 1,r , f_i(x) = w'_r xw'_r , r = numarul de salturi ale functiei.

Fie Sⁱ multimea perechilor care caracterizeaza f_i . Atunci S^i-1 caracterizeaza f_i-1.

Se noteaza cu Tⁱ = multimea ce caracterizeaza g_i(x) = f_i-1(x-w_i) + p_i.

Tⁱ se obtine din S^i-1 adunand la fiecare pereche (w_i,p_i).

Sⁱ se obtine combinand Tⁱ cu S^i-1astfel incat sa se obtina maxim din cele doua functii f_i-1 si g_i. Combinarea celor doua multimi Tⁱ si S^i-1 se face dupa urmatorul principiu (principiul dominantei ) :

Fie (w'_j,p'_j) Tⁱ si (w'_k,p'_k) S^i-1 sau (w'_j,p'_j) S^i-1 si (w'_k,p'_k) Tⁱ.

Daca p'_j < p'_k si w'_j > w'_k , atunci (w'_j,p'_j) se elimina.

Pentru exemplul anterior:

S⁰ = T¹ =

S¹ = T² =

S² = T³ =

S³ =

Observatii 1. In calculul multimilor Sⁱ se pot elimina toate perechile (w,p) cu w > M, deoarece nu se calculeaza f_i(x) cu x > M.

2. In conditiile eliminarilor de la obs.1. valoarea de optim a solutiei este data de ultima pereche din Sⁿ , (w,p) , anume p este valoarea de optim.

3. Metoda prezentata nu ofera inca o solutie completa. Cum se deduce solutia (x₁ x₂ x_n) ?

Fie (w,p) ultima pereche din Sⁿ . Daca (w,p) S^n-1 , atunci x_n = 0 altfel x_n=1. Daca (w,p) S^n-1, atunci (w-w_n, p-p_n) S^n-1 .

Se considera (w',p')= (w-w_n, p-p_n) daca (w,p) S^n-1 . Altfel (w',p')= (w, p). Se testeaza (w',p') S^n-2 etc.

Pentru exemplul anterior:

M = 6 , S³ =

(w,p) = (6,6) , (6,6) S² , deci x₃ = 1

(6-w₃, 6-p₃) = (2,1)

(2,1) S² , (2,1) S¹ x₂ = 0

(2,1) S¹ , (2,1)S⁰ x₁ = 1

dinamic_knapsack(w,p,n,M)

{

S⁰ = ;

for i =1, . ,n

;

Sⁱ = combine(Tⁱ,S^i-1) ;

}

fie (w,p) ultima pereche din S^{n ;}

for i=n,n-1, . ,1

if (w,p) S^i-1

x_i=0;

else

Complexitate

Algoritmul construieste element cu element multimile S⁰, S¹, . .Sⁿ. In cazul cel mai defavorabil cind nu se elimina nimic | S⁰|=1, |S¹|=2, . .|Sⁱ|=2*|S^i-1|=2ⁱ, . . Un calcul simplu produce urmatorul rezultat

Rezulta o complexitate de timp si de spatiu exponentiala O(2ⁿ)

Metoda deci este extrem de ineficienta.

Inmultire optima de matrici

Presupunem ca avem produsul de matrice A₁ x A₂ x A₃ x x A_n , unde pentru i=1, . ,n, A_i are dimeniunile d_i si d_i+1 . Pentru inmultirea acestor matrice numarul total de operatii este d₁ * d₂ **d_n. Asociativitatea permite o strategie de solutie care sa minimizeze numarul total de inmultiri.

Exemplu fie produsul de matrice A₁ x A₂ x A₃ x A₄

_{de dimensiuni: (100,1) (1,100) (100,1) (1,100)}

Consideram urmatoarele variante de asociere a inmultirilor:

1) (A₁ x A₂) x (A₃ x A₄) nr.oper. = 10000 + 10000 + 1000000 = 1020000

2) (A₁ x (A₂ x A₃)) x A₄ nr.oper. = 100 + 100 + 10000 = 10200

Rezolvarea problemei prin programare dinamica:

Fie A_i,j = A_i x A_i+1 x x A_j 1 i j n si cost[ i,j] - costul inmultirii.

Observam cost[ i,i] = 0 1 i n

cost[i, i+1] = d_i * d_i+1 * d_i+2 pentru 1 i n-1

Principiul optimalitatii se poate formula astfel:

Pentru un pas general al inmultirii:

(A_i x A_i+1 x x A_k) x ( A_k+1 x A_k+2 x x A_j)

d_i,d_i+1 d_i+1,d_i+2 d_k,d_k+1 d_k+1,d_k+2 d_k+2,d_k+3 d_j,d_j+1

cost[ i, j ]= min

ik<j

Putem calcula acest cost[i,j] in ordinea :  j - i = 1

j - i = 2

..

j - i = n - 1 pana la cost[1,n].

Construim matricea cost[i,j]. Observam ca matricea este triunghiulara.

prod(n,d,cost)

cost[ j,i ]= q // q -indicele pt care se realiz. minimul anterior.

}

}

Pentru exemplul anterior, calculul costului este urmatorul:

n = 4

d = ( 100, 1 , 100 , 1 , 100 )

cost[1,1] = cost[2,2] = cost[3,3] = cost[4,4] = 0

Pentru k = 1:

i = 1, j = 2, p =1

cost[1,2] = 0 + 0 + 10000 = 10000

i = 2, j = 3, p = 2

cost[2,3] = 0 + 0 + 100 = 100

i = 3, j = 4, p = 3

cost[3,4] = 0 + 0 + 10000 = 10000

Pentru k = 2 :

i = 1 , j = 3

cost[1,3] = min

= min= 200

i = 2 , j = 4

cost[2,4] = min

= min= 200

Pentru k = 3 :

i = 1 , j = 4

cost[1,4] = min

= min= 10200

Complexitate:

Se poate usor observa ca algoritmul lucreaza in O(n³) , intrucat sunt doua bucle for, plus numarul de comparatii pentru selectia minimului.

= = = - -+

= n- n^. 2n+ n - + = O(n³)

Arbori binari de cautare optimali

Fie A=( a₁, a₂, . . a_n ) secventa sortata crescator cu valori din care se construieste un arbore de cautare. Se considera ca operatia de cautare se executa cu anumite frecvente. Anume:

P = ( p_i ; p_i - probabilitatea de a fi cautat elementul a_i , i= 1,n )

Q = ( q_i ; q_i - probabilitatea de a fi cautat un element x cu proprietatea a_i<x<a_i+1 , i=0,n )

unde a₀= - , a_n+1= +.

In aceste conditii se noteaza:

- probabilitatea de succes

- probabilitatea de insucces

iar

+ = 1

Pentru P si Q date arborele binar de cautare optimal este cel pentru care operatia de cautare ofera timp mediu minim. Pentru a pune in evidenta timpul mediu se considera arborele binar de cautare completat cu o serie de pseudonoduri corespunzatoare intervalelor de insucces, pseudonoduri care se asociaza pointerilor nuli. In exemplul de mai jos se prezinta un arbore si completatul sau.

Nodul E_i corespunde tuturor cautarilor fara succes pentru valori cuprinse in intervalul

(a_i, a_i+1). Timpul unei operatii de cautare pentru un element x este dat de adincimea nodului de valoare x sau de adincimea pseudonodului corespunzator intervalului care-l contine pe x.

Costul unui arbore reprezinta timpul mediu al unei cautari pentru o valoare x , adica

Prin level(a) se noteaza nivelul nodului a si reprezinta numarul de comparatii efectuate de functia de cautare pe drumul de la radacina pina la nodul a. Ponderind acest numar cu probabilitatea de a fi cautat nodul a si efectuind suma pentru toate nodurile se obtine timpul mediu de cautare cu succes a unui nod. In mod similar se calculeaza timpul mediu de cautare pentru insucces, cu observatia ca din level(E_i) se scade valoarea 1 deoarece decizia de apartenenta la un interval nu se face la nivelul pseudonodului ci la nivelul parintelui sau.

Data fiind secventa de valori A se pot construi o multime de arbori binari de cautare cu cheile nodurilor din A. Un arbore binar de cautare optimal este arborele de cost minim.

Din punctul de vedere al programarii dinamice, construirea unui arbore optimal consta intr-un sir de decizii privind nodul care se alege ca radacina in fiecare pas.

Fie ( a₁, a₂, . ..a_k, . . a_n) secventa de noduri sortata crescator si presupunem ca in primul pas se alege ca radacina nodul a_k. Conform principiului optimalitatii vom avea:

subarborele sting L este construit cu secventa ( a₁, a₂, . ..a_k-1) si clasele (E₀,E₁, . E_k-1)

subarborele drept R este construit cu secventa ( a_k+1, a_k+2, . ..a_n) si clasele (E_k, E_k+1, . ..E_n)

Valoarea level() se calculeaza relativ la subarborii L, R, respectiv.

Costul asociat arborelui devine

( * )

Sumele reprezinta valorile suplimentare care apar datorita faptului ca arborele intreg

T introduce un nivel suplimentar (cel al radacini) fata de subarborii L,R. In continuare relatia ( * ) se rescrie ca :

  ( ** )

Notind se obtine:

. ( *** )

Atunci cind acest cost este minimal el devine egal cu .

Principiul optimalitatii este respectat deoarece subarborii L si R trebuie sa fie optimi.

Se noteaza cu c_i,j costul unui subarbore optimal T_i,j care are nodurile din secventa (a_i+1, a_i+2, . . ..a_j) si pseudonodurile din (E_i, E_i+1, . .E_j ).

Pentru situatia discutata anterior, in conditiile in care arborele cu nodul radacina a_k este optimal, notatiile devin:

c_0,k-1=Cost( L )

c_k,n =Cost( R )

Principiul optimalitatii se scrie astfel:

    ( **** )

Generalizind,

   

Costul optimal c_0,n se poate calcula efectiv folosind ultima relatie de recurenta pentru j-i=1 apoi j-i=2, . . . j-i=n . Valorile initiale sint c_i,i=0, w_i,i=q_i, 0 i n . In plus se foloseste relatia

Algoritmul de calcul al arborelui optimal

opt-bst(P,Q,n)

// (a₁,a₂, . .a_n) secventa de noduri (valori)

// P, Q, secventele de succes si insucces

// Se calculeaza C=(c_i,j)- costurile, W=(w_i,j) si R matricea de indici ai radacinilor

// r_i,j=indicele nodului radacina al subarborelui optimal format din secventa (a_i+1,a_i+2, . .a_j)

w_n,n = q_n; r_n,n = 0; c_n,n = 0;

for m =2, . ,n

for i =0, . ,n-m

; // (XXX)

c_i,j = w_i,j + c_i,k-1 + c_k,j ;

r_i,j = k ;

}

}

Complexitate

In mod obisnuit algoritmul lucreaza in timp O(n³) . Exista o observatie a lui Knuth prin care in linia marcata (XXX) in algoritm nu se considera intervalul de indici I=[i+1, j] ci intervalul I=[ r_i,j-1 , r_i+1,j], algoritmul lucrind astfel corect in timp O(n²).