Algoritmi e Strutture Dati (Mod. B)
Programmazione Dinamica
(Parte III)
Sottosequenza
Una sequenza S’=(a1,…,am) è una sottosequenza 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 contigui 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 esaustiva
LCS-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 sottosequenze di lunghezza minore o uguale a lunghezza[Y].
Soluzione esaustiva
Ma 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 0 
n
 (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 sottosequenza (x1,…,xi). X0 denota la sottosequenza nulla.
Esempio:
• X = ABDCCAABD
• X3 = ABD
• X6 = ABDCCA
1) xm= yn
X[1,…,m]
Y[1,…,n]
X
X
Z[1,…,k]
X[1,…,m-1]
Y[1,…,n-1]
Z[1,…,k-1]
X
2) xm  yn e zk  xm
X[1,…,m]
Y[1,…,n]
X
Y
Z[1,…,k]
X[1,…,m-1]
Y[1,…,n]
Y
Z[1,…,k]
?
?
3) xm  yn e zk  ym
X[1,…,m]
Y[1,…,n]
Z[1,…,k]
X
Y
?
X[1,…,m]
Y[1,…,n-1]
Z[1,…,k]
X
?
 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)
Y=(y1,…,yn), sia Z=(z1,…,zk) una LCS di X e Y.
e
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 sottosequenza 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)
Y=(y1,…,yn), sia Z=(z1,…,zk) una LCS di X e Y.
e
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 sottosequenza comune più lunga di Z, contraddicendo l’ipotesi.
 Carattedizzazione della soluzione ottima
Teorema: Date le due sequenze X=(x1,…,xm)
Y=(y1,…,yn), sia Z=(z1,…,zk) una LCS di X e Y.
e
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
1) xm= yn
X[1,…,i]
Y[1,…,j]
X
X
Z[1,…,k]
X[1,…,i-1]
Y[1,…,j-1]
Z[1,…,k-1]
X
c(i,j) = c(i-1,j-1) + 1 se i,j > 0 e xi = yj
2) xm  yn e zk  xm
X[1,…,i]
Y[1,…,j]
X
Y
Z[1,…,k]
X[1,…,i-1]
Y[1,…,j]
Y
Z[1,…,k]
?
?
3) xm  yn e zk  ym
X[1,…,i]
Y[1,…,j]
Z[1,…,k]
X
Y
?
X[1,…,i]
Y[1,…,j-1]
Z[1,…,k]
X
?
c(i,j) = max { c(i-1,j), c(i,j-1) } se i,j > 0 e xi  yj
 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.
0
se i  j

c( i , j )  c[i  1, j  1]  1
se i  j e x i  y j
max c[i , j  1], c[i  1, j ] se i  j e x  y
i
j

 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-1,j
i,j-1
i,j-2
i,j-3
i-1,j-2
i-1,j-3
i-1,j-2 i-2,j-2
i-2,j-2
i-2,j
i-1,j-1
i-1,j-1
i-1,j-2
i-2,j-1
i-1,j-3 i-2,j-2
i-2,j-1
i-3,j
i-2,j-2 i-3,j-1
 Calcolo del valore della soluzione ottima
Utilizziamo due tabelle di dimensione mn
 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 mn
 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
• TACCBT
• ATBCBD
j
i
0
 punta a i-1,j-1
 punta a i-1,j
 punta a i,j-1
0
1
2
3
4
5
6
A
T
B
C
B
D
0
0
0
0
0
0
0
1
T
0
0
1
1
1
1
1
2
A
0
1
1
1
1
1
1
3
C
0
1
1
1
2
2
2
4
C
0
1
1
1
2
2
2
5
B
0
1
1
2
2
3
3
6
T
0
1
2
2
2
3
3
c(i,j) = 0
c(i,j) = c(i-1,j-1) + 1
c(i,j) = max{ c(i-1,j), c(i,j-1) }
se i=0 o j=0
se i,j > 0 e xi = yj
se i,j > 0 e xi  yj
• ABDDBE
• BEBEDE
j
0
i
0
 punta a i-1,j-1
 punta a i-1,j
 punta a i,j-1
