[10] prog-din

Proiectarea algoritmilor: Programare dinamica

Dorel Lucanu

Faculty of Computer ScienceAlexandru Ioan Cuza University, Iasi, Romania

[email protected]

PA 2014/2015

D. Lucanu (FII - UAIC) Programare dinamica PA 2014/2015 1 / 52

Outline

1 Prezentarea generala a paradigmei

2 Studii de cazProblema rucsacului II (varianta discreta)Distanta ntre siruri


Prezentarea generala a paradigmei

Plan





Clasa de probleme

Clasa de probleme la care se aplica include probleme de optim.



Modelul matematic

1 Definirea notiunii de stare, care este de fapt o generalizare aproblemei initiale si asocierea functiei obiectiv pentru stare.Problemei trebuie sa devina un caz particular (o stare).

2 Definirea unei relatii de tranzitie ntre stari. O relatie s s , unde ssi s sunt stari, va fi numita decizie. O politica este o secventa dedecizii consecutive, adica o secventa de forma s0 s1 sn.

3 Unei stari s i asociem o valoare z si definim f (z) astfel ncat, dacastarea s corespunde problemei initiale, atunci

f (z) = optim R(x0, . . . , xm1)



Modelul matematic

4 Aplicarea Principiului de Optim pentru obtine o relatie de recurenta.Principiul de optim (PO) afirma ca o subpolitica a unei politicioptimale este la randul ei optimala. Deoarece este posibil ca PO sa nuaiba loc, rezulta ca trebuie verificata validitatea relatiei de recurenta.

5 Principiul de optim conduce la obtinerea unei ecuatii functionale deforma:

f (z) = optimy

[H(z , y , f (T (z , y)))] (1)

unde:

s si s sunt doua stari astfel ncat una se obtine din cealalta aplicanddecizia d ,z este valoarea asociata starii s,T (z , y) calculeaza valoarea starii s , iarH exprima algoritmul de calcul al valorii f (z) dat de decizia d .



Modelul matematic

6 Relatia de mai sus poate fi interpretata astfel: dintre toate deciziilecare se pot lua n starea s (sau care conduc la starea s), se alege unacare da valoarea optima n conditiile n care politica aplicata ncontinuare (sau pana atunci) este este si ea optima.

7 Relatia (1) poate fi dovedita utilizand inductia si reducerea la absurd.Deoarece este posibil ca formularile pentru T () si sau H() sa fieneadecvate, ducand la cazul n care principiul de optim nu are loc,este necesara verificarea acestuia pentru problema supusa rezolvarii.

8 Rezolvarea ecuatiilor recurente (1) conduce la determinarea unui sirde decizii ce n final constituie politica optima prin care se determinavaloarea functiei obiectiv.



Modelul matematic

9 Calculul recurentei rezolvand problemele de la mic la mare simemorand valorile obtinute ntr-un tablou. Nu se recomanda scriereaunui program recursiv care sa calculeze valorile optime. Daca nsecventa de decizii luate, o anumita problema apare de mai multe ori,ea va fi calculata de algoritmul recursiv de cate ori apare.Exemplu cu numerele Fibonacci: pe tabla

10 Extragerea solutiei optime din tablou utilizand proprietatea desubstructura optima a solutiei, care afirma ca solutia optima aproblemei include solutiile optime ale subproblemelor sale. Deremarcat ca proprietatea de substructura optima este echivalenta cuprincipiul de optim.


Studii de caz

Plan




Studii de caz Problema rucsacului II (varianta discreta)

Plan





Problema

Se considera n obiecte 1, . . . , n de dimensiuni (greutati)w1, . . . ,wn Z+, respectiv, si un rucsac de capacitate M Z+.Un obiect i sau este introdus n totalitate n rucsac, xi = 1, saunu este introdus de loc, xi = 0, astfel ca o umplere a rucsaculuiconsta dintr-o secventa x1, . . . , xn cu xi {0, 1} si

i xi wi M. Ca si n cazul continuu, introducerea obiectului in rucsac aduce profitul pi Z iar profitul total este

ni=1 xipi .

Problema consta n a determina o alegere (x1, . . . , xn) care saaduca un profit maxim.

Deci, singura deosebire fata de varianta continua studiata la metodagreedy consta n conditia xi {0, 1} n loc de xi [0, 1].



