Algoritmi e Strutture Dati (Mod. B) Programmazione Dinamica (Parte III)

32
Algoritmi e Strutture Dati (Mod. B) Programmazione Dinamica (Parte III)

Transcript of Algoritmi e Strutture Dati (Mod. B) Programmazione Dinamica (Parte III)

Page 1: Algoritmi e Strutture Dati (Mod. B) Programmazione Dinamica (Parte III)

Algoritmi e Strutture Dati (Mod. B)

Programmazione Dinamica

(Parte III)

Page 2: Algoritmi e Strutture Dati (Mod. B) Programmazione Dinamica (Parte III)

Sottosequenza

Una sequenza S’=(a1,…,am) è una sotto-sequenza della sequenza S se S’ è ottenuta da S rimuovendo uno o più elementi.

Gli elementi rimanenti devono comparire nello stesso ordine nella sequenza risultante, anche se non devono essere necessariamente conti-gui in S.

• La sequenza nulla (di lunghezza 0) è una sottosequenza di ogni sequenza.

• Una sequenza è una lista di elementi ma….• … una sottosequenza non è necessariamente

una sottolista (poiché deve essere contigua).

Page 3: Algoritmi e Strutture Dati (Mod. B) Programmazione Dinamica (Parte III)

Sottosequenza più lunga comune

Definizione: Date due sequenze S1=(a1,…,am) e S2=(b1,…,bn), una sottosequenza comune Z di S1 e S2 è una sequenza che è sottosequenza di entrambe le sequenze S1 e S2.

Definizione: Date due sequenze S1=(a1,…,am) e S2=(b1,…,bn), la più lunga sottosequenza comune Z (LCS) di S1 e S2 è la sottosequenza comune di S1 e S2 che ha lungezza massima.

Page 4: Algoritmi e Strutture Dati (Mod. B) Programmazione Dinamica (Parte III)

Sottosequenza più lunga comune

• Input• 2 sequenze di simboli, S1 e S2

• Output• Trovare la più lunga sottosequenza comune (LCS)

di S1 e S2

Esempio

S1 = AAAATTGA S2 = TAACGATA

LCS[S1,S2] = AAATA

Page 5: Algoritmi e Strutture Dati (Mod. B) Programmazione Dinamica (Parte III)

Soluzione esaustivaLCS-Esaustivo(X[],Y[]: array di char) l = 0 LCS = Nil /* Enumera tutte le sottosequenza di X */ for each “sottosequenza K di X” do if “K è una sottosequenza di Y” then ls = lunghezza[K] if ls > l then l = ls LCS = K return LCS

Miglioramento possibile:Se lunghezza[Y] < lunghezza[X] enumera solo le sotto-sequenze di lunghezza minore o uguale a lunghezza[Y].

Page 6: Algoritmi e Strutture Dati (Mod. B) Programmazione Dinamica (Parte III)

Soluzione esaustivaMa data una sequenza di lunghezza n, quante

sono le possibili sottosequenze?

Ogni sottosequenza può avere lunghezza k con 0 k n.

Cioè il numero di sottosequenze è pari al numero di possibili sottoinsiemi di elementi distinti di un insieme degli n elementi nella sequenza originaria

n

k k

n

0)2( n Soluzione

impraticabile!

Page 7: Algoritmi e Strutture Dati (Mod. B) Programmazione Dinamica (Parte III)

Carattedizzazione della soluzione ottima

Iniziamo col caratterrizzare la struttura della soluzione ottima.

Data una sequenza X=(x1,…,xn), denoteremo con Xi, l’i-esimo prefisso di X, cioè la sotto-sequenza (x1,…,xi). X0 denota la sotto-sequenza nulla.

Esempio:• X = ABDCCAABD

• X3 = ABD

• X6 = ABDCCA

Page 8: Algoritmi e Strutture Dati (Mod. B) Programmazione Dinamica (Parte III)

X[1,…,m-1]

Y[1,…,n-1]

Z[1,…,k-1]

XX

X

X[1,…,m]Y[1,…,n]

Z[1,…,k]

YX[1,…,m]Y[1,…,n]

X

?Z[1,…,k]

X[1,…,m-1]Y[1,…,n] Y

?Z[1,…,k]

YX[1,…,m]Y[1,…,n]

X

?Z[1,…,k]

X[1,…,m]

Y[1,…,n-1]X

?Z[1,…,k]

2) xm yn e zk xm

