Algoritmi e Strutture Dati (Mod. B) Programmazione Dinamica (Parte III)
-
Upload
silvestro-bianco -
Category
Documents
-
view
216 -
download
1
Transcript of Algoritmi e Strutture Dati (Mod. B) Programmazione Dinamica (Parte III)
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).
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.
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
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].
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!
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
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
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.
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
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.
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
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
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
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
),(
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)
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
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
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
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
• 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
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
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)
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.
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)
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
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
• 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
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
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)
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)
Esercizi
Esercizi:
• 16.3-2
• 16.3-3
• 16.3-4
Problemi:
• 16.2
• 16.3
• 16.4