Formularea matematica

functia obiectiv:

maxn

i=1

xi pi

restrictii:n

i=1xi wi M

xi {0, 1}, i = 1, . . . , nwi Z+, pi Z, i = 1, . . . , nM Z



Definirea notiunii de stare

Rucsac(j ,X ) reprezinta urmatoarea problema, care este o generalizare acelei initiale:

functia obiectiv:

max

ji=1

xi pi

restrictii:j

i=1xi wi X

xi {0, 1}, i = 1, . . . , jwi Z+, pi Z, i = 1, . . . , jX Z

Cu fj(X ) notam valoarea optima pentru instanta Rucsac(j ,X ). Dacaj = 0 si X 0, atunci fj(X ) = 0.



Definirea notiunilor de decizie si relatia de tranzitie

Presupunem j > 0. Consideram decizia optima prin care stareaRucsac(j ,X ) este transformata n Rucsac(j 1, ?).

Notam cu (x1, . . . , xj) alegerea care da valoarea optima fj(X ).



Aplicarea principiului de optim

Daca xj = 0 (obiectul j nu este pus n rucsac) atunci, conform principiuluide optim, fj(X ) este valoarea optima pentru starea Rucsac(X , j 1) side aici fj(X ) = fj1(X ).

Daca xj = 1 (obiectul j este pus n rucsac) atunci, din nou conformprincipiului de optim, fj(X ) este valoarea optima pentru stareaRucsac(j 1,X wj) la care se adauga profitul pi si de aicifj(X ) = fj1(X wj) + pj .



Obtinerea recurentei

Combinand relatiile de mai sus obtinem:

fj(X ) =

, daca X < 00 , daca j = 0 si X 0max{fj1(X ), fj1(X wj) + pj} , daca j > 0 si X 0

(2)

Am considerat fj(X ) = daca X < 0.



(2) ca instanta a relatiei (1)

Reamintim (1):

f (z) = optimy

[H(z , y , f (T (z , y)))]

valoarea z asociata starii s este (j ,X )

valoarea T (y , z) asociata starii s este (j 1,X y wj)algoritmul H este fj1(X y wj) + y pj , unde y {0, 1}optim

yeste max

y{0,1}care duce la scrierea mai concisa pentru cazul j > 0 si X 0:

fj(X ) = maxy{0,1}

fj1(X y wj) + y pj



Rezolvarea problemelor de la mic la mare si memorarearezultatelor n tabel

Fie M = 10, n = 3 si greutatile si profiturile date de urmatorul tabel:

i 1 2 3

wi 3 5 6pi 10 30 20

Valorile optime pentru subprobleme sunt calculate cu ajutorul relatiilor 2 sipot fi memorate ntr-un tablou bidimensional astfel:

X 0 1 2 3 4 5 6 7 8 9 10

f0 0 0 0 0 0 0 0 0 0 0 0

f1 0 0 0 10 10 10 10 10 10 10 10

f2 0 0 0 10 10 30 30 30 40 40 40

f3 0 0 0 10 10 30 30 30 40 40 40

Tabloul de mai sus este calculat linie cu linie: pentru a calcula valorile depe o linie sunt consultate numai valorile de pe linia precedenta.



Analiza

Tabloul de mai sus are dimensiunea n m (au fost ignorate prima linie siprima coloana). Daca m = O(2n) rezulta ca atat complexitatea spatiu catsi cea timp sunt exponentiale. Privind tabloul de mai sus observam caexista multe valori care se repeta.



Rafinare

In continuare ne punem problema memorarii mai compacte a acestuitablou. Construim graficele functiilor f0, f1, f2 si f3 pentru exemplul de maisus. Avem:

f0(X ) =

