Paradigma Programare dinamica

Prezentarea generala a paradigmei Studii de caz

alocarea resurselordrumurile minime intr-un digrafrucsac 0/1distanta intre siruridistanta intre sirurisubsecventa crescatoare de lungime maximaPrezentarea formala a paradigmei

Programare dinamica - ingrediente

probleme de optim definirea subproblemei (stare) si asocierea functii obiectiv

pentru subproblema definirea unei relatii de tranzitie intre stari (decizie) politica = secventa de decizii aplicarea Principiului de Optim pentru obtine relatia de

recurenta

Principiul de Optim (PO): o subpolitica a unei politici optimale este la rindul ei optimala

calculul recurentei rezolvind subproblemele de la mic la mare si memorind valorile date de relatia de recurenta intr-un tablou

extragerea solutiei optime din tablou

Exemplu: retea triunghiulara de numere: modelare

functia obiectiv: maxdD lg(d)

stare: DMR(i) = subreteaua cu virful in ai val. asociata: i functia asociata: f(i) = maxdD(i) lg(d)

decizii posibile: DMR(i) DMR(stg(i)),

DMR(i) DMR(drp(i)) recurenta obtinuta: f(i) = max(f(stg(i)), f(drp(i))) + ai

a0

a1

a3 a5

a6 a7

a4

a2

a9a8

Exemplu: retea triunghiulara de puncte: implementare

Tine minte! Rezolva subproblemele de la mic la mare si memoreaza valorile date de relatia de recurenta intr-un tablouvalorile functiei f[] vor fi calculate in ordinea

f[n-1], f[n-2], ..., f[2], f[1], f[0]

Atentie! Transformarea recurentei in recursie duce la solutii costisitoare (subprobleme rezolvate de mai multe ori).

extragerea solutiei optime din tabel initial: sol[0] = 0pas curent:

• daca f[sol[i]] = f[stg[sol[i]]]+a[sol[i]]

atunci sol[i+1] = stg[sol[i]]

altfel sol[i+1] = drp[sol[i]]

Alocarea resurselor

Pentru realizarea a p proiecte sunt disponibile r resurse. Alocarea a j resurse la proiectul i produce un profit c[i,j]. Problema consta in alocarea celor r resurse astfel incat profitul

total sa fie maxim.

c[1,0]

c[2,0]

c[2,1] c[2,2]

c[2,0]

c[2,1]

c[3,0]

c[3,1]

c[3,2]

c[1,2]

c[1,1]s t

proiectul 1 proiectul 2 proiectul 3

c[2,0]

Alocarea resurselor

Intrare:Digraf etajat G = (V, A),

• V = V1 V2 … Vp Vp+1

• Vi Vj = Ø

• V1 = {s}. Vp+1 = {t}

• daca un arc are sursa in Vi atunci are destinatia in Vi+1

functie de profit c : A R Iesire: un drum de la s la t de profit maxim

Alocarea resurselor

X V stare: DODE(j) = problema determinarii drumurilor de la j la t V = {0, 1, …, n-1} D[i,j] = drumul optim la j Vi la t

ValOpt[i,j] valoarea acestui drum decizie: DODE(j) DODE(k) aplicam PO si obtinem

ValOpt[i, j] = c[j, k] + ValOpt[i+1, k] de unde rezulta recurenta:

ValOpt[p+1, n-1] = 0

ValOpt[i, j] = optim{c[j, k] + ValOpt[i+1, k] | k Vi+1, (j,k) A}

ordinea de rezolvare a subproblemelor:

DODE(Vp+1), DODE(VpVp+1), …, DODE(V)

Alocarea resurselor

function alocRes(G, ValOpt, D)for j 0 to G.n-2 do ValOpt[j] ValOpt[G.n-1] 0 for k G.n-1 downto 1 do q G.a[k] while (q NULL) do j q->varf if (ValOpt[j] < ValOpt[k] + q->c) then ValOpt[j] ValOpt[k] + q->c S[j] k q q->succ D[0] 0 D[p] n-1 for i 1 to p-1 do D[i] S[D[i-1]] return ValOpt[0] end

Drumuri minime intr-un digraf

Problemainstanta:

• D = (V, A, lg), lg : A R

• lg[i, i] = 0, lg[i, j] = daca (i,j) A

