Tecniche Algoritmiche/3 Tecniche Algoritmiche/3 Programmazione Dinamica Programmazione Dinamica

(1)

Tecniche Algoritmiche/3 Tecniche Algoritmiche/3

Programmazione Dinamica Programmazione Dinamica

Ivan Lanese

Dip. di Informatica—Scienza e Ingegneria Università di Bologna

Ivan.lanese@gmail.com

http://www.cs.unibo.it/~lanese/

(2)

(3)

Programmazione dinamica

●

Definizione

– Strategia sviluppata negli anni '50 da Richard E. Bellman

– Ambito: problemi di ottimizzazione

– Trovare la soluzione ottima secondo un “indice di qualità” assegnato ad ognuna delle soluzioni possibili

●

Approccio

– Risolvere un problema combinando le soluzioni di sotto-problemi

Richard Ernest Bellman (1920—1984), http://en.wikipedia.org/wiki/Richard_Bellman

(4)

Programmazione dinamica vs divide-et-impera

●

Divide-et-impera

– Tecnica ricorsiva

– Approccio top-down

– Vantaggiosa quando i sottoproblemi sono indipendenti

●

Programmazione dinamica

– Tecnica iterativa

– Approccio bottom-up

– Vantaggiosa quando ci sono sottoproblemi ripetuti

(5)

Quando applicare la

programmazione dinamica?

●

Sottostruttura ottima

– Deve essere possibile combinare le soluzioni dei

sottoproblemi per trovare la soluzione di un problema più

“grande”

●

Sottoproblemi ripetuti

– Un sottoproblema compare più volte

(6)

Programmazione dinamica

1) Caratterizzare la struttura di una soluzione ottima 2) Definire ricorsivamente il valore di una soluzione

ottima

 La soluzione ottima ad un problema contiene le soluzioni ottime ai sottoproblemi

3) Calcolare il valore di una soluzione ottima “bottom-up”

 Si usa una tabella (es., array o matrice) per memorizzare le soluzioni dei sottoproblemi per evitare di ricalcolare le

soluzioni più volte

4) Costruire la (una) soluzione ottima

(7)

Numeri di Fibonacci

(8)

La successione di Fibonacci

●

La successione di Fibonacci F

1

, F

₂

, ... F

_n

, ... è definita come:

Leonardo Fibonacci (Pisa, 1170—Pisa, 1250) http://it.wikipedia.org/wiki/Leonardo_Fibonacci

F

₁

=1 F

₂

=1

F

_n

= F

_n−1

 F

_n−2

, n2

(9)

Numeri di Fibonacci in natura

● Il numero di spirali orarie e antiorarie nei fiori di girasoli, nelle pigne e in altri vegetali (es., ananas) tendono ad assumere valori adiacenti nella successione di Fibonacci

(10)

Implementazione ricorsiva

integer FibRic(integer n)

if ((n = 1) or (n = 2)) then return 1;

else

return FibRic(n-1)+FibRic(n-2);

endif

●

Costo computazionale

●

Soluzione

– T(n) = O(2ⁿ)

F(6)

F(5) F(4)

F(4) F(3) F(3) F(2)

F(1) F(2)

F(1) F(3) F(2) F(2)

F(1) F(2)

T (n)=