1
A
2
B
3
D
4
D
5
B
6
E
c(i,j) = 0
c(i,j) = c(i-1,j-1) + 1
c(i,j) = max{ c(i-1,j), c(i,j-1) }
1
2
3
4
5
6
B
E
B
E
D
E
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
0
1
1
1
1
2
2
0
1
1
1
1
2
2
0
1
1
2
2
2
2
0
1
2
2
3
3
3
se i=0 o j=0
se i,j > 0 e xi = yj
se i,j > 0 e xi  yj
 Calcolo del valore della soluzione ottima
LCS-Length(X[],Y[]: array of char)
m = lunghezza[X]
Inizalizzazione prima riga
n = lunghezza[Y]
e prima colonna della marice
for i = 1 to m
do c[i,0] = 0
I carattri finali di Xj e Yj sono identici!
for j = 1 to n
I caratteri finali
do c[0,j] = 0
for i = 1 to m
diversi
do for j = 1 to n
• LCS di Xj-1 e Yj è
do if xi = yj
non peggiore
then c[i,j]=1+c[i-1,j-1]
• LCS di Xj e Yj -1 è
b[i,j] = “”
migliore
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
 Calcolo del valore della soluzione ottima
LCS-Length(X[],Y[]: array of char)
m = lunghezza[X]
(m+n)
n = lunghezza[Y]
for i = 1 to m
do c[i,0] = 0
for j = 1 to n
(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
(nm)
 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)
• TACCBT
• ATBCBD
j
0
i
0
1
2
3
4
5
6
A
T
B
C
B
D
0
0
0
0
0
0
0
1
T
0
0
1
1
1
1
1
2
A
0
1
1
1
1
1
1
3
C
0
1
1
1
2
2
2
4
C
0
1
1
1
2
2
2
5
B
0
1
1
2
2
3
3
6
T
0
1
2
2
2
3
3
c(i,j) = 0
c(i,j) = c(i-1,j-1) + 1
c(i,j) = max{ c(i-1,j), c(i,j-1) }
se i=0 o j=0
se i,j > 0 e xi = yj
se i,j > 0 e xi  yj
• TACCBT
• ATBCBD
• TCB
j
0
i
0
1
2
3
4
5
6
A
T
B
C
B
D
0
0
0
0
0
0
0
1
T
0
0
1
1
1
1
1
2
A
0
1
1
1
1
1
1
3
C
0
1
1
1
2
2
2
4
C
0
1
1
1
2
2
2
5
B
0
1
1
2
2
3
3
6
T
0
1
2
2
2
3
3
c(i,j) = 0
c(i,j) = c(i-1,j-1) + 1
c(i,j) = max{ c(i-1,j), c(i,j-1) }
se i=0 o j=0
se i,j > 0 e xi = yj
se i,j > 0 e xi  yj
• ABDDBE
• BEBEDE
j
0
i
0
1
A
2
B
3
D
4
D
5
B
6
E
c(i,j) = 0
c(i,j) = c(i-1,j-1) + 1
c(i,j) = max{ c(i-1,j), c(i,j-1) }
1
2
3
4
5
6
B
E
B
E
D
E
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
0
1
1
1
1
2
2
0
1
1
1
1
2
2
0
1
1
2
2
2
2
0
1
2
2
3
3
3
se i=0 o j=0
se i,j > 0 e xi = yj
se i,j > 0 e xi  yj
• ABDDBE
• BEBEDE
j
0
i
0
• BDE
1
A
2
B
3
D
4
D
5
B
6
E
c(i,j) = 0
c(i,j) = c(i-1,j-1) + 1
c(i,j) = max{ c(i-1,j), c(i,j-1) }
1
2
3
4
5
6
B
E
B
E
D
E
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
0
1
1
1
1
2
2
0
1
1
1
1
2
2
0
1
1
2
2
2
2
0
1
2
2
3
3
3
se i=0 o j=0
se i,j > 0 e xi = yj
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