Algoritmi e Strutture Dati
Capitolo 13 - Programmazione dinamica
Alberto Montresor
Università di Trento
This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License. To view a
copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/2.5/ or send a letter to Creative
Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.
© Alberto Montresor
1
Programmazione dinamica
Divide-et-impera
✦
Tecnica ricorsiva
✦
Approccio top-down (problemi divisi in sottoproblemi)
✦
Vantaggioso solo quando i sottoproblemi sono indipendenti
✦
Altrimenti, gli stessi sottoproblemi possono venire risolti più volte
✦
Programmazione dinamica
✦
Tecnica iterativa
✦
Approccio bottom-up
✦
Vantaggiosa quando ci sono sottoproblemi in comune
✦
Esempio semplice: il triangolo di Tartaglia
✦
© Alberto Montresor
2
Coefficienti binomiali
Coefficienti binomiali
✦
Il numero di modi di scegliere k oggetti da un insieme di n oggetti
✦
I coefficienti di un’equazione di grado n
✦
© Alberto Montresor
3
Triangolo di Tartaglia
Versione ricorsiva
✦
Deriva direttamente dalla definizione
✦
Domanda
✦
Complessità?
✦
© Alberto Montresor
4
Triangolo di Tartaglia
Versione iterativa
✦
Basata su programmazione dinamica
✦
Domanda
✦
Complessità?
✦
© Alberto Montresor
5
Quando applicare la programmazione dinamica?
Sottostruttura ottima
✦
E' possibile combinare le soluzioni dei sottoproblemi per trovare la soluzione di un
problema più grande
✦
PS: In tempo polinomiale!
✦
Le decisioni prese per risolvere un problema rimangono valide quando esso diviene
un sottoproblema di un problema più grande
✦
Sottoproblemi ripetuti
✦
Un sottoproblema può occorrere più volte
✦
Spazio dei sottoproblemi
✦
Deve essere polinomiale
✦
© Alberto Montresor
6
Programmazione dinamica
Caratterizzare la struttura di una soluzione ottima
✦
Definire ricorsivamente il valore di una soluzione ottima
✦
La soluzione ottima ad un problema contiene le soluzioni ottime ai sottoproblemi
✦
Calcolare il valore di una soluzione ottima “bottom-up”
(cioè calcolando prima le soluzioni ai casi più semplici)
✦
Si usa una tabella per memorizzare le soluzioni dei sottoproblemi
✦
Evitare di ripetere il lavoro più volte, utilizzando la tabella
✦
Costruire la (una) soluzione ottima.
✦
© Alberto Montresor
7
Catena di moltiplicazione di matrici
Problema:
✦
Data una sequenza di matrici A1, A2, A3, …, An, compatibili 2 a 2 al prodotto,
vogliamo calcolare il loro prodotto.
✦
Cosa vogliamo ottimizzare
✦
La moltiplicazione di matrici si basa sulla moltiplicazione scalare come operazione
elementare.
✦
Vogliamo calcolare il prodotto impiegando il numero minore possibile di
moltiplicazioni
✦
Attenzione:
✦
Il prodotto di matrici non è commutativo...
✦
...ma è associativo: (A1 ⋅ A2) ⋅ A3 = A1 ⋅ (A2 ⋅ A3)
✦
© Alberto Montresor
8
Catena di moltiplicazione tra matrici
3 matrici:
✦
A
B
1x100
100x1
# Moltiplicazioni
Memoria
(A ⋅ B )
((A ⋅ B ) ⋅ C )
100×1×100 = 10000
100×100×1 = 10000
20000
10000
100
10100
(B ⋅ C)
(A ⋅ (B ⋅ C))
1×100×1
100×1×1
© Alberto Montresor
=
=
100
100
200
C
100x1
1
100
101
9
Catena di moltiplicazione tra matrici
4 matrici:
A
✦
B
C
D
50x10
10x40
40x30
30x5
((( A ⋅ B ) ⋅ C ) ⋅ D )
(( A ⋅ ( B ⋅ C )) ⋅ D )
(( A ⋅ B ) ⋅ ( C ⋅ D ))
( A ⋅ (( B ⋅ C ) ⋅ D ))
( A ⋅ ( B ⋅ ( C ⋅ D )))
: 87500 moltiplicazioni
: 34500 moltiplicazioni
: 36000 moltiplicazioni
: 16000 moltiplicazioni
: 10500 moltiplicazioni
((( A ⋅ B ) ⋅ C ) ⋅ D ) : 87500
© Alberto Montresor
(A⋅B)
20000
(( A ⋅ B ) ⋅ C )
60000
(( A ⋅ B ) ⋅ C ) ⋅ D
7500
50×10×40 =
50×40×30 =
50×30× 5 =
10
Applicare la programmazione dinamica
Le fasi principali:
✦
Caratterizzare la struttura di una soluzione ottima
✦
Definire ricorsivamente il valore di una soluzione ottima
✦
Calcolare il valore di una soluzione ottima “bottom-up”
(dal basso verso l’alto)
✦
Costruzione di una soluzione ottima
✦
Nei lucidi successivi:
✦
Vediamo ora una ad una le quattro fasi del processo di sviluppo applicate al
problema della parentesizzazione ottima
✦
© Alberto Montresor
11
Parentesizzazione
Definizione: Una parentesizzazione Pi,j del prodotto Ai · Ai+1 · · · Aj consiste
✦
nella matrice Ai, se i = j;
✦
nel prodotto di due parentesizzazioni
(Pi,k · Pk+1,j), altrimenti.
✦
(A1·(A2·A3 ))·(A4·(A5·A6 ))
Esempio:
✦
(A1·(A2·A3 )) · (A4·(A5·A6 )) →
k=3
(A1·(A2·A3 ))
(A4·(A5·A6 ))
✦
“Ultima moltiplicazione”
✦
A1
(A2·A3 )
A2
© Alberto Montresor
A3
A4
(A5·A6 )
A5
A6
12
Parentesizzazione ottima
Parentesizzazione ottima
✦
Determinare il numero di moltiplicazioni scalari necessari per i prodotti tra le
matrici in ogni parentesizzazione
✦
Scegliere una delle parentesizzazioni che richiedono il numero minimo di
moltiplicazioni
✦
Motivazione:
✦
Vale la pena di spendere un po' di tempo per cercare la parentesizzazione migliore,
per risparmiare tempo dopo
✦
Domanda
✦
Quante sono le parentesizzazioni possibili?
✦
n=3 → 2, n=4 → 5, n=5 → ???
✦
© Alberto Montresor
13
Parentesizzazione ottima
Definiamo una relazione di ricorrenza
✦
P(n): numero di parentesizzazioni per n matrici A1 · A2 · A3 ···An
✦
L'ultima moltiplicazione può occorrere in n-1 posizioni diverse
✦
Fissato l'indice k dell'ultima moltiplicazione, abbiamo
✦
P(k)
parentesizzazioni per A1 · A2 · A3 ··· Ak
✦
P(n-k) parentesizzazioni per Ak+1 · Ak+2 ··· An
✦
© Alberto Montresor
n
1
2
3
4
5
P(n)
1
1
2
5
14 42 132
6
7
8
9
10
429
1430
4862
14
Parentesizzazione ottima
Equazione di ricorrenza:
✦
Soluzione: n-1-esimo “numero catalano”
✦
Domanda: Più semplicemente, dimostrare che P(n) = Ω(2n)
✦
Conseguenza: la “forza bruta” (tentare tutte le possibili parentesizzazioni) non
funziona
✦
© Alberto Montresor
15
Definizioni
Denoteremo nel seguito con:
✦
A1 · A2 · A3 ··· An
✦
il prodotto di n matrici da ottimizzare
ci-1
il numero di righe della matrice Ai
ci
il numero di colonne della matrice Ai
A[i..j]
il prodotto Ai · Ai+1 ··· Aj
✦
✦
✦
P[i..j]
✦
© Alberto Montresor
una parentesizzazione di A[i..j]
(non necessariamente ottima)
16
Struttura di una parentesizzazione ottima
Sia A[i..j] = Ai · Ai+1 ··· Aj una sottosequenza del prodotto di matrici
✦
Si consideri una parentesizzazione ottima P[i..j] di A[i..j]
✦
Esiste una “ultima moltiplicazione”: in altre parole, esiste un indice k tale che
P[i..j] = P[i..k] · P[k+1..j]
✦
Domanda:
✦
Quali sono le caratteristiche
delle due sotto-parti P[i..k] e
P[k+1..j] ?
( P[i..k] ) · ( P[k+1..j] )
✦
© Alberto Montresor
P[i..k]
P[k+1..j]
?
?
17
Struttura di una parentesizzazione ottima
Teorema (sottostruttura ottima)
✦
Se P[i..j] = P[i..k] · P[k+1..j] è una parentesizzazione ottima del prodotto A[i..j],
allora P[i..k] e P[k+1..j] sono parentesizzazioni ottime dei prodotti A[i..k] e
A[k+1..j], rispettivamente.
✦
Dimostrazione
✦
Ragionamento per assurdo
✦
Supponiamo esista un parentesizzazione ottima P'[i..k] di A[i..k] con costo inferiore
a P[i..k]
✦
Allora, P'[i..k] · P[k+1..j] sarebbe una parentesizzazione di A[i..j] con costo
inferiore a P[i..j], assurdo.
✦
© Alberto Montresor
18
Struttura di una parentesizzazione ottima
In altre parole:
✦
Il teorema afferma che esiste una sottostruttura ottima:
✦
Ogni soluzione ottima al problema della parentesizzazione contiene al suo interno le
soluzioni ottime dei due sottoproblemi
Programmazione dinamica:
✦
L'esistenza di sottostrutture ottime è una delle caratteristiche da cercare per
decidere se la programmazione dinamica è applicabile
✦
Prossima fase:
✦
Definire ricorsivamente il costo di una soluzione ricorsiva
✦
© Alberto Montresor
19
Definire ricorsivamente il valore di una soluzione ottima
Definizione: sia M[i,j] il numero minimo di prodotti scalari richiesti per calcolare il
prodotto A[i,j]
✦
Come calcolare M[i,j]?
✦
Caso base: i=j . Allora, M[i,j] = 0
✦
Passo ricorsivo: i < j. Esiste una parentesizzazione ottima
P[i..j] = P[i..k] · P[k+1..j]; sfruttiamo la ricorsione:
✦
M[i,j] = M[i,k] + M[k+1,j] + ci-1 · ck · cj
Prodotti per
P[i..k]
© Alberto Montresor
Prodotti per
P[k+1..j]
Prodotto di una coppia
di matrici:
 n. righe: prima matrice
 n. colonne: ultima matrice