{

^cT (n−1)+T (n−2)+c¹ ₂ ^n≤2n>2

(11)

Implementazione iterativa

integer FibIter(integer n) if (n ≤ 2) then

return 1;

else

integer f[1..n];

f[1] ← 1;

f[2] ← 1;

for integer i ← 3 to n do f[i] ← f[i-1] + f[i-2];

endfor

return f[n];

endif

8 7

6 5

4 3

2 1

n

●

Complessità

– Tempo: Θ(n)

– Spazio: Θ(n)

(12)

Implementazione iterativa - 2

●

Complessità

– Tempo: Θ(n)

– Spazio: O(1)

● Array di 3 elementi

integer FibIter2(integer n) if (n ≤ 2) then

return 1;

else

integer f[1..3];

f[2] ← 1;

f[3] ← 1;

for integer i ← 3 to n do f[1] ← f[2];

f[2] ← f[3];

f[3] ← f[2] + f[1];

endfor

return f[3];

endif

n 3 4 5 6

f[1] 1 1 2 3

f[2] 1 2 3 5

f[3] 2 3 5 8

(13)

Sottovettore di valore massimo

(14)

Esempio (già visto)

sottovettore di valore massimo

●

Consideriamo un vettore V[1..n] di n valori reali arbitrari

●

Vogliamo individuare un sottovettore non vuoto di V la somma dei cui elementi sia massima

●

Abbiamo già visto (vedi tecniche divide-et-impera) che ci sono n(n+1)/2 sottovettori non vuoti di V

3 -5 10 2 -3 1 4 -8 7 -6 -1

(15)

Soluzione basata su “forza bruta”

Costo O(n

³

)

real SommaMax1( real V[1..n] ) real smax ← V[1];

for integer i ← 1 to n do

for integer j ← i to n do real s ← 0;

for integer k ← i to j do s ← s + V[k];

endfor

if (s > smax) then smax ← s;

endif endfor endfor

return smax;

(16)

Implementazione più efficiente Costo O(n

²

)

real SommaMax2( real V[1..n] ) real smax ← V[1];

for integer i ← 1 to n do real s ← 0;

for integer j ← i to n do s ← s + V[j];

if (s > smax) then smax ← s;

return smax;

(17)

Soluzione basata su

programmazione dinamica

●

Sia P(i) il problema che consiste nel determinare il valore massimo della somma degli elementi dei

sottovettori non vuoti del vettore V[1..i] che hanno V[i]

come ultimo elemento

●

Sia S[i] il valore della soluzione di P(i)

– S[i] è la massima somma degli elementi del sottovettori di V[1..i] che hanno V[i] come ultimo elemento

●

La soluzione S al problema di partenza può essere* espressa come

∗

(18)

Soluzione basata su

programmazione dinamica

●

P(1) ammette una unica soluzione

– S[1] = V[1]

●

Consideriamo il generico problema P(i), i > 1

– Supponiamo di avere già risolto il problema P(i - 1), e quindi di conoscere S[i - 1]

– Se S[i - 1]+V[i] ≥ V[i] allora S[i] = S[i - 1]+V[i]

– Se S[i - 1]+V[i] < V[i] allora S[i] = V[i]

S[i - 1] V[i]

P(i - 1) P(i)

(19)

Esempio

3 -5 10 2 -3 1 4 -8 7 -6 -1

V[]

3 -2 10 12 9 10 14 6 13 7 6

S[]

S[i] = max { V[i], V[i] + S[i - 1] }

(20)

L'algoritmo

real sottovettoreMax(real V[1..n]) real S[1..n];

S[1] ← V[1];

integer imax ← 1; // indice val. max in S for integer i ← 2 to n do

if ( S[i-1]+V[i] ≥ V[i] ) then S[i] ← S[i-1] + V[i];

else

S[i] ← V[i];

endif

if ( S[i] > S[imax] ) then imax ← i;

endif endfor

return S[imax];

(21)

Come individuare il sottovettore?

●

Fino ad ora siamo in grado di calcolare il valore della massima somma tra tutti i sottovettori di V[1..n]

●

Come facciamo a determinare quale sottovettore produce tale somma?

– L'indice dell'elemento finale del sottovettore l'abbiamo

– L'indice iniziale lo possiamo ricavare procedendo “a ritroso”

● Se S[i] = V[i], il sottovettore massimo inizia nella posizione i

(22)

Esempio

3 -5 10 2 -3 1 4 -8 7 -6 -1 V[]

3 -2 10 12 9 10 14 6 13 7 6 S[]

integer indiceInizio(real V[1..n], real S[1..n], integer imax) integer i ← imax;

while ( S[i] ≠ V[i] ) do i ← i - 1;

endwhile return i;

(23)

L'efficienza conta!

●

Confrontiamo l'algoritmo O(n

³

) con l'algoritmo O(n) su due piattaforme hardware molto diverse

●

Algoritmo O(n

³

)

– Ubuntu Linux 14.04

– CPU: Intel i7 @ 3.6GHz

– Linguaggio: Java 1.7.0_75

●

Algoritmo O(n)

– Commodore 64 (uscito nel 1982)

– CPU: MOS 6502 @ 1MHz