3) xm yn e zk ym

1) xm= yn

Page 9: Algoritmi e Strutture Dati (Mod. B) Programmazione Dinamica (Parte III)

Carattedizzazione della soluzione ottima

Teorema: Date le due sequenze X=(x1,…,xm) e Y=(y1,…,yn), sia Z=(z1,…,zk) una LCS di X e Y. 1 se xm= yn, allora zk = xn = yn e Zk-1 è una LCS di Xm-1 e

Yn-1.2 se xm yn e zk xm, allora Z è una LCS di Xm-1 e Y.3 se xm yn e zk yn, allora Z è una LCS di X e Yn-1.

Page 10: Algoritmi e Strutture Dati (Mod. B) Programmazione Dinamica (Parte III)

Carattedizzazione della soluzione ottima

Teorema: Date le due sequenze X=(x1,…,xm) e Y=(y1,…,yn), sia Z=(z1,…,zk) una LCS di X e Y. 1 se xm= yn, allora zk = xm = yn e Zk-1 è una LCS di Xm-1 e Yn-1.2 se xm yn e zk xm, allora Z è una LCS di Xm-1 e Y.3 se xm yn e zk yn, allora Z è una LCS di X e Yn-1.

Dimostrazione: 1 Suponiamo xm= yn ma zk xm.

Poiché Z è una sottosequenza comune di X e Y di lunghezza k,

Ma allora concatenando xm a Z otterremmo una sotto-sequenza comune di X e Y di lunghezza k+1.

Questo però contraddice l’assunzione che Z sia una LCS di X e Y.

Quindi deve essere zk = xm = yn

Page 11: Algoritmi e Strutture Dati (Mod. B) Programmazione Dinamica (Parte III)

Carattedizzazione della soluzione ottima

Teorema: Date le due sequenze X=(x1,…,xm) e Y=(y1,…,yn), sia Z=(z1,…,zk) una LCS di X e Y. 1 se xm= yn, allora zk = xm = yn e Zk-1 è una LCS di Xm-1 e Yn-1.2 se xm yn e zk xm, allora Z è una LCS di Xm-1 e Y.3 se xm yn e zk yn, allora Z è una LCS di X e Yn-1.

Dimostrazione: Quindi deve essere zk = xm = yn

Ma allora eliminando dalle 3 sequenze l’ultimo carattere, otteniamo che Zk-1 deve essere una sottosequenza comune di Xm-1 e Yn-1 di lunghezza k-1

Ma Zk-1 è anche una LCS di Xm-1 e Yn-1?(Per assurdo) Supponiamo che esista una sottosequenza comune

W di Xm-1 e Yn-1 di lunghezza maggiore di k-1.

Allora concatenando zk a W otterremmo ancora una sotto-sequenza comune più lunga di Z, contraddicendo l’ipotesi.

Page 12: Algoritmi e Strutture Dati (Mod. B) Programmazione Dinamica (Parte III)

Carattedizzazione della soluzione ottima

Teorema: Date le due sequenze X=(x1,…,xm) e Y=(y1,…,yn), sia Z=(z1,…,zk) una LCS di X e Y. 1 se xm= yn, allora zk = xm = yn e Zk-1 è una LCS di Xm-1 e Yn-1.2 se xm yn e zk xm, allora Z è una LCS di Xm-1 e Y.3 se xm yn e zk yn, allora Z è una LCS di X e Yn-1.

Dimostrazione: 2 Se xm yn e zk xm, allora Z è una LCS di Xm-1 e Yn

Infatti, se esistesse una sottosequenza comune W di Xm-1 e Y di lunghezza maggiore di k, allora (essendo xm yn e zk xm) W sarebbe pure una sottosequenza comune di Xm e Y.