20
Definire ricorsivamente il valore di una soluzione ottima
Ma qual è il valore di k?
✦
Non lo conosciamo....
✦
... ma possiamo provarli tutti!
✦
k può assumere valori fra i e j-1
✦
La formula finale:
✦
M[i,j] = mini ≤ k < j { M[i,k] + M[k+1, j] + ci-1 · ck · cj }
✦
© Alberto Montresor
21
Esempio
Li \ R
j
1
1
2
3
4
5
2
-
0
3
-
-
0
4
-
-
-
0
5
-
-
-
-
0
6
-
-
-
-
-
6
0
0
M[1,2] = min1 ≤ k < 2 { M[1,k] + M[k+1,2] + c0ckc2 }
= M[1,1] + M[2,2] + c0c1c2
= c0 c1 c2
© Alberto Montresor
22
Esempio
Li \ R
j
1
1
2
3
4
5
2
-
0
3
-
-
0
4
-
-
-
0
5
-
-
-
-
0
6
-
-
-
-
-
6
0
0
M[2,4] = min2≤k<4{ M[2,k] + M[k+1,4] + c1ckc4 }
= min { M[2,2] + M[3,4] + c1c2c4,
M[2,3] + M[4,4] + c1c3c4 }
© Alberto Montresor
23
Esempio
Li \ R
j
1
1
2
3
4
5
2
-
0
3
-
-
0
4
-
-
-
0
5
-
-
-
-
0
6
-
-
-
-
-
6
0
0
M[2,5] = min2≤k<5{ M[2,k] + M[k+1,5] + c1ckc5 }
= min { M[2,2] + M[3,5] + c1c2c5,
M[2,3] + M[4,5] + c1c3c5,
M[2,4] + M[5,5] + c1c4c5 }
© Alberto Montresor
24
Esempio
Li \ R
j
1
1
2
3
4
5
2
-
0
3
-
-
0
4
-
-
-
0
5
-
-
-
-
0
6
-
-
-
-
-
6
0
0
M[1,5] = min1≤k<5{ M[1,k] + M[k+1,5] + c0ckc5 }
= min { M[1,1] + M[2,5] + c0c1c5 ,
M[1,2] + M[3,5] + c0c2c5 ,
M[1,3] + M[4,5] + c0c3c5 ,
M[1,4] + M[5,5] + c0c4c5 }
© Alberto Montresor
25
Esempio
Li \ R
j
1
1
2
3
4
5
2
-
0
3
-
-
0
4
-
-
-
0
5
-
-
-
-
0
6
-
-
-
-
-
6
0
0
M[1,6] = min1≤k<6{ M[1,k] + M[k+1,6] + c0ckc6 }
= min { M[1,1] + M[2,6] + c0c1c6 ,
M[1,2] + M[3,6] + c0c2c6 ,
M[1,3] + M[4,6] + c0c3c6 ,
M[1,4] + M[5,6] + c0c4c6 ,
M[1,5] + M[6,6] + c0c5c6 }
© Alberto Montresor
26
Calcolo “bottom-up” del valore della soluzione
Passiamo ora al terzo passo della programmazione dinamica:
✦
“calcolare in modo bottom-up il valore della soluzione ottima”
✦
Ma la definizione ricorsiva di M[i,j] suggerisce di utilizzare un approccio ricorsivo
top-down per risolvere il problema:
✦
Lanciamo il problema sulla sequenza completa [1,n]
✦
Il meccanismo ricorsivo individua i sottoproblemi da risolvere
✦
Proviamo... male non fa ;-)
✦
Input: un array c[0..n] con le dimensioni delle matrici,
✦c[0] è il numero di righe della prima matrice
✦
c[i] è il numero di colonne della matrice Ai
✦
© Alberto Montresor
27
Soluzione ricorsiva top-down