(24)

Tempi di esecuzione

(25)

Problema dello Zaino / 1

(Knapsack problem)

(26)

Problema dello zaino

●

Abbiamo un insieme X = {1, 2, ..., n} di n oggetti

●

L'oggetto i-esimo ha peso p[i] e valore v[i]

●

Disponiamo un contenitore in grado di trasportare al massimo un peso P

●

Vogliamo determinare un sottoinsieme Y X tale che

– Il peso complessivo degli oggetti in Y sia ≤ P

– Il valore complessivo degli oggetti in Y sia il massimo

possibile, tra tutti gli insiemi di oggetti che possiamo inserire nel contenitore

(27)

Definizione formale

●

Vogliamo determinare un sottoinsieme Y X di oggetti tale che:

e tale da massimizzare il valore complessivo:

∑

x∈Y

p[ x ]≤P

∑

x∈Y

v [ x ]

(28)

Approccio greedy #1

(non produce sempre una soluzione ottima)

●

Ad ogni passo, scelgo tra gli oggetti non ancora nello zaino quello di valore massimo, tra tutti quelli che

hanno un peso minore o uguale alla capacità residua dello zaino

– Questo algoritmo non fornisce sempre la soluzione ottima

(29)

Esempio

20Kg 10Kg / 15€

8Kg / 20€

20Kg / 28€

10Kg / 15€

8Kg / 20€

20Kg / 28€

●

La soluzione calcolata in questo esempio non è la

soluzione ottima!

(30)

Approccio greedy #2

(non produce sempre una soluzione ottima)

●

Ad ogni passo, scelgo tra gli oggetti non ancora nello zaino quello di valore specifico massimo, tra tutti quelli che hanno un peso minore o uguale alla capacità

residua dello zaino

– Il valore specifico è definito come il valore di un oggetto diviso il suo peso

– Anche questo approccio non fornisce sempre la soluzione ottima

(31)

Esempio

20Kg 10Kg / 15€

8Kg / 20€

20Kg / 28€

1.5 2.5

1.4 20Kg / 28€ 1.4

8Kg / 20€ 10Kg / 15€

●

In questo esempio, l'algoritmo greedy #2 calcola la

soluzione ottima, ma...

(32)

Esempio

20Kg 10Kg / 15€

10Kg / 20€

11Kg / 33€

1.5 2.0 3.0

10Kg / 15€

10Kg / 20€

1.5 2.0 11Kg / 33€

●

...in questo altro esempio anche l'algoritmo greedy #2 non produce la soluzione ottima

9Kg

(33)

Soluzione ottima basata sulla Programmazione Dinamica

●

NB: l'algoritmo di programmazione dinamica richiede che i pesi siano numeri interi

●

Definizione dei sottoproblemi P(i, j)

– “Riempire uno zaino di capienza j, utilizzando un opportuno sottoinsieme dei primi i oggetti, massimizzando il valore

degli oggetti usati”

●

Definizione delle soluzioni V[i, j]

– V[i, j] è il massimo valore ottenibile da un sottoinsieme degli oggetti {1, 2, ... i} in uno zaino che ha capacità j

i = 1, 2, ...n

(34)

Calcolo delle soluzioni:

casi base

●

Primo caso base: zaino di capienza zero

– V[i, 0] = 0 per ogni i = 1..n

● Se la capacità dello zaino è zero, il massimo valore ottenibile è zero (nessun oggetto)

●

Secondo caso base: ho a disposizione solo l'oggetto 1

– V[1, j] = v[1] se j ≥ p[1]

● C'è abbastanza spazio per l'oggetto numero 1

– V[1, j] = 0 se j < p[1]

● Non c'è abbastanza spazio per l'oggetto numero 1

V[i, j] denota il massimo valore ottenibile da un sottoinsieme degli oggetti {1, 2, ..., i} in uno zaino che ha capacità massima j

(35)

Calcolo delle soluzioni:

caso generale

●

Se j < p[i] significa che l'i-esimo oggetto è troppo pesante per essere contenuto nello zaino. Quindi V[i, j] = V[i - 1, j]

●

Se j ≥ p[i] possiamo scegliere se