Ma questo contraddice l’ipotesi che Z sia una LCS di X e Y. 3 Se xm yn e zk ym, allora Z è una LCS di X e Yn-1

La dimostrazione è simmetrica a quella del punto 2

Page 13: Algoritmi e Strutture Dati (Mod. B) Programmazione Dinamica (Parte III)

Definizione ricorsiva della soluzione ottima

• c(i,j) = lunghezza della LCS di Xi e Yj.

• Vogliamo trovare c(m,n) dove m e n sono le lunghezze di X e Y, rispettivamente.

c(i,j) = 0 se i=0 o j=0

c(i,j) = ? se i,j 0

Page 14: Algoritmi e Strutture Dati (Mod. B) Programmazione Dinamica (Parte III)

c(i,j) = c(i-1,j-1) + 1 se i,j > 0 e xi = yj

c(i,j) = max { c(i-1,j), c(i,j-1) } se i,j > 0 e xi yj

XX

X

X[1,…,i]Y[1,…,j]

X[1,…,i-1]

Y[1,…,j-1]

Z[1,…,k] Z[1,…,k-1]

1) xm= yn

YX[1,…,i]Y[1,…,j]

X[1,…,i-1]Y[1,…,j]

XY

? ?Z[1,…,k] Z[1,…,k]

2) xm yn e zk xm

YX[1,…,i]Y[1,…,j]

X[1,…,i]

Y[1,…,j-1]XX

? ?Z[1,…,k]Z[1,…,k]

3) xm yn e zk ym

Page 15: Algoritmi e Strutture Dati (Mod. B) Programmazione Dinamica (Parte III)

Definizione ricorsiva della soluzione ottima

• c(i,j) = lunghezza della LCS di Xi e Yj.

• Vogliamo trovare c(m,n) dove m e n sono le lunghezze di X e Y, rispettivamente.

ji

ji

yxejisejicjic

yxejisejic

jise