Domanda: Complessità risultante?
© Alberto Montresor
28
Critica all'approccio top-down
Alcune riflessioni
✦
La soluzione ricorsiva top-down è Ω(2n)
✦
Non è poi migliore dell'approccio basato su forza bruta!
✦
Qual è il problema?
✦
Il problema principale è che molti problemi vengono risolti più volte
✦
1…4
1…1
1…2
2…4
3…4
1…3
4…4
2…2 3…4 2…3 4…4 1…1 2…2 3…3 4…4 1…1 2…3 1…2 3…3
3…3
© Alberto Montresor
4…4
2…2
3…3
2…2
3…3 1…1
2…2
29
Calcolare la soluzione ottima in modo bottom-up
E' interessante notare che il numero di possibili problemi è molto inferiore a 2n
✦
uno per ogni scelta di i e j (con 1 ≤ i ≤ j ≤ n):
✦
Sottoproblemi
con i ≠ j
Ogni sottoproblema
✦
Sottoproblemi
con i = j
È risolvibile utilizzando le soluzioni dei sottoproblemi che sono state
eventualmente già calcolate e memorizzate nell'array
✦
Idea chiave della programmazione dinamica:
✦
Mai calcolare più di una volta la soluzione ad un sottoproblema
✦
© Alberto Montresor
30
Calcolare la soluzione ottima in modo bottom-up
L’algoritmo parentesizzazione()
✦
prende in ingresso un array c[0..n] con le dimensioni delle matrici
✦
c[0] è il numero di righe della A1
✦
c[i] è
✦
il numero di righe della matrice Ai+1
✦
il numero di colonne della matrice Ai
✦
utilizza (e ritorna) due matrici n·n ausiliarie:
✦
M[i,j] che contiene i costi minimi dei sottoproblemi A[i..j]
✦
S[i,j] che contiene il valore di k che minimizza il costo per il sottoproblema
✦
© Alberto Montresor
31
Algoritmo
h varia sulle diagonali sopra
quella principale
i e j assumono i valori delle
celle nella diagonale h
Calcola tutti i possibili valori e conserva solo il
più piccolo
© Alberto Montresor
L
1
2
3
4
5
6
1
0
2
3
4
5
6
0
0
0
0
32
0
M[ ]
Li \i Rj
1
1
2
3
4
5
6
i
ci
0
224
176
218
276
350
0
7
2
-
0
64
112
174
250
1
8
3
-
-
0
24
70
138
2
4
4
-
-
-
0
30
90
3
2
5
-
-
-
-
0
90
4
3
6
-
-
-
-
-
0
5
5
6
6
M[1,4] = min1 ≤ k ≤ 3{ M[1,k] + M[k+1,4] + c0ckc4 }
= min { M[1,1] + M[2,4] + c0c1c4,
M[1,2] + M[3,4] + c0c2c4,
M[1,3] + M[4,4] + c0c3c4 }
= min { 0 + 112 + 7 * 8 * 3,
224 + 24 + 7 * 4 * 3,
176 + 0 + 7 * 2 * 3 }
= min { 280, 332, 218 } = 218
© Alberto Montresor
33
Li \ Rj
1
S[ ]
2
3
4
5
6
1
2
3
4
5
6
i
ci
0
1
1
3
3
3
0
7
0
2
3
3
3
1
8
0
3
3
3
2
4
0
4
5
3
2
0
5
4
3
0
5
5
6
6
M[1,4] = min1 ≤ k ≤ 3{ M[1,k] + M[k+1,4] + c0ckc4 }
= min { M[1,1] + M[2,4] + c0c1c4,
M[1,2] + M[3,4] + c0c2c4,
M[1,3] + M[4,4] + c0c3c4 }
= min { 0 + 112 + 7 * 8 * 3,
224 + 24 + 7 * 4 * 3,
176 +
0 +7*2*3}
= min { 280, 332, 218 } = 218
© Alberto Montresor
34
Calcolare la soluzione ottima in modo bottom-up
Considerazioni sull'algoritmo
✦
Costo computazionale: O(n3)
✦
Nota
✦
Lo scopo della terza fase era “calcolare in modo bottom-up il valore della soluzione
ottima”
✦
Questo valore si trova in M[1,n]
✦
Per alcuni problemi
✦
E' anche necessario mostrare la soluzione trovata
✦
Per questo motivo registriamo informazioni sulla soluzione
mentre procediamo in maniera bottom-up
✦
© Alberto Montresor
35
Costruire una soluzione ottima
Possiamo definire un algoritmo che costruisce la soluzione a partire
dall'informazione calcolata da parentesizzazione().
✦
La matrice S ci permette di determinare il modo migliore di moltiplicare le matrici.
✦
S[i,j]=k contiene infatti il valore k su cui dobbiamo spezzare il prodotto A[i..j]
✦
Ci dice cioè che per calcolare A[i..j] dobbiamo prima calcolare
A[i..k] e A[k+1..j] e poi moltiplicarle tra loro.
✦
Ma questo è un processo facilmente realizzabile tramite un algoritmo ricorsivo
✦
© Alberto Montresor
36
Costruire una soluzione ottima
© Alberto Montresor
37
Costruire una soluzione ottima
© Alberto Montresor
38
Esempio di esecuzione
A1…6 = A1…k×Ak+1…6
= A1…3×A4…6
A1…3 = A1…k×Ak+1…3
=A1×A2…3
A4…6 = A4…k×Ak+1…6
=A4..5×A6
A2…3 = A2…k×Ak+1…3
= A2×A3
A4…5 = A4…k×Ak+1…5
=A4×A5
S[ ]
Li \ Rj
1
2
3
4
5
1
2
3
4
5
6
0
1
1
3
3
3
0
2
3
3
3
0
3
3
3
0
4
5
0
5
6
0
A1…6 = ( ( A1 (A2A3) )( (A4A5 ) A6) )
© Alberto Montresor
39
Numeri di Fibonacci
Definiti ricorsivamente
✦
F(0) = F(1) = 1
✦
F(n) = F(n-2)+F(n-1)
✦
Un po' di storia
✦
Leonardo di Pisa, detto Fibonacci
✦
Utilizzati per descrivere la crescita di una popolazione di conigli (!)
✦
In natura:
✦
Pigne, conchiglie, parte centrale dei girasoli, etc.
✦
In informatica:
✦
Alberi AVL minimi, Heap di Fibonacci, etc.
✦
© Alberto Montresor
40
Implementazione ricorsiva
Complessità computazionale
✦
Soluzione
✦
T(n) = O(2n)
✦
© Alberto Montresor
41
Implementazione iterativa
Complessità
✦
In tempo: O(n)
✦
In spazio: O(n)
✦
Array di n elementi
✦
n
0
1
2
3
4
5
6
f []
1
1
2
3
5
8
13 21
© Alberto Montresor
7
42
Implementazione iterativa - risparmio memoria
Complessità
✦
In tempo: O(n)
✦
In spazio: O(1)
✦
3 variabili
✦
n
0
1
2
3
4
5
6
7
F0
-
-
1
1
2
3
5
8
F1
1
1
1
2
3
5
8
13
F2
1
1
2
3
5
8
13 21
© Alberto Montresor
43
Zaino
Input
✦
Un intero positivo C - la capacità dello zaino
✦
n oggetti, tali che l’oggetto i-esimo è caratterizzato da:
✦
un profitto pi e
✦
un volume vi , entrambi interi positivi
✦
Problema
✦
trovare un sottoinsieme S di {1, . . . , n} di oggetti tale che il volume totale non
superi la capacità massima e il profitto totale sia massimo
✦
© Alberto Montresor
44
Zaino
Caratterizzazione del problema
✦
P(i, c) è il sottoproblema dato dai primi i oggetti da inserire in uno zaino con
capacità c
✦
Il problema originale corrisponde a P(n, C)
✦
Teorema - sottostruttura ottima
✦
Sia S(i, c) una soluzione ottima per il problema P(i, c)
✦
Possono darsi due casi:
✦
Se i ∈ S(i, c), allora S(i, c)-{i} è una soluzione ottima
per il sottoproblema P(i-1, c-vi )
✦
Se i ∉ S(i, c), allora S(i, c) è una soluzione ottima
per il sottoproblema P(i−1, c)
✦
Dimostrazione
✦
per assurdo
✦
© Alberto Montresor
45
Zaino
Tabella per programmazione dinamica
✦
D[i, c] contiene il profitto massimo ottenibile per il problema P(i,c)
✦
Alcune considerazioni
✦
Costo di un algoritmo di programmazione dinamica bottom-up: O(nC)
✦
Non è detto che tutti i problemi debbano essere risolti
✦
© Alberto Montresor
46
Memoization
Memoization (annotazione)
✦
Tecnica che fonde l'approccio di memorizzazione della programmazione dinamica
con l'approccio top-down di divide-et-impera
✦
Quando un sottoproblema viene risolto per la prima volta,
viene memorizzato in una tabella
✦
ogni volta che si deve risolvere un sotto-problema, si controlla nella tabella se è già
stato risolto precedentemente
✦
SI:
si usa il risultato della tabella
NO:
si calcola il risultato e lo si memorizza
✦
✦
In tal modo, ogni sottoproblema viene calcolato una sola volta e memorizzato
come nella versione bottom-up
✦
© Alberto Montresor
47
Zaino “annotato”
Note sulla soluzione
✦
⏊
✦
è un valore speciale per indicare che un certo problema non è stato risolto
Gli elementi della tabella D sono inizializzati con il valore ⏊
✦
© Alberto Montresor
48
Discussione su memoization
Caso pessimo
✦
Nel caso pessimo, è comunque O(nC)
✦
Quando si verifica?
✦
Inizializzazione
✦
E’ necessario inizializzare D - costo O(nC)
✦
Se il costo dell’inizializzazione è asintoticamente inferiore al costo di ricombinare i
risultati, si ottiene un guadagno
✦
Altrimenti: è possibile utilizzare una tabella hash
✦
Complessità pseudo-polinomiale
✦
La complessità O(nC) è polinomiale nella dimensione dell’input?
✦
© Alberto Montresor
49
Bioinformatica
DNA
✦
Una stringa di molecole chiamate basi
✦
Solo quattro basi: Adenina, Citosina, Guanina, Timina
✦
Esempi
✦
Due esempi di DNA: AAAATTGA, TAACGATAG
✦
Date due sequenze, è lecito chiedersi quanto siano “simili”
✦
Una è sottostringa dell'altra?
✦
Distanza di editing: costo necessario per trasformare una nell'altra
✦
La più lunga sottosequenza (anche non contigua) comune ad entrambe
✦
© Alberto Montresor
50
Caratterizzazione del problema
Definizione
✦
Una sequenza T è una sotto-sequenza di P se T è ottenuta da P rimuovendo uno o
più elementi
✦
Alternativamente: T è definito come il sottoinsieme degli indici l'insieme di
elementi di P che compaiono anche in T
✦
Gli elementi rimanenti devono comparire nello stesso ordine, anche se non devono
essere necessariamente contigui in P
✦
Esempio
✦
P = “AAAATTGA” , T = “AAATA”
✦
Nota
✦
La sequenza nulla è una sotto-sequenza di ogni sequenza
✦
© Alberto Montresor
51
Caratterizzazione del problema
Definizione:
✦
Date due sequenze P e T, una sequenza Z è una sottosequenza comune di P e T se Z
è sottosequenza sia di P che di T
✦
Scriviamo Z ∈ CS(P, T)
✦
“Common Subsequence”, o CS
✦
Definizione:
✦
Date due sequenze P e T, una sequenza è una sottosequenza comune massimale di P
e T, se Z ∈ CS(P, T) e non esiste una sequenza W ∈ CS(P, T) tale che |W| > |Z|
✦
Scriviamo Z ∈ LCS(P, T)
✦
“Longest Common Subsequence”, o LCS
✦
© Alberto Montresor
52
Caratterizzazione del problema
Problema LCS
✦
Input: due sequenze di simboli, P e T
✦
Output: Trovare la più lunga sottosequenza Z comune a P e T
✦
Esempio
✦
P = “AAAATTGA”
✦
T = “TAACGATA”
✦
LCS(P,T) = ????
✦
Prima di provare con la programmazione dinamica, proviamo di “forza bruta”...
✦
© Alberto Montresor
53
Risoluzione tramite enumerazione