– Inserire l'oggetto i-esimo nello zaino. Il valore massimo ottenibile in questo caso è V[i - 1, j - p[i] ] + v[i]

– Non inserire l'oggetto i-esimo nello zaino. Il massimo valore ottenibile in questo caso è V[i - 1, j]

– Scegliamo l'alternativa che massimizza il valore:

V[i, j] = max{ V[i - 1, j], V[i - 1, j - p[i] ] + v[i] }

(36)

Soluzione ottima basata sulla Programmazione Dinamica

●

Riassumendo

V [i , j]= { ^{V [i−1, j]} se j p[i ]

max { V [i−1, j] ,V [i−1, j− p [i ]]v [i] } se j≥ p[i ]

j - p[i] Kg p[i] Kg

V[i - 1, j - p[i] ] v[i]

1 2 i - 1 i

(37)

Tabella di programmazione dinamica / matrice V

0.0 12.7

0.0

0.0 0.0 0.0

0.0

0.0 0.0

12.7 12.7 12.7

12.7 12.7 12.7 12.7

12.7 12.7 12.7 13.0

12.7 12.7

12.7 13.0

14.4 12.7

14.4

19.1

19.1 19.1 19.1 19.1 19.1 12.7

0 1 2 3 4 5 6 7 8 9 10

1 2 3 4

j

i

p =[ 2, 7, 6, 4 ]

v = [ 12. 7, 6.4, 1.7, 0.3]

(38)

Tabella di programmazione dinamica / matrice V

0.0 12.7

0.0

0.0 0.0 0.0

0.0

0.0 0.0

12.7 12.7 12.7

12.7 12.7 12.7 12.7

12.7 12.7 12.7 13.0

12.7 12.7

12.7 13.0

14.4 12.7

14.4

19.1

19.1 19.1 19.1 19.1 19.1 12.7

0 1 2 3 4 5 6 7 8 9 10

1 2 3 4

p =[ 2, 7, 6, 4 ]

v = [ 12. 7, 6.4, 1.7, 0.3]

j

i

V (3,8)=max { V (2,8) ,V (2, 8−6)+1.7 }

= max { 12.7,14.4 }

(39)

Stampare la soluzione

●

Il valore della soluzione ottima del problema di partenza è V[n, P]

●

Come facciamo a sapere quali oggetti fanno parte della soluzione ottima?

– Usiamo una tabella ausiliaria booleana K[i, j] che ha le stesse dimensioni di V[i, j]

– K[i, j] = true se e solo se l'oggetto i-esimo fa parte della soluzione ottima del problema P(i, j) che ha valore V[i, j]

(40)

Programmazione Dinamica 40

Tabella di programmazione

dinamica / stampa soluzione ottima

integer j ← P;

integer i ← n;

while ( i > 0 ) do

if ( K[i,j] = true ) then

stampa “Seleziono oggetto “, i j ← j - p[i];

endif

i ← i - 1;

endwhile

F

0 1 2 3 4 5 6 7 8 9 10

1 2 3 4

F T T T T T T

T T

T

T T

F F F F F F F F F

T F F

F F F F F F F F

F F

F

T T

F F F F F F

p =[ 2, 7, 6, 4 ]

v = [ 12. 7, 6.4, 1.7, 0.3 ]

(41)

Problema dello Zaino / 2

(Subset-sum problem)

(42)

Subset-Sum Problem / 1

●

E' dato un insieme X = {1, 2, ..., n} di n oggetti

– L'oggetto i-esimo ha peso p[i]

– I pesi sono numeri interi positivi

●

Disponiamo un contenitore in grado di trasportare al massimo un peso C (capacità dello zaino)

●

Vogliamo determinare un sottoinsieme Y X tale che

il peso complessivo degli oggetti in Y sia esattamente

uguale a C

(43)

Subset-sum problem

●

Definizione dei problemi P(i, j)

– “Determinare se esiste un sottoinsieme (anche vuoto) dei primi i oggetti aventi peso complessivo esattamente uguale a j”

●

Definizione delle soluzioni B[i, j]

– B[i, j] = true se e solo se esiste un sottoinsieme (anche

vuoto) dei primi i oggetti {1, 2, … i} avente peso complessivo uguale a j

(44)

Calcolo delle soluzioni:

casi base

●

B[i, 0] = true per ogni i = 1, … n

– L'insieme vuoto è sottoinsieme di qualunque insieme di oggetti, e ha peso uguale a 0

●

B[1, j] = true se j = p[1]

– La capacità dello zaino è pari al peso dell'unico oggetto a disposizione (il primo)

●

B[1, j] = false se j > 0, j ≠ p[1]

– La capacità j è diversa dal peso dell'oggetto 1

B[i, j] = true se e solo se esiste un sottoinsieme (anche vuoto) dei primi i oggetti {1, 2, … i} avente peso complessivo esattamente uguale a j

(45)

Calcolo delle soluzioni:

caso generale

●

Se j < p[i] significa che l'i-esimo oggetto è troppo

pesante per essere contenuto nello zaino. In tal caso B[i, j] ← B[i - 1, j]

●

Se j ≥ p[i] ho due possibilità

– Inserire l'oggetto i-esimo nello zaino. In questo caso il

problema P(i, j) ammette soluzione se B[i - 1, j - p[i] ] è true

– Non inserire l'oggetto i-esimo nello zaino. In questo caso il problema P(i, j) ammette soluzione se B[i - 1, j] è true

j

(46)

Quali oggetti fanno parte della soluzione (se esiste)?

●

Sfruttiamo un array booleano U[i, j]

– i = 1, ... n

– j = 0, ... C

●

U[i, j] = true se e solo se l'oggetto i-esimo fa parte di un sottoinsieme dei primi i oggetti {1, ... i} di peso

complessivo j

(47)

bool SubsetSum(integer p[1..n], integer C)

bool B[1..n, 0..C], U[1..n, 0..C]; integer i, j;

B[1,0] ← true; U[1,0] ← false;

for j ← 1 to C do

if (j = p[1]) then

B[1,j] ← true; U[1,j] ← true;

else

B[1,j] ← false; U[1,j] ← false;

for i ← 2 to n do

if ( j ≥ p[i] ) then

B[i,j] ← B[i-1,j] or B[i-1,j-p[i]];

U[i,j] ← B[i-1,j-p[i]];

else

B[i,j] ← B[i-1,j]; U[i,j] ← false;

if ( not B[n,C] ) then

print “nessuna soluzione”;

else

i ← n; j ← C;

while ( i > 0 and j > 0 ) do if U[i,j] then

(48)

Problema dello Zaino / 3

(49)

Problema dello zaino / 3

●

Il solito insieme X = {1, 2, ..., n} di n oggetti

– L'oggetto i-esimo ha peso p[i]

– I pesi sono numeri interi positivi

●

Disponiamo un contenitore in grado di trasportare peso massimo C (capacità dello zaino)

●

Vogliamo riempire lo zaino il più possibile

– Vogliamo determinare un sottoinsieme Y X di oggetti il cui peso complessivo sia massimo possibile e minore o uguale a C

(50)

Problema dello zaino / 3

●

Definizione dei problemi P(i, j)

– Determinare un sottoinsieme dei primi i oggetti il cui peso sia massimo possibile, e minore o uguale a j

●

Definizione delle soluzioni M[i, j]

– M[i, j] = massimo peso minore o uguale a j che si può ottenere da un opportuno sottoinsieme dei primi i oggetti aventi pesi p[1], … p[i]

●

Definizione della soluzione del problema di partenza

– E' il valore di M[n, C]

(51)

Definizione di M[i, j]

●

Casi base: M[1, j], con j = 0, ... C

●

Caso generale: M[i, j] con i = 2, … n, j = 0, ... C

M [1, j ]= { ⁰ se j< p[1]

p[1] altrimenti

M [i , j]=

{

M [i−1, j ] se j < p[i]

max( M [i−1, j ] , M [i−1, j− p[i ]]+ p[i ]) altrimenti

(52)

integer Zaino3(integer p[1..n], integer C) integer M[1..n, 0..C];

integer i, j;

if (j < p[1]) then M[1, j] ← 0;

else

M[1, j] ← p[1];

for i ← 2 to n do

if (j≥p[i] and M[i-1,j-p[i]] + p[i] > M[i-1,j]) then M[i,j] ← M[i-1,j-p[i]] + p[i];

elseM[i,j] ← M[i-1,j];

return M[n, C];

(53)

Seam Carving

(54)

Seam Carving

●

Algoritmo per ridimensionare immagini in modo

“intelligente”

– Shai Avidan and Ariel Shamir. 2007. Seam carving for content-aware image resizing. In ACM SIGGRAPH 2007 (SIGGRAPH '07). ACM, New York, NY, USA,

http://doi.acm.org/10.1145/1275808.1276390

(55)

(56)

Programmazione Dinamica 56

https://en.wikipedia.org/wiki/Seam_carving

Scaling Cropping Seam Carving

(57)

Seam Carving

●

L'immagine viene ridimensionata togliendo cuciture

●

Una cucitura (seam) è un cammino composto da pixel adiacenti di “minima importanza”

– Se l'immagine ha M righe per N colonne, una cucitura

(verticale) è una sequenza di M pixel adiacenti, uno per ogni riga

(58)

Seam Carving

●

Assegnare ad ogni pixel (i, j) un peso E[i, j]  [0, 1] che denota quanto il pixel è “importante”

– Es.: quanto un pixel è “diverso” da quelli adiacenti

– 0 = non importante, 1 = molto importante

●

Determinare una cucitura verticale di peso minimo

●

Rimuovere i pixel della cucitura,

ottenendo una immagine M  (N – 1)

●

Ripetere il procedimento fino ad ottenere la larghezza desiderata.

0.1 0.0 0.2 0.9 0.8 0.9 0.2 0.8 0.4 0.7 0.8 0.8 0.1 0.7 0.8 0.1 0.0 0.6 0.5 0.7

0.1 0.2 0.9 0.8 0.9 0.8 0.4 0.7 0.8 0.8 0.7 0.8 0.1 0.6 0.5 0.7

(59)

Esempio

Immagine originale Pesi (nero=0, bianco=1) Alcune cuciture di peso minimo

(60)

Determinare le cuciture di peso minimo con la programmazione dinamica

●

Definizione dei sottoproblemi P(i, j)

– Determinare una cucitura di peso minimo che termina nel pixel di coordinate (i, j)

●

Definizione delle soluzioni W[i, j]

– Minimo peso tra tutte le possibili cuciture che terminano nel pixel di coordinate (i, j)

●

Calcolo della soluzione del problema originario

– La cucitura di peso minimo avrà peso pari al minimo tra { W[M, 1], … W[M, N] }

(61)

Calcolo di W[i, j]

●

Casi base (i = 1):

– W[1, j] = E[1, j] per ogni j = 1, … M

●

Caso generale (i > 1):

– Se j = 1

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

– Se 1 < j < N

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

– Se j = N

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

(62)

Esempio

0.1

0.1 0.0

0.0 0.2

0.2 0.9

0.9 0.8

0.8 0.9

0.9 0.2

0.2 0.8

0.8 0.4

0.6 0.7

1.5 0.8

1.0 0.8

1.0 0.1

0.3 0.7

1.3 0.8

1.4 0.1

1.1 0.0

0.3 0.6

0.9 0.5

0.8 0.7

2.0 E[i, j]

W[i, j]

Energia del pixel (i, j)

Minimo peso tra tutte le cuciture che iniziano sulla prima riga e terminano nel pixel (i, j)

(63)

Esempio

0.1

0.1 0.0

0.0 0.2

0.2 0.9

0.9 0.8

0.8 0.9

0.9 0.2

0.2 0.8

0.8 0.4

0.6 0.7

1.5 0.8

1.0 0.8

1.0 0.1

0.3 0.7

1.3 0.8

1.4 0.1

1.1 0.0

0.3 0.6

0.9 0.5

0.8 0.7

2.0 E[i, j]

W[i, j]

(64)

Distanza di Levenshtein

(65)

●

I correttori ortografici sono in grado di suggerire le

parole corrette più simili a quello che abbiamo digitato

●

Come si fa a decidere quanto “simili” sono due stringhe (=sequenze di caratteri) ?

Introduzione

(66)

Distanza di Levenshtein

●

Basata sul concetto di “edit distance”

– Numero di operazioni di “editing” che sono necessarie per trasformare una stringa S in una nuova stringa T

●

Trasformazioni ammesse

– Lasciare immutato il carattere corrente (costo 0)

– Cancellare un carattere (costo 1)

– Inserire un carattere (costo 1)

– Sostituire il carattere corrente con uno diverso (costo 1)

●

Dopo ciascuna operazione ci si sposta sul carattere successivo

– Si inizia dal primo carattere di S

(67)

Esempio

●

Trasformiamo “ALBERO” in “LIBRO”

– Una possibilità è cancellare tutti i caratteri di “ALBERO” e inserire tutti quelli di “LIBRO”

– Costo totale: 6 cancellazioni + 5 inserimenti = 11

ALBERO → LBERO cancellazione A LBERO → BERO cancellazione L

BERO → ERO cancellazione B

ERO → RO cancellazione E

RO → O cancellazione R

O → cancellazione O

→ L inserimento L

L → LI inserimento I

(68)

Esempio

●

Possiamo ottenere lo stesso risultato con un costo inferiore

– 2 cancellazioni + 1 inserimento = 3

ALBERO → LBERO cancello A

LBERO → LBERO lascio immutato LBERO → LIBERO inserisco I

LIBERO → LIBERO lascio immutato LIBERO → LIBRO cancello E

(69)

Definizione

●

Due stringhe S[1..n] e T[1..m] di n ed m caratteri, rispettivamente

– Una o entrambe potrebbero anche essere vuote.

●

La distanza di Levenshtein tra S[1..n] e T[1..m] è il costo minimo tra tutte le sequenze di operazioni di editing che trasformano S in T

●

Alcune definizioni aggiuntive

– S[1..i] la stringa composta dai primi i caratteri di S

● se i = 0 è la sottostringa vuota

(70)

Determinare la distanza di Levenshtein con la progreammazione dinamica

●

Definizione dei sottoproblemi P(i, j)

– Determinare il minimo numero di operazioni di editing

necessarie per trasformare il prefisso S[1..i] di S nel prefisso T[1..j] di T

●

Definizione delle soluzioni L[i, j]

– minimo numero di operazioni di editing necessarie per trasformare il prefisso S[1..i] di S nel prefisso T[1..j] di T

●

Calcolo della soluzione del problema originario

– La distanza di Levenshtein tra S[1..n] e T[1..m] è il valore L[n, m]

(71)

Calcolo di L[i, j]

●

Se i = 0 oppure j = 0

– Il costo per trasformare una stringa vuota in una non vuota è dato dalla lunghezza della stringa non vuota (occorre inserire i

caratteri necessari)

●

Se i > 0 e j > 0, il minimo costo tra:

– Trasformare S[1..i - 1] in T[1..j], e cancellare l'ultimo carattere S[i] di S

– Trasformare S[1..i] in T[1..j - 1] e inserire l'ultimo carattere T[j] di T

S T

S[1..i-1]

T[1..j]

S[1..i]

T[1..j-1]

(72)

Calcolo di L[i, j]

●

Se i = 0 oppure j = 0

– L[i, j] = max { i, j }

●

Altrimenti

– Se S[i] = T[j]

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

– Se S[i] != T[j]

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

Costo per trasformare S[1..i-1] in T[1..j], e cancellare il carattere S[i]

Costo per trasformare S[1..i] in T[1..j- 1], e aggiungere il carattere T[j]

Costo per trasformare S[1..i- 1] in T[1..j-1], e lasciare invariato l'ultimo carattere

(73)

Esempio

“” A L B E R O

“” 0 1 2 3 4 5 6

L 1 1 1 2 3 4 5

I 2 2 2 2 3 4 5

B 3 3 3 2 3 4 5

R 4 4 4 3 3 3 4

O 5 5 5 4 4 4 3

(74)

Conclusioni

●

La programmazione dinamica è una tecnica algoritmica estremamente potente

●

Va pero' applicata (dove applicabile) con disciplina

– Identificare i sottoproblemi

– Definire le soluzioni dei sottoproblemi

– Calcolare le soluzioni nei casi semplici

– Calcolare le soluzioni nel caso generale

Tecniche Algoritmiche/3 Tecniche Algoritmiche/3 Programmazione Dinamica Programmazione Dinamica