jic

],1[],1,[max

1]1,1[

0

),(

Page 16: Algoritmi e Strutture Dati (Mod. B) Programmazione Dinamica (Parte III)

Definizione ricorsiva della soluzione ottima

RLCS-length(X[]Y[]:array of char;i,j:intero) if i = 0 or j = 0 then return 0 else if X[i] Y[j] then return max(RLCS-length(X,Y,i,j-1), RLCS-length(X,Y,i -1,j)) else return 1 + RLCS-length(b,X,i-1,j-1)

Page 17: Algoritmi e Strutture Dati (Mod. B) Programmazione Dinamica (Parte III)

Definizione ricorsiva della soluzione ottima

i,j

i,j-1 i-1,j

i,j-2 i-1,j-1 i-1,j-1 i-2,j

i,j-3 i-1,j-2 i-1,j-2 i-2,j-2 i-1,j-2 i-2,j-1 i-2,j-1 i-3,j

i-1,j-3 i-2,j-2 i-2,j-2 i-3,j-1i-1,j-3 i-2,j-2

Page 18: Algoritmi e Strutture Dati (Mod. B) Programmazione Dinamica (Parte III)

Calcolo del valore della soluzione ottima

Utilizziamo due tabelle di dimensione mn

c[i,j] conterrà il valore della lunghezza della massima sottosequenza comune dei prefissi Xi e Yj. • c[m,n] conterrà quindi lunghezza della massima

sottosequenza comune di X e Y.

b[i,j] conterrà un “puntatore” alla entry della tabella stessa che identifica il sottoproblema ottimo scelto durante il calcolo del valore c[i,j].

• i valori possibili saranno , e

Page 19: Algoritmi e Strutture Dati (Mod. B) Programmazione Dinamica (Parte III)

Calcolo del valore della soluzione ottima

Utilizziamo due tabelle di dimensione mn

b[i,j] conterrà un “puntatore” alla entry della tabella stessa che identifica il sottoproblema ottimo scelto durante il calcolo del valore c[i,j].

• i valori possibili saranno , e punta alla cella con indici i-1,j-1 punta alla cella con indici i-1,j punta alla cella con indici i,j-1

Page 20: Algoritmi e Strutture Dati (Mod. B) Programmazione Dinamica (Parte III)

0000000

0

0

0

0

0

0

T6

B5

C4

C3

A2

T1

0

0

DBCBTA

654321 j

i• TACCBT

• ATBCBD

c(i,j) = 0 se i=0 o j=0c(i,j) = c(i-1,j-1) + 1 se i,j > 0 e xi = yj

c(i,j) = max{ c(i-1,j), c(i,j-1) } se i,j > 0 e xi yj

111110

111111

222111

222111

332211

332221

punta a i-1,j-1 punta a i-1,j punta a i,j-1

Page 21: Algoritmi e Strutture Dati (Mod. B) Programmazione Dinamica (Parte III)

• ABDDBE• BEBEDE

000000

111111

221111

221111

222211

333221

0 0000000

0

0

0

0

0

0

0

E6

B5

D4

D3

B2

A1

EDEBEB

654321 j

i

punta a i-1,j-1 punta a i-1,j punta a i,j-1

c(i,j) = 0 se i=0 o j=0c(i,j) = c(i-1,j-1) + 1 se i,j > 0 e xi = yj

c(i,j) = max{ c(i-1,j), c(i,j-1) } se i,j > 0 e xi yj

Page 22: Algoritmi e Strutture Dati (Mod. B) Programmazione Dinamica (Parte III)

Calcolo del valore della soluzione ottimaLCS-Length(X[],Y[]: array of char) m = lunghezza[X] n = lunghezza[Y] for i = 1 to m do c[i,0] = 0 for j = 1 to n do c[0,j] = 0 for i = 1 to m do for j = 1 to n do if xi = yj

then c[i,j]=1+c[i-1,j-1] b[i,j] = “” else if c[i-1,j] c[i,j-1] then c[i,j] = c[i-1,j] b[i,j] = “”

else c[i,j] = c[i,j-1] b[i,j] = “” return b e c

Inizalizzazione prima rigae prima colonna della marice

I carattri finali di Xj e Yj sono identici!

I caratteri finali diversi

• LCS di Xj-1 e Yj è non

peggiore• LCS di Xj e Yj -1 è

migliore

Page 23: Algoritmi e Strutture Dati (Mod. B) Programmazione Dinamica (Parte III)

Calcolo del valore della soluzione ottimaLCS-Length(X[],Y[]: array of char) m = lunghezza[X] n = lunghezza[Y] for i = 1 to m do c[i,0] = 0 for j = 1 to n do c[0,j] = 0 for i = 1 to m do for j = 1 to n do if xi = yj

then c[i,j]=1+c[i-1,j-1] b[i,j] = “” else if c[i-1,j] c[i,j-1] then c[i,j] = c[i-1,j] b[i,j] = “”

else c[i,j] = c[i,j-1] b[i,j] = “” return b e c

(m+n)

(nm)

(n)

Page 24: Algoritmi e Strutture Dati (Mod. B) Programmazione Dinamica (Parte III)

Costruzione della soluzione ottima

Per costruire la LCS possiamo quindi utilizzare la tabella b[i,j] che contiene i “puntatori” ai sottoproblemi ottimi per ogni coppia di indici i e j.

Partiamo dalla entry b[m,n] e procediamo a ritroso seguendo le “frecce” della tabella.

Ricordate che LCS-Length assegna b[i,j] = solo quando xi = yj .

Quindi, partendo dalla fine della tabella, ogni volta che in b[i,j] troviamo sappiamo che xi (=yj) è contenuto nella LCS che cerchiamo.

I valori vengono stampati nell’ordine corretto.

Page 25: Algoritmi e Strutture Dati (Mod. B) Programmazione Dinamica (Parte III)

Costruzione della soluzione ottima

Print-LCS(b[]: array;X[]: array;i,j: intero) if i = 0 or j = 0 then return if b[i,j] = ”” then Print-LCS(b,X,i-1,j-1) print xi

else if b[i,j] = ”” then Print-LCS(b,X,i-1,j) else Print-LCS(b,X,i,j-1)

Page 26: Algoritmi e Strutture Dati (Mod. B) Programmazione Dinamica (Parte III)

0000000

0

0

0

0

0

0

T6

B5

C4

C3

A2

T1

0

0

DBCBTA

654321 j

i• TACCBT

• ATBCBD

111110

111111

222111

222111

332211

332221

c(i,j) = 0 se i=0 o j=0c(i,j) = c(i-1,j-1) + 1 se i,j > 0 e xi = yj

c(i,j) = max{ c(i-1,j), c(i,j-1) } se i,j > 0 e xi yj

Page 27: Algoritmi e Strutture Dati (Mod. B) Programmazione Dinamica (Parte III)

00000000

0

0

0

0

0

0

0

T6

B5

C4

C3

A2

T1

DBCBTA

654321 j

i

111110

111111

222111

222111

332211

332221

• TCB

T C B • TACCBT

• ATBCBD

c(i,j) = 0 se i=0 o j=0c(i,j) = c(i-1,j-1) + 1 se i,j > 0 e xi = yj

c(i,j) = max{ c(i-1,j), c(i,j-1) } se i,j > 0 e xi yj

Page 28: Algoritmi e Strutture Dati (Mod. B) Programmazione Dinamica (Parte III)

• ABDDBE• BEBEDE

000000

111111

221111

221111

222211

333221

0 0000000

0

0

0

0

0

0

0

E6

B5

D4

D3

B2

A1

EDEBEB

654321 j

i

c(i,j) = 0 se i=0 o j=0c(i,j) = c(i-1,j-1) + 1 se i,j > 0 e xi = yj

c(i,j) = max{ c(i-1,j), c(i,j-1) } se i,j > 0 e xi yj

Page 29: Algoritmi e Strutture Dati (Mod. B) Programmazione Dinamica (Parte III)

00000000

0

0

E6

B5

D4

D3

B2

A1

EDEBEB

654321 j

i

000000

0

0

0

0

0 111111

221111

221111

222211

333221

• BDE

B D E

• ABDDBE• BEBEDE

c(i,j) = 0 se i=0 o j=0c(i,j) = c(i-1,j-1) + 1 se i,j > 0 e xi = yj

c(i,j) = max{ c(i-1,j), c(i,j-1) } se i,j > 0 e xi yj

Page 30: Algoritmi e Strutture Dati (Mod. B) Programmazione Dinamica (Parte III)

Costruzione della soluzione ottima

Print-LCS(b[]: array;X[]: array;i,j: intero) if i = 0 or j = 0 then return if b[i,j] = ”” then Print-LCS(b,X,i-1,j-1) print xi

else if b[i,j] = ”” then Print-LCS(b,X,i-1,j) else Print-LCS(b,X,i,j-1)

Poiché ad ogni passo della ricorsione almeno uno tra i e j viene decrementato, il tempo di esecuzione è pari alla somma delle lunghezze delle due sequenze: (m+n)

Page 31: Algoritmi e Strutture Dati (Mod. B) Programmazione Dinamica (Parte III)

Ottimizzazioni possibili

La tabella b[i,j] può essere eliminata, risparmia-ndo un . Il valore di c[i,j] dipende solo dai valori c[i-1,j-1], c[i,j-1] e

c[i-1,j]. In tempo costante si può quindi determinare quale di questi tre è stato usato, e perchò quale sia il tipo di freccia. (Esercizio 16.3-2)

Se ci serve solo calcolare la lunghezza della LCS, possiamo ancora ridurre lo spazio della tabella c[i,j] a due sole righe di lunghezza min{ n , m }Ad ogni istante (cioè per ogni coppia i,j), ci servono i

valori c[i-1,j-1], c[i,j-1] e c[i-1,j], che stanno nella riga corrente e in quella precedente. (Esercizio 16.3-4)

Page 32: Algoritmi e Strutture Dati (Mod. B) Programmazione Dinamica (Parte III)

Esercizi

Esercizi:

• 16.3-2

• 16.3-3

• 16.3-4

Problemi:

• 16.2

• 16.3

• 16.4