Domanda: Quante sono le sotto-sequenze di P?
© Alberto Montresor
54
Caratterizzazione della soluzione ottima
Data una sequenza P=(p1, …, pn):
✦
denoteremo con P(i) l’i-esimo prefisso di P, cioè la sotto-sequenza ( p1, … , pi )
✦
Esempio:
✦
P = ABDCCAABD
✦
P(0) denota la sotto-sequenza nulla
✦
P(3) = ABD
✦
P(6) = ABDCCA
✦
© Alberto Montresor
55
Caratterizzazione della soluzione ottima
Teorema (Sottostruttura ottima)
✦
Date le due sequenze P=(p1,…, pm) e T=(t1, …, tn),
sia Z=(z1,…,zk ) una LCS di P e T
✦
1. pm= tn
→
zk = pm = tn e
Z(k-1) ∈ LCS( P(m-1),
T(n-1) )
2. pm ≠ tn e zk ≠ pm
→
Z ∈ LCS( P(m-1), T )
3. pm ≠ tn e zk ≠ tn
→
Z ∈ LCS( P, T(n-1) )
Dimostrazione
✦
© Alberto Montresor
56
Dimostrazione
Punto 1
✦
Supponiamo per assurdo che zk ≠ pm = tn
✦
Si consideri W=Zpm. Allora W ∈ CS(P,T) e | W | > | Z |, assurdo
✦
Quindi zk = pm = tn
✦
Supponiamo per assurdo che Z(k-1) ∉ LCS( P(m-1), T(n-1) )
✦
Allora esiste W ∈ LCS( P(m-1), T(n-1) ) tale che |W| > |Z(k-1)|
✦
Quindi Wpm ∈ CS(P,T) e |Wpm| > |Z|, assurdo
✦
P[1,…,m]
T[1,…,n]
Z[1,…,k]
© Alberto Montresor
a
a
a
P[1,…,m-1]
T[1,…,n-1]
Z[1,…,k-1]
57
Dimostrazione
Punto 2 (Punto 3 simmetrico)
✦
Se zk ≠ pm, allora Z ∈ CS(P(m-1), T)
✦
Per assurdo ipotizziamo che Z ∉ LCS(P(m-1), T)
allora esiste W ∈ LCS(P(m-1), T) tale che: | W | > | Z |
✦
Allora è anche vero che W ∈ LCS(P, T), contraddicendo l'ipotesi
✦
P[1,…,m]
T[1,…,n]
Z[1,…,k]
© Alberto Montresor
a
b
?
P[1,…,m-1]
T[1,…,n]
Z[1,…,k]
b
?
58
Cosa ci dice il teorema?
Se pm = tn, dobbiamo risolvere un sottoproblema
✦
LCS( P(m-1), T(n-1) )
✦
La definizione ricorsiva è la seguente:
✦
LCS(P,T) = LCS( P(m-1), T(n-1) ) pm
✦
Se pm ≠ tn, dobbiamo risolvere due sottoproblemi
✦
LCS( P(m-1), T )
✦
LCS( P, T(n-1) )
A questo punto, dobbiamo scegliere la LCS più lunga fra le 2
✦
La definizione ricorsiva è la seguente:
✦
LCS(P,T) = longest( LCS( P(m-1), T ) , LCS( P, T(n-1) ) )
✦
© Alberto Montresor
59
LCS basato su programmazione dinamica
Definiamo una tabella per memorizzare la lunghezza dei vari sottoproblemi di
LCS:
✦
D[0 ... m, 0 ... n] → tabella di (m+1) · (n+1) elementi, dove |P| = m, |T| = n
✦
D[i,j] → lunghezza della LCS di P(i) e T(j)
✦
Goal finale:
✦
Calcolare D[m,n] → lunghezza della LCS di P e T
✦
Formulazione ricorsiva
✦
© Alberto Montresor
60
LCS basato su programmazione dinamica
Definiamo una tabella per memorizzare informazioni necessarie ad ottenere la
stringa finale
✦
B[0 ... m, 0 ... n] → tabella di (m+1) · (n+1) elementi, dove |P| = m, |T| = n
✦
B[i,j] → “puntatore” alla entry della tabella stessa che identifica il sottoproblema
ottimo scelto durante il calcolo del valore D[i,j]
✦
Valori possibili:
✦
➘ deriva da i-1,j-1
↓ deriva da i-1,j
→ deriva da i,j-1
© Alberto Montresor
61
j
0
1
2
3
4
5
6
A
T
B
C
B
D
0
0
0
0
0
0
0
• TACCBT
• ATBCBD
i
➘ deriva da i-1,j-1
↓ deriva da i-1,j
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
→ deriva da i,j-1
© Alberto Montresor
0
62
j
0
1
2
3
4
5
6
B
E
B
E
D
E
0
0
0
0
0
0
• ABDDBE
• BEBEDE
i
➘ deriva da i-1,j-1
↓ deriva da i-1,j
1
A
0
↓0 ↓0 ↓0 ↓0 ↓0 ↓0
2
B
0
➘1 →1 ➘ 1 →1 →1 →1
3
D
0
↓ 1 ↓ 1 ↓ 1 ↓ 1 ➘2 →2
4
D
0
↓1 ↓1 ↓1 ↓1 ➘2 ↓2
5
B
0
➘ 1 ↓ 1 ➘2 →2 ↓ 2 ↓ 2
6
E
0
↓ 1 ➘2 ↓ 2 ➘ 3 →3 ➘ 3
→ deriva da i,j-1
© Alberto Montresor
0
0
Calcolo del valore della soluzione ottima
© Alberto Montresor
64
j
0
1
2
3
4
5
6
B
E
B
E
D
E
0
0
0
0
0
0
• ABDDBE
• BEBEDE
i
➘ deriva da i-1,j-1
↓ deriva da i-1,j
1
A
0
↓0 ↓0 ↓0 ↓0 ↓0 ↓0
2
B
0
➘1 →1 ➘ 1 →1 →1 →1
3
D
0
↓ 1 ↓ 1 ↓ 1 ↓ 1 ➘2 →2
4
D
0
↓1 ↓1 ↓1 ↓1 ➘2 ↓2
5
B
0
➘ 1 ↓ 1 ➘2 →2 ↓ 2 ↓ 2
6
E
0
↓ 1 ➘2 ↓ 2 ➘ 3 →3 ➘ 3
→ deriva da i,j-1
© Alberto Montresor
0
0
j
0
1
2
3
4
5
6
A
T
B
C
B
D
0
0
0
0
0
0
0
• TACCBT
• ATBCBD
i
➘ deriva da i-1,j-1
↓ deriva da i-1,j
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
→ deriva da i,j-1
© Alberto Montresor
0
66
Alcune ottimizzazioni
La matrice B può essere eliminata:
✦
Il valore di D[i,j] dipende solo dai valori D[i-1,j-1], D[i,j-1] e D[i-1,j].
✦
In tempo costante si può quindi determinare quale di questi tre è stato usato, e
perciò quale sia il tipo di freccia
✦
Se ci serve solo calcolare la lunghezza della LCS, possiamo ridurre la tabella
D[i,j] a due sole righe di lunghezza min{ n , m }
✦
Ad ogni istante (cioè per ogni coppia i,j), ci servono i valori
D[i-1,j-1], D[i,j-1] e D[i-1,j]
✦
Esercizio
✦
© Alberto Montresor
67
Stampa della soluzione ottima
Costo computazionale
A ogni passo, almeno uno
fra i e j viene decrementato:
θ(m+n)
© Alberto Montresor
68
LCS e diff
diff
✦
Esamina due file di testo, e ne evidenzia le differenze a livello di riga.
✦
Lavorare a livello di riga significa che i confronti fra simboli sono in realtà
confronti fra righe, e che n ed m sono il numero di righe dei due file
✦
Ottimizzazioni
✦
diff è utilizzato soprattutto per codice sorgente; è possibile applicare euristiche
sulle righe iniziali e finali
✦
per distinguire le righe - utilizzo di hash table
✦
© Alberto Montresor
69
String matching approssimato
Input
✦
una stringa P = p1 ··· pm
(pattern)
una stringa T = t1 ··· tn
(testo), con m ≤ n
✦
✦
Definizione
✦
Un’occorrenza k-approssimata di P in T , con 0 ≤ k ≤ m, è una copia della stringa P
nella stringa T in cui sono ammessi k “errori” (o differenze) tra caratteri di P e
caratteri di T , del seguente tipo:
✦
(1) i corrispondenti caratteri in P e in T sono diversi (sostituzione)
(2) un carattere in P non è incluso in T (inserimento)
(3) un carattere in T non è incluso in P (cancellazione)
Problema:
✦
Trovare un’occorrenza k-approssimata di P in T per cui k sia minimo.
✦
© Alberto Montresor
70
Esempio
Input
✦
questoèunoscempio
✦
unesempio
✦
Domanda
✦
Qual è il minimo valore k per cui si trova una occorrenza k-approssimata?
✦
A partire da dove?
✦
Con quali errori?
✦
© Alberto Montresor
71
Sottostruttura ottima
Definizione
✦
Tabella D[0...m, 0...n], i cui elementi D[i,j] contengono il minimo valore k per
cui esiste una occorrenza k-approssimata di P(i) in T(j)
✦
D[i,j] può essere uguale a
✦
D[i-1,j-1], se pi = tj
✦
avanza su entrambi i caratteri (uguali)
D[i-1,j-1]+1, se pi ≠ tj
avanza su entrambi i caratteri (sostituzione)
D[i-1,j]+1
avanza sul pattern (inserimento)
D[i,j-1]+1
avanza sul testo (cancellazione)
✦
✦
✦
© Alberto Montresor
72
Sottostruttura ottima
Definizione
✦
Tabella D[0...m, 0...n], i cui elementi D[i,j] contengono il minimo valore k per
cui esiste una occorrenza k-approssimata di P(i) in T(j)
✦
Ricordate che cerchiamo il minimo:
✦
© Alberto Montresor
73
Ricostruzione della soluzione finale
Si noti che:
✦
D[m,j] = k se e solo se c’è un’occorrenza k-approssimata di P in T che
termina in tj
✦
la soluzione del problema è data dal valore di D[m,j] più piccolo, per 0 ≤ j ≤ n
✦
© Alberto Montresor
74
Algoritmo String matching approssimato
Domanda:
complessità?
© Alberto Montresor
75
String matching approssimato
Variante dello string matching approssimato:
Distanza di editing (Distanza di Levenshtein)
✦
Date due stringhe, vogliamo conoscere il numero minimo di operazioni
(sostituzione, inserimento, cancellazione) necessarie per trasformare una nell’altra
✦
(o viceversa, visto che inserimento e cancellazione sono simmetriche)
✦
Esempio:
✦
distanza fra google e yahoo?
✦
Algoritmo?
✦
Come (e se) dobbiamo modificare le condizioni iniziali?
✦
Come (e se) dobbiamo modificare la definizione ricorsiva?
✦
© Alberto Montresor
76
Insieme indipendente di intervalli pesati
Input
✦
Siano dati n intervalli distinti [a1, b1[, ..., [an,bn[ della retta reale, aperti a destra,
dove all’intervallo i è associato un peso wi, 1 ≤ i ≤ n.
✦
Definizione
✦
Due intervalli i e j si dicono digiunti se: bj ≤ ai oppure bi ≤ aj
✦
ai
Output:
bi
aj
bj
✦
Trovare un insieme indipendente di peso massimo, ovvero un sottoinsieme di
intervalli tutti disgiunti tra di loro tale che la somma dei pesi degli intervalli nel
sottoinsieme sia la più grande possibile
✦
Esempio:
✦
Prenotazione di una sala conferenza in un hotel
✦
© Alberto Montresor
77
Pre-elaborazione
Per poter applicare la programmazione dinamica, è necessario effettuare una preelaborazione
✦
Ordiniamo gli intervalli per estremi finali non decrescenti
✦
b1 ≤ b2 ≤ ⋅ ⋅ ⋅ ≤ bn
✦
Per ogni intervallo i, sia pi = j il predecessore di i, dove j < i è il massimo indice tale
che [aj , bj [ è disgiunto da [ai , bi [ (se non esiste j, allora pi = 0)
✦
Teorema sottostruttura ottima
✦
Sia P[i] il sottoproblema dato dai primi i intervalli e sia S[i] una sua soluzione
ottima di peso D[i]
✦
Se l’intervallo i-esimo non fa parte di tale soluzione, allora deve valere
D[i] = D[i − 1], dove si assume D[0] = 0;
✦
altrimenti, deve essere D[i] = wi + D[pi]
✦
© Alberto Montresor
78
Definizione ricorsiva
Definizione ricorsiva del peso di una soluzione ottima
✦
D[n] è il problema originario
✦
Costo della procedura risultante
✦
O(n log n) per l’ordinamento
✦
O(n log n) per il calcolo degli indici pi
✦
O(n) per il riempimento della tabella
✦
O(n) per la ricostruzione della soluzione
✦
Esercizio:
✦
Scrivere algoritmo per il calcolo degli indici pi
✦
© Alberto Montresor
79
Codice
© Alberto Montresor
80