{ ,X < 00 ,X 0

Notam cu g0 functia data de:

g0(X ) = f0(X w1) + p1 ={ ,X < 310 , 3 X



Rafinare

Graficele functiilor f0 si g0:

6 6

3

10--



Rafinare

Functia f1 se calculeaza prin:

f1(X ) = max{f0(X ), g0(X )} =

,X < 00 , 0 X < 310 , 3 X

Notam cu g1 functia data prin:

g1(X ) = f1(X w2) + p2 =

,X < 530 , 5 X < 840 , 8 X



Rafinare


6

3

10-

6

3

10-

5

3040

8



Rafinare


f2(X ) = max{f1(X ), g1(X )} =

,X < 00 , 0 X < 310 , 3 X < 530 , 5 X < 840 , 8 X

In continuare, notam cu g2 functia data prin:

g2(X ) = f2(X w3) + p3 =

,X < 620 , 6 X < 930 , 9 X < 1150 , 11 X < 1460 , 14 X



Rafinare


6

3

10-

6

3

10-

5

30405060

85

3040

8 6 9 11 14

20



Rafinare


f3(X ) = max{f2(X ), g2(X )} =

,X < 00 , 0 X < 310 , 3 X < 530 , 5 X < 840 , 8 < X 1150 , 11 X < 1460 , 14 X



Rafinare

Graficul functiei f3:

6

3

10-

5

30

40

8

50

60

11 14



Rafinare

Se remarca faptul ca functiile fi si gi sunt functii n scara. Graficele acestorfunctii pot fi reprezentate prin multimi finite din puncte din plan. Deexemplu, graficul functiei f2 este reprezentat prin multimea{(0, 0), (3, 10), (5, 30), (8, 40)}.

X 0 1 2 3 4 5 6 7 8 9 10

f0 0 0 0 0 0 0 0 0 0 0 0f1 0 0 0 10 10 10 10 10 10 10 10f2 0 0 0 10 10 30 30 30 40 40 40f3 0 0 0 10 10 30 30 30 40 40 40

O multime care reprezinta o functie n scara contine acele puncte n carefunctia face salturi. Graficul functiei gi se obtine din graficul functiei fiprintr-o translatie iar graficul functiei fi+1 se obtine prin interclasareagraficelor functiilor fi si gi .



Rafinare

In general, fiecare fi este complet specificat de o multimeSi = {(Xj ,Yj) | j = 0, . . . , r} unde Yj = fi (Xj).Presupunem X1 < < Xr .Analog, functiile gi sunt reprezentate prin multimileTi = {(X + wi ,Y + pi ) | (X ,Y ) Si}.Notam Ti = (Si ) si Si+1 = (Si ,Ti ). Multimea Si+1 se obtine din Si siTi prin interclasare.

Algoritmul pentru :

Se considera o variabila L care ia valoarea 1 daca graficul lui fi+1 coincidecu cel al lui fi si cu 2 daca el coincide cu cel al lui gi . Deoarece (0, 0)apartine graficului rezultat, consideram L = 1, j = 1 si k = 1.



Rafinare

Presupunand ca la un pas al interclasarii se compara (Xj ,Yj) Si cu(Xk ,Yk) Ti atunci:

daca L = 1:daca Xj < Xk atunci adauga (Xj ,Yj) n Si+1 si se incrementeaza j ;daca Xj = Xk :

daca Yj > Yk atunci adauga (Xj ,Yj) n Si+1 si se incrementeaza j si k;daca Yj < Yk atunci adauga (Xk ,Yk) n Si+1, L = 2 si seincrementeaza j si k;

daca Xj > Xk atunci, daca Yk > Yj adauga (Xk ,Yk) n Si+1, L = 2 sise incrementeaza k ;

daca L = 2:daca Xj < Xk atunci, daca Yj > Yk adauga (Xj ,Yj) n Si+1, L = 1 sise incrementeaza j ;daca Xj = Xk :

daca Yj < Yk atunci adauga (Xk ,Yk) n Si+1 si se incrementeaza j si k;daca Yj > Yk atunci adauga (Xj ,Yj) n Si+1, L = 1 si se incrementeazaj si k;

daca Xj > Xk atunci adauga (Xk ,Yk) n Si+1 si se incrementeaza k;



Rafinare

Ramane de extras solutia optima din Sn. Consideram mai ntai cazul dinexemplul de mai sus.

Se cauta n Sn = S3 perechea (Xj ,Yj) cu cel mai mare Xj pentru careXj M. Obtinem (Xj ,Yj) = (8, 40). Deoarece (8, 40) S3 si(8, 40) S2 rezulta foptim(M) = foptim(8) = f3(8) = f2(8) si decix3 = 0. Perechea (Xj ,Yj) ramane neschimbata.

Pentru ca (Xj ,Yj) = (8, 40) este n S2 si nu este n S1, rezulta ca

foptim(8) = f1(8 w2) + p2 si deci x2 = 1. In continuare se ia(Xj ,Yj) = (Xj w2,Yj p2) = (8 5, 40 30) = (3, 10).Pentru ca (Xj ,Yj) = (3, 10) este n S1 si nu este n S0, rezulta cafoptim(3) = f1(3 w1) + p1 si deci x1 = 1.



Rafinare

Metoda poate fi descrisa pentru cazul general:

Initial se determina perechea (Xj ,Yj) Sn cu cel mai mare Xj pentrucare Xj M. Valoarea Yj constituie ncarcarea optima a rucsacului,i.e. valoarea functiei obiectiv din problema initiala.

Pentru i = n 1, . . . , 0:daca (Xj ,Yj) este n Si , atunci fi+1(Xj) = fi (Xj) = Yj si se facexi+1 = 0 (obiectul i + 1 nu este ales);daca (Xj ,Yj) nu este n Si , atunci fi+1(Xj) = fi (Xj wi+1) + pi+1 = Yjsi se face xi+1 = 1 (obiectul i + 1 este ales), Xj = Xj wi+1 siYj = Yj pi+1.



Algoritmul rafinat

rucsacVD(n, w, p, valOpt, x) {S0 = {(0, 0)};T0 = {(w1, p1)};for (i = 1; i < n; ++i) {

Si(X) = (Si1, Ti1)Ti = {(X + wi, Y + pi) | (X, Y) Si}

}determina (Xj, Yj) cu Xj = max{Xi | (Xi, Yi) Sn, Xi M}for (i = n-1; i 1; --i)

if ((Xj, Yj) Si) then xi+1 = 0else {

xi+1 = 1Xj = Xj wi+1Yj = Yj pi+1

}}



Analiza algoritmului rafinat

Notam m =n

i=0 |Si |. Deoarece |Ti | = |Si | rezulta ca |Si+1| 2 |Si | side aici

i |Si |

i 2

i = 2n 1. Calculul lui Si din Si1 necesita timpul(|Si1|) si de aici calculul lui Sn necesita timpul

i (|Si |) = O(2n).

Deoarece profiturile pi sunt numere ntregi, pentru orice (X ,Y ) Si , Yeste ntreg si Y ji pj . Analog, pentru ca dimensiunile wi suntnumere ntregi, pentru (X ,Y ) Si , X este ntreg si X

ji wj .

Deoarece perechile (X ,Y ) cu X > M nu intereseaza, ele pot sa nu fieincluse n multimile Si .



Analiza algoritmului rafinat

De aici rezulta ca numarul maxim de perechi (X ,Y ) distincte din Sisatisface relatiile:

|Si | 1 +i

j=1 wj|Si | M

care implica

|Si | 1 + min

ij=1

wj ,M

Relatia de mai sus permite o estimare mai precisa a spatiului necesarpentru memorarea multimilor Si n cazul unor probleme concrete. In ceeace priveste timpul, facand calculele rezulta ca algoritmul are complexitateatimp O(min(2n, n

ni=1 pi , nM)).


Studii de caz Distanta ntre siruri

Plan





Problema

Se considera doua siruri = a1 an si = b1 bn formate culitere dintr-un alfabet A. Asupra sirului se pot faceurmatoarele operatii:

Stergere: S(i) sterge litera de pe pozitia i ;Inserare: I (i , c) insereaza litera c pe pozitia i ;Modificare: M(i , c) nlocuieste litera de pe pozitia i cu c .

Problema consta n determinarea unei secvente de operatii delungime minima care transforma pe n .

Exemplu: Fie = carnet, = paleta. O secventa de transformari estecarnet 7 parnet 7 palnet 7 palet 7 paleta. Transformarile efectuatesunt M(1, p),M(3, l),S(4) si I (6, a). Exista o alta secventa mai scurta?

sfex



Analiza domeniului problemei

Lema

Fie s = (. . .T (i , ),T (j , ) . . .) o secventa optima (de lungime minima)care transforma pe n . Atunci exista k , ` astfel ncat secventas = (. . .T (k , ),T (`, ) . . .), obtinuta din s prin interschimbarea celordoua operatii T si T si n rest ramanand neschimbata, este de asemeneao secventa optima care transforma pe n .