• lungime drum = lungimilor arcelor de pe drumiesire:

• pentru orice pereche (i,j) lungimea celui mai scurt drum de la i la j

Modelul matematicstare: DMD(X) – drumuri minime cu virfuri intermediare in X

• functia asociata: LX[i, j] = lung. drumului minim de la i la j cu virfuri intermediare in X

Drumuri minime intr-un digraf (continuare)

decizie: DMD(X{k}) DMD(X) relatia de recurenta:

LX {k}[i, j] = min{LX[i, j], LX[i, k] + LX[k, j]}

L[i, j] = lg[i, j]politica optima: DMD(), DMD({0}), DMD({0,1}), ...,

DMD({0,1, ...,n-1})notatie: Lk[i, j] = L{0,1,...,k-1}[i, j]

Lk[i, j] = min{Lk-1[i, j], Lk-1[i, k] + Lk-1[k, j]}matricele Lk sint calculate in ordinea L0, L1,…, Ln

Drumuri minime intr-un digraf: algoritm (Floyd-Warshall)

procedure DMD(D, L)begin

for all [i,j] doif (i,j) A)then L[i,j] lg[i,j]else L[i,j] if (i = j) then L[i,j] = 0;

for k 1 to n dofor all [i,j] do

temp L[i,k] + L[k,j]if (L[i,j] > temp) then L[i,j] tempif (i=j and L[i,i] < 0) then throw “ERR:circuit negativ”

end

Problema rucsacului (varianta discreta): formulare

instanta: n obiecte 0, 1, ..., n-1 de dimensiuni (greutati) w0, w1, ..., wn-1

un rucsac de capacitate M un obiect i poate fi introdus in rucsac complet (xi = 1) sau de loc

(xi=0)

introducerea in rucsac a obiectului i aduce un profit pi

profitul total adus de alegerile x0, ..., xn-1 este i=0,n-1 xipi

iesire:o alegere pentru care profitul adus este maxim

Problema rucsacului (varianta discreta): solutie

modelul matematicstare: RUCSAC(j, X)

• functia obiectiv:

max i=0,j-1 xipi

• restrictii:

(i)xi {0,1}

i=0,j-1 xiwi X

X Z, (i)wi ,pi Z

functia asociata unei stari: fj(X) = max i=0,j-1 xipi

Problema rucsacului (varianta discreta): solutie (cont)

decizie: RUCSAC(j, X) RUCSAC(j-1, ?)relatia de recurenta:

altfel.))(),(max(

,000

,0

)(

1111 jjjj

j

pwXfXf

jX

X

Xf

Problema rucsacului (varianta discreta): exemplu

M = 10, p = (10, 30, 20), w = (3, 5, 6)

40

4040403030301010000f2(X)

10

0 0 000000000f0(X)

10 101010101010000f1(X)

40403030301010000f3(X)

109876543210X

x2 = 0 x1 = 1 x0 = 1

Problema rucsacului (varianta discreta): functiile fi

fi este o functie in scara

graficul lui fi poate fi reprezentat prin multimea punctelor de salt Si

graficul lui gi-1(X) = fi-1(x-wi-1)+pi-1 este o translatie a lui Si-1 ; notam (Si-1)

graficul lui fi = max(fi-1, gi-1) se obtine prin interclasarea graficelor Si-1 si (Si-1);

notam (Si-1,(Si-1))

Problema rucsacului (varianta discreta): algoritmprocedure Rucsac(n, p, w)begin

/* calculeaza valoarea optima */

S0 {(0,0)}for i 1 to n do

Si (Si-1,(Si-1))/* determina alegerea optima */

calc. (U,V) a.i. Xj= max{Xi|(Xi,Yi) Sn, Xi M}for i n-1 downto 0 do

if ((U,V) Si then xi+1 = 0

else xi+1 = 1;

(U,V) = (U-wi+1,V-pi+1) end

Problema rucsacului (varianta discreta): complexitate

calculul lui Si din Si-1 se face in timpul |Si|

punctele (Xj,Yj)din Si satisfac:

0 Xj M

0 Yj kpk nmaxkpk

rezulta

|Si| min(M, nmaxkpk) nmax(p0, p1,…, pn-1,M)

rezulta ca Sn-1 se calculeaza in timpul

O(n2max(p0, p1,…, pn-1,M))

calculul solutiei se face in timpul O(n) rezulta ca timpul de executie a algoritmului este

O(n2max(p0, p1,…, pn-1,M))

spatiul: |S0| + |S1| + … + |Sn-1| = O(n2max(p0, p1,…, pn-1,M))

daca max(p0, p1,…, pn-1,M) > 2n atunci timpul de executie a algoritmului este exponential

algoritmul este pseudo-polinomial

Algoritmi pseudo-polinomiali

consideram probleme pentru care intrarea pentru P este data ca o secventa de numere intregi

presupunem ca intrarea este codificata peste alfabetul {0,1,#}daca x = (x0, x1,…, xn-1), atunci

cod(x) = cod(x0)#cod(x1)#…#cod(xn-1), cod(x1) {0,1}*

max(x) = max{x0, x1,…, xn-1}

un algoritm A pentru P este pseudo-polinomial (relativ la timpul de executie) daca exista un polinom p(X,Y) de doua variabile astfel incat timpul de executie a lui A este

TA(x) = O(p(|cod(x)|, max(x)))

daca q(X) este un polinom astfel incat max(x) q(|cod(x)|), atunci TA(x) este marginit de un polinom

Algoritmi pseudo-polinomiali

s 0i 0while (i < m) do

i i+1s s + i

• nr. de biti pentru reprez. lui m este

• n = [log m] + 1

• luam m = 2n-1

• presupunem ca op. i < m si i i+1 se executa fiecare in timpul log i

• prespunem ca op. s s + i se executa in timpul log s • rezulta un timp de calcul

• TA(m) = Θ(m log m) = Θ(n 2n)

• algoritmul este pseudo-polinomial

• p(X,Y) = XY

• TA(m) = Θ (p(n, m))

Distanta intre siruri – problema

instantadoua siruri a si b de lungime nasupra lui a se pot face operatiile:

• modificare: M(i, c) daca ai c• stergere: S(i)• inserare: I(i, c)

iesireo secventa de operatii de lungime minima care transforma

sirul a in b exemplu

a = “armata”, b = “camara”“armata” “amata” “camata” “camara”d[“armata”, “camara”] = 3

Distanta intre siruri – propretati

ordinea operatiilor intr-o secventa optima nu are importanta

“armata” “amata” “camata” “camara”“armata” “amata” “amara” “camara”“armata” “carmata” “camata” “camara”“armata” “carmata” “carmara” “camara”“armata” “armara” “amara” “camara”“armata” “armara” “carmara” “camara”

Distanta intre siruri – proprietati (cont.)

exista o secventa optima in care sirurile intermediare au lungimea n

d[a,b] este o metrica:d[a, a] = 0d[a, b] = d[b, a]d[a, c] d[a, b] + d[b, c]

Distanta intre siruri – model

stare: DES[i,j] = determinarea distantei minime intre subsirurile de lungime i si respectiv j

valoarea asociata unei stari: [i,j] functia asociata unei stari: d[i, j] = d[a[1..i], b[1..j]] decizie:

presupunem ca b[j] se obtine prin stergere:

DES[i,j] DES[i-1, j]presupunem ca b[j] se obtine prin modificare:

DES[i,j] DES[i-1, j-1]presupunem ca a[i] se obtine prin inserare:

DES[i,j] DES[i, j-1]

Distanta intre siruri – model (cont.)

relatia de recurenta

d[0, j] = j, d[i, 0] = i (i, j)

d[i, j] = min{d[i-1, j] + 1, d[i-1, j-1] + [i, j], d[i, j-1] + 1}

[i, j] = if (a[i] = b[j]) then 0 else 1

timp:calculului matricii d: O(n2)determinarea secventei de operatii: O(n)

spatiu: O(n2)

Distanta intre siruri - exemplu

3

3

2

2

2

1

10

a

t

a

m

r

a

aramac

445566

434455

433344

443333

433222

543211

65432

( )M(5,’r’), S(2), I(1,’c’)

Distanta intre siruri - variatii

alte operatii:transpozitia: schimba ordinea a doua caractere adiacente

distanta Levenshtein (de editare)sunt admise numai inserari, stergeri si inlocuiritoate operatiile au costul 1

distanta Hammingsunt admise numai inlocuirilecostul operatiei este 1este finita ori de cate ori |a| = |b|

distanta “episodica” (episode distance)sunt admise numai inseraricostul operatiei este 1distanta este sau |b|-|a| sau

Distanta intre siruri - variatii

distanta data de cea mai lunga subsecventasunt admise numai inserari si stergeri toate operatiile au costul 1

a = “amxbtycsnma” si b = “bancxstymcxn”

“amxbtycsnma” “bamxbtycsnma” “baxbtycsnma” “banxbtycsnma” “bancxbtycsnma” “bancxtycsnma”

“bancxstycsnma” “bancxstymcsnma” “bancxstymcnma” “bancxstymcxnma” “bancxstymcxna” “bancxstymcxn” = b

• (a,x,t,y,c,n) este subsecventa comuna

• este cea mai lunga?

Distanta intre siruri - aplicatii

“matching” aproximativ peste siruri (aproximate string matching)problema: dat un text s de lungime n, un patern p de lungime

m, o distanta d() intre siruri si un numar k, sa se determine pozitiile j din textul s astfel incat sa existe i cu d(p, s[i..j]) k

distanta Levenshtein: “string matching with k differences”distanta Hamming: “string matching with k missmatches”distanta episodica: “episode matching” (modeleaza cazul cand

se cauta o secventa de evenimente intr-o perioada scurta de timp)

cea mai lunga subsecventa comuna: exact ce spune numeleprocesul de cautare:

• a = p, b = s

• trebuie sa modificam alg. a.i. orice pozitie j din text este startul potential al unei potriviri; asta se realizeaza prin setarea d[0,j] = 0

Distanta intre siruri - aplicatii

• calculul matricei se face pe coloane

• initial: d[i, 0] = i pentru i = 0, …, m

• se proceseaza textul caracter cu caracter

• presupunem ca la pasul curent se proceseaza sj

• coloana j este actualizata:

d[i, j] = if (pi = sj) then d[i-1, j-1]

else 1 + min(d[i-1, j], d[i, j-1], d[i-1, j-1])

• pozitiile j pentru care d[m,j] k sunt raportate

• de remarcat ca numai ultimele doua coloane sunt necesare

Distanta intre siruri - aplicatii

s u r g e r y

0 0 0 0 0 0 0 0

s 1 0 1 1 1 1 1 1

u 2 1 0 1 2 2 2 2

r 3 2 1 0 1 2 2 3

v 4 3 2 1 1 2 3 3

e 5 4 3 2 2 1 2 3

y 6 5 4 3 3 2 2 2

Paralelizare

G. Myers. A fast Bit-Vector Algorithm for Approximate String Matching Based on Dynamic Programming, 1998 Δh[i,j] = d[i,j] - d[i, j-1], Δ[i,j] = d[i,j] - d[i-1, j], Δh[i,j], Δv[i,j] ∊ {-1,0,1} (a se vedea fig. 1 din articol) Δv[*,j] este reprezentata prin vectorii de tip bit

Pvj[i] ≡ Δv[i,j] = +1, Mvj[i] ≡ Δv[i,j] = -1 se considera celule ale matricii formate din patrate (i-1, j-1), (i-1, j), (i,

j-1), (i,j) Eq = Eq[i,j] = if pi = sj then 1 else 0

Δvout = min{-Eq, vin , Δhin }+ {1 -Δhin },Δhout = min{-Eq, vin , Δhin }+ {1 -Δvin } (a se vedea fig. 2) (Pvout , Mvout ) = (Mhin or not (Xv or Phin), Phin and Xv),

(Phout , Mhout ) = (Mvin or not (Xh or Pvin), Pvin and Xh),

unde Xv = Eq or Mvin

Paralelizare (continuare)

Scorej = m, Scorej = Scorej-1 + Δh[m,j] scanarea (a se vedea fig. 3)

Phj[i] = Mvj-1[i] or not (Xhj[i] or Pvj[i]Mhj[i] = Pvj-1[i] and Xvj[i] Scorej = Scorej-1 + (1 if Phj[m]) – (1 if Mhj[m])

Phj[0] = Mhj[0] = 0 (*)

Pvj[i] = Mhj-1[i] or not (Xvj[i] or Phj[i]Mvj[i] = Phj-1[i] and Xhj[i]

calculul pe biti (a se vedea fig. 4) algoritmul ((a se vedea fig. 5)

Subsecventa crescatoare maximala – problema

instantao secventa de numere intregi a = (a1, a2, …, an)

stergand cateva elemente din a se obtine o subsecventao subsecventa pastreaza ordinea relativa a elementelorexemplu:

• a = (9, 3, 15, 12, 7, 4, 13, 6, 8)

• subsecventa: (3, 12, 7, 6)

• subsecventa crescatoare: ( 3, 7, 13) iesire: subsecventa crescatoare de lungime maxima exemplu: exista o subsecventa crescatoare de lungime > 3? cum se poate rezolva utilizand distanta de editare?

Subsecventa crescatoare maximala – model

a = (9, 3, 15, 12, 7, 4, 13, 6, 8)

1 2 3 4 5 6 7 8 9 construim un graf G:

varfuri: 0, 1, 2, …, 9arce: { (0,i) | i > 0 } { (i,j) | a[i] <= a[j] }

0 1 32 54 76 98

Subsecventa crescatoare maximala – model

subsecventa crescatoare = drum in G subsecventa crescatoare maximala = drum de lungime maxima

in G asociem o matrice de costuri:

c[i, j] = 1 daca i < j si (a[i] <= a[j] sau i = 0)c[i,j] = - altfel

stare: SCM(i) = subproblema determinarii celui mai lung drum ce se termina in i

L[i] = valoarea optima pentru SCM(i) PO implica L[i] = L[j] + c[j,i], j predecesorul lui i pe drumul

optim relatia de recurenta:

L[0] = 0L[i] = max { L[j] + c[j,i] | j < i }

Subsecventa crescatoare maximala – model

a = (9, 3, 15, 12, 7, 4, 13, 6, 8)

0 1 2 3 4 5 6 7 8 9

L = (0, 1, 1, 2, 2, 2, 2, 3, 3, 4) extragerea solutiei:

s[4] = 9s[3] = 8s[2] = 6s[1] = 2s[0] = 0

timp de executie: O(n2) spatiu suplimentar: O(n)

Programare dinamica – prezentare formala

Modelul matematicprobleme de optim

• functia obiectiv: optim R(x1, ..., xn)

• restrictii: g(x1, ..., xn) ? 0

decizie: d: s s’unei stari s asociem o valoare z si o functie f(z) a.i. daca s

corespunde starii initiale atunci f(z) = optim R(x1, ..., xn)

politica: d1: s0 s1, d2: s1 s2, . . . , dn: sn-1 sn,

Programare dinamica – prezentare formala (cont.)

PO conduce la o relatie de recurenta:

• daca

– d: s s’ (sau d: s’ s)

– z val. asociata lui s, T(z,y) val. asociata lui s’,

– H algoritmul care calculeaza f(z) conform lui d,

atunci, aplicind PO, obtinem

f(z) = optimy H(z, y, f(T(z,y)))

Addendum: Cea mai lunga subsecventa comuna - problema

instantaX = x1 ... xm

Y = y1 ... yn

iesireZ = z1 ... zk – cea mai lunga subsecventa comuna

exemplu:

X = abeac

Y = aebcac

Z = abac

Cea mai lunga subsecventa comuna - model

stare:

Xi = x1 x2 ... xi

Yj = y1 y2 ... yj

LCS(Xi, Yj)

cazuri de baza:

LCS(X0, Yj), LCS(Xi, Y0)

decizii posibile la evaluarea LCS(Xi, Yj)

xi == yj atunci

• zk = xi = yj /\ Zk-1 este LCS(Xi-1, Yj-1)

xi =/= yj /\ zk =/= xi atunci

• Zk este LCS(Xi-1, Yj)

xi =/= yj /\ zk =/= yj atunci

• Zk este LCS(Xi, Yj-1)

Cea mai lunga subsecventa comuna – model (cont.)

recurenta:

exemplu:

ji

ji

yxjijicjic

yxjijic

ji

jic

0,]),1[],1,[max(

0,1]1,1[

000

],[

A T C T G A T

0 0 0 0 0 0 0 0

T 0 0 1 1 1 1 1 1

G 0 0 1 1 1 2 2 2

C 0 0 1 2 2 2 2 2

A 0 1 1 2 2 2 3 3

T 0 1 2 2 3 3 3 4

A 0 1 2 2 3 3 4 4