Corolar

Exista o secventa optima care daca efectueaza transformarile:

= 0 7 1 7 7 t =

atunci pentru orice i , |i | ||, unde prin | | am notat lungimea sirului .



Analiza domeniului problemei

Lema

Are loc:

(i) d(, ) = 0;

(ii) d(, ) = d(, );

(iii) d(, ) d(, ) + d(, ).

Observatie: Lema de mai sus arata ca d(, ) este o metrica. De aici si

numele problemei. sfobs



Notiunea de stare

DS(i , j) corespunzatoare transformarii subsirului i = a1 . . . ai nj = b1 . . . bj si prin d [i , j ] valoarea optima d(i , j).

Daca i = 0, 0 este sirul vid si j se obtine prin j inserari: deci d [0, j ] = j .

Daca j = 0, atunci j se obtine prin i stergeri si avem d [i , 0] = i .

In continuare presupunem i , j > 0.



Decziile si Principiul de optim

Consideram decizia optima prin care starea DS(a1 . . . ai , b1 . . . bj) estetransformata ntr-o stare DS(a1 . . . ai , b1 . . . bj ) cu (i

< i si j j) sau(i i si j < j).Distingem urmatoarele situatii:

1 Daca ai = bj atunci i = i 1, j = j 1 si, aplicand principiul de

optim, obtinem d [i , j ] = d [i 1, j 1].2 DS(a1, . . . , ai , b1, . . . , bj) se obtine prin stergere. Rezulta

i = i 1, j = j si, aplicand principiul de optim, obtinemd [i , j ] = d [i 1, j ] + 1.

3 DS(a1, . . . , ai , b1, . . . , bj) se obtine prin inserare. Avemi = i , j = j 1 si, aplicand principiul de optim, obtinemd [i , j ] = d [i , j 1] + 1. Din corolarul lemei precedente rezulta caaceasta operatie poate fi realizata numai daca i < j .

4 DS(a1, . . . , ai , b1, . . . , bj) se obtine prin modificare. Avemi = i 1, j = j 1 si, aplicand principiul de optim, obtinemd [i , j ] = d [i 1, j 1] + 1.



Relatia de recurenta

Deoarece d [i , j ] trebuie sa fie minima, rezulta:

d [i , j ] = min{d [i 1, j ] + 1, d [i 1, j 1] + (i , j), d [i , j 1] + 1} (3)

unde

(i , j) =

{0 ,daca ai = bj

1 ,daca ai 6= bj



(3) ca instanta a relatiei (1)

Reamintim (1):

f (z) = optimy

[H(z , y , f (T (z , y)))]

valoarea z asociata starii s este [i , j ]valoarea T (y , z) asociata starii s este [i yi , j yj ], undeyi , yj {0, 1}, yi + yj > 0algoritmul H este d [i yi , j yj ] + (i , j , yi , yj), unde

(i , j , yi , yj) =

{0 ,daca ai = bj yi + yj = 21 ,daca (ai 6= bj yi + yj = 2) yi + yj = 1

optimy

este minyi ,yj{0,1},yi+yj>0

care duce la scrierea mai concisa pentru cazul i , j > 0:

d [i , j ] = minyi ,yj{0,1},yi+yj>0

d [i yi , j yj ] + (i , j , yi , yj)



Calculul lui d[i,j]: exemplu

c a m a r a

0 1 2 3 4 5 6

a 1 1 1 2 3 4 5

r 2 2 2 2 3 3 4

m 3 3 3 2 3 4 4

a 4 4 3 3 2 3 4

t 5 5 4 4 3

a 6



Determinarea secventei optime

Notam cu L lista care nregistreaza transformarile solutiei optime. Seprocedeaza n modul urmator:

initial se considera i = n; j = n; si L = ( ) (lista vida);

urmatorul proces se repeta pana cand i si j devin 0:

daca d [i , j ] = d [i 1, j 1] atunci L ramane neschimbata si se facei = i-1; j = j-1;

altfel, daca d [i , j ] = d [i 1, j 1] + 1 atunci se face L = (M(i , bj), L)si i = i-1; j = j-1;altfel, daca d [i , j ] = d [i 1, j ] + 1 atunci se face L = (S(i), L) sii = i-1;

altfel, daca d [i , j ] = d [i , j 1] + 1 atunci se face L = (I (i , bj), L) sij = j-1.



Determinarea secventei optime: exemplu

c a m a r a

0 1 2 3 4 5 6

a 1 1 1 2 3 4 5

r 2 2 2 2 3 3 4

m 3 3 3 2 3 4 4

a 4 4 3 3 2 3 4

t 5 5 4 4 3 3 4

a 6 6 5 5 4 4 3

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




c a m a r a

0 1 2 3 4 5 6

a 1 1 1 2 3 4 5

r 2 2 2 2 3 3 4

m 3 3 3 2 3 4 4

a 4 4 3 3 2 3 4

t 5 5 4 4 3 3 4

a 6 6 5 5 4 4 3

M(5, r)

, S(2), I (1, c)




c a m a r a

0 1 2 3 4 5 6

a 1 1 1 2 3 4 5

r 2 2 2 2 3 3 4

m 3 3 3 2 3 4 4

a 4 4 3 3 2 3 4

t 5 5 4 4 3 3 4

a 6 6 5 5 4 4 3

M(5, r), S(2)

, I (1, c)




c a m a r a

0 1 2 3 4 5 6

a 1 1 1 2 3 4 5

r 2 2 2 2 3 3 4

m 3 3 3 2 3 4 4

a 4 4 3 3 2 3 4

t 5 5 4 4 3 3 4

a 6 6 5 5 4 4 3

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



AlgoritmuldistSir(a, b, n) {

for (j = 1; j n; ++j) d[0,j] = j;for (i = 1; i n; ++i) d[i,0] = i;for (i = 1; i n; ++i)

for (j = 1; j n; ++j) { = (a[i] == b[j])? 0 : 1;d[i, j] = min{d[i 1, j] + 1, d[i 1, j 1] + , d[i, j 1] + 1}

}L = listaVida();i = n; j = n;repeat

if (d[i,j] == d[i-1,j-1]) {i = i-1; j = j-1;

} else if (d[i,j] == d[i-1,j-1]+1) {L.pushFront(M, i, b[j]));i = i-1; j = j-1;

} else if (d[i,j] == d[i-1,j]+1) {L.pushFront(S, i));i = i-1

} else {L.pushFront(I, i, b[j]);j = j-1;

}until ((i = 0) && (j = 0))

}D. Lucanu (FII - UAIC) Programare dinamica PA 2014/2015 47 / 52


Analiza

Teorema

Determinarea distantei optime si a secventei optime care transforma un sir ntr-un sir , || = || = n, se poate face n timpul O(n2).



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 nlocuirilecostul 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



Variatii

distanta data de cea mai lunga subsecventasunt admise numai inserari si stergeritoate operatiile au costul 1Exemplu: = amxbtycsnma si = bancxstymcxn = amxbtycsnma bamxbtycsnma baxbtycsnma banxbtycsnma bancxbtycsnma bancxtycsnma bancxstycsnma bancxstymcsnma bancxstymcnma bancxstymcxnma bancxstymcxna bancxstymcxn = (a,x,t,y,c,n) este subsecventa comunaeste cea mai lunga?



Variatii

matching aproximativ peste siruri (aproximate string matching)problema: dat un text s de lungime n, un patern p de lungime m, odistanta d() ntre siruri si un numar k , sa se determine pozitiile j dintextul s astfel ncat 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 osecventa de evenimente intr-o perioada scurta de timp)

cea mai lunga subsecventa comuna: exact ce spune numele



Variatii

procesul de cautare pentru matching aproximativ:

= p, = strebuie sa modificam algoritmul a.. orice pozitie j din text este startulpotential al unei potriviri; asta se realizeaza prin setarea d [0, j ] = 0

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 ] = (pi == sj) ? d [i 1, j 1] :1 + min(d [i 1, j ], d [i , j 1], d [i 1, j 1])pozitiile j pentru care d [m, j ] k sunt raportatede remarcat ca numai ultimele doua coloane sunt necesare


Prezentarea generala a paradigmeiStudii de cazProblema rucsacului II (varianta discreta)Distanta ntre siruri

[10] prog-din

Documents

Transcript of [10] prog-din