Programmazione dinamica
Introduzione.
Prodotto di una sequenza di matrici.
Caratterizzazione soluzione ottima.
Definizione ricorsiva soluzione ottima.
Calcolo del valore di una soluzione ottima.
Costruzione di una soluzione ottima.
Programmazione dinamica
La programmazione dinamica, generalmente, viene adottata
per risolvere problemi di ottimizzazione.
Questo vuol dire:
•il problema ammette diverse soluzioni
•ogni soluzione ha un costo
•si sta cercando una soluzione che mi dia il valore ottimo
(il massimo o il minimo dei costi)
Nota: non si cerca “la” soluzione ottima, ma “una” soluzione
ottima, dato che possono esistere varie soluzioni ottime.
Prodotto di una sequenza di matrici
Problema:
Si vuole effettuare il prodotto di una sequenza di matrici
<A1, A2,…, An> minimizzando il numero di moltiplicazioni
scalari effettuati.
Il costo dipende dalla sua parentesizzazione:
((A1 ((A2 A3) (A4 …)))An)
Per esempio: <A1, A2, A3>
dim(A1)=10x100; dim(A2)=100x5; dim(A3)=5x50;
E’ meglio ((A1 A2) A3) ?
Oppure
(A1 (A2 A3)) ?
Costo moltiplicazione di due matrici
MATRIX-MULTIPLY(A, B)
1.
if columns[A] ≠ rows[B]
2.
then error “dimensioni non compatibili”
3.
else for i ← 1 to rows[A]
4.
do for j ← 1 to columns[B]
5.
do C[i,j] ← 0
6.
for k ← 1 to columns[A]
7.
do C[i,j] ← C[i,j] + A[i,k] B[k,j]
8.
return C
Sostanzialmente:
Se si moltiplica A con dimensioni p x q e B con dimensioni q
x r, si ottiene una nuova matrice C con dimensioni p x r.
Il costo è determinato dal numero di moltiplicazioni scalari
effettuati, ossia p • q • r. Per ogni elemento della matrice C
(p x r) bisogna effettuare q moltiplicazioni scalari.
Prodotto di una sequenza di matrici
Ritornando all’esempio: <A1, A2, A3>
dim(A1)=10x100; dim(A2)=100x5; dim(A3)=5x50;
(A1 A2) → (10 • 100 • 5) = 5000 molt.
((A1 A2) A3) → (10 • 100 • 5) + (10 • 5 • 50) = 7500 molt.
(A2 A3) → (100 • 5 • 50) = 25000 molt.
(A1 (A2 A3)) → (100 • 5 • 50) + (10 • 100 • 50) = 75000 molt.
Quindi: ((A1 A2) A3) costa meno di (A1 (A2 A3))!
Numero di parentesizzazioni
Supponiamo che per risolvere il problema si controlli in
maniera esaustiva tutte le soluzioni.
P(n) = tutte le possibili parentesizzazioni di una sequenza di
n matrici
1
se n  1

 n 1
P ( n)  
P (k ) P (n  k ) se n  2

k 1
prodotto di sottoparentesizzazioni
P(n)  C (n  1)
sequenza dei numeri Catalani
1  2n 
   (4n / n3 / 2 )
C ( n) 
Nota: la ricerca esaustiva risulta
n 1  n 
essere molto dispendiosa!
Soluzione in programmazione
dinamica
Lo sviluppo di un algoritmo in programmazione dinamica
può essere diviso in quattro fasi o passi:
1. Caratterizzazione della struttura di una soluzione
ottima.
2. Definizione ricorsiva del valore di una soluzione ottima.
3. Calcolo del valore di una soluzione ottima con una
strategia bottom-up.
4. Costruzione di una soluzione ottima a partire dalle
informazioni calcolate.
1. Caratterizzazione della struttura
di una soluzione ottima.
Per il nostro problema una soluzione ottima è del tipo:
((A1 A2… Ak) (Ak+1 Ak+2… An)) con 1 ≤ k ≤ n
tale che
(A1 A2… Ak) → la sua parentizzazione è ottima per la
sequenza <A1, A2,… Ak> (altrimenti scelgo quella ottima,
costa meno!). Dimensione matrice finale = p x q
(Ak+1 Ak+2… An) → la sua parentizzazione è ottima per la
sequenza <Ak+1, Ak+2,… An> (altrimenti scelgo quella ottima).
Dimensione matrice finale = q x r
Inoltre il costo della soluzione ottima è
costo = costo(A1 A2… Ak) + costo(Ak+1 Ak+2… An) + p•q•r
2. Definizione ricorsiva del valore di
una soluzione ottima.
Si determina una soluzione ottima ricorsivamente in
termini dei valori delle soluzioni ottime dei sottoproblemi.
Sottoproblema: <Ai, Ai+1,… Aj> con 1 ≤ i ≤ j ≤ n
m[i,j] = costo minimo per la sottosequenza
<Ai, Ai+1,… Aj>
m[i,i] = costo minimo per la sottoseq. <Ai,… Aj> = Ai = 0
m[1,n] = costo minimo per la sequenza <A1, A2,… An>
0
se i  j


m[i, j ]  
min m[i, k ]  m[k  1, j ]  pi 1 pk p j  se i  j

i  k  j
2. Definizione ricorsiva del valore di
una soluzione ottima.
0
se i  j


m[i, j ]  
min m[i, k ]  m[k  1, j ]  pi 1 pk p j  se i  j

i  k  j
E’ facile vedere che il valore di m[i,j] è ottenuto
sommando i costi minimi del calcolo dei sottoprodotti Ai..k
e Ak+1..j con il costo del prodotto delle due matrici
risultanti (pari a pi-1pkpj).
Dimensioni matrice Aj
(pi-1Aipi…pk-1Akpk) (pkAk+1pk+1…pj-1Ajpj)
Nota: definiamo s[i,j] = k, per tenere traccia del valore k
che costituisce una soluzione ottima per il sottoproblema
<Ai, A2,… Aj>.
3. Calcolo del valore di una soluzione
ottima con strategia bottom-up.
Bottom-up vuol dire che si parte a calcolare i costi ottimi
per le sottosequenze lunghe 1, poi quelle lunghe 2 e così
via…
UP
lung=n
m[1,n]
…
…
m[1,3]
lung=3
lung=2
lung=1
BOTTOM
m[1,2]
m[1,1] = 0
m[2,4]
m[2,3]
m[2,2] = 0
…
m[3,5]
m[3,4]
m[3,3] = 0
m[4,5]
m[4,4] = 0
m[n-2,n]
…
…
m[n-1,n]
m[n,n] = 0
3. Calcolo del valore di una soluzione
ottima con strategia bottom-up.
MATRIX-CHAIN-ORDER(p) // INPUT: p = <p0, p1, …, pn> dimensioni
matrici in ingresso, lunghezza(p) = n+1
1. n ← length[p] – 1
// n = lunghezza(p) – 1
2. for i ← 1 to n
3.
do m[i,i] ← 0
// costo 0 sottoseq. lunghe 1
4. for l ← 2 to n
// l = lunghezza sottoseq., da 2 a n !!!
5.
do for i ← 1 to n-l+1
// i = inizio sottoseq.
6.
do j ← i+ l -1
// j = fine sottoseq.
7.
m[i,j] ← ∞
// costo sottoseq. [i,j] inizializzato a ∞
8.
for k ← i to j-1
// calcolo k soluzione ottima m[i,j]
9.
do q ← m[i,k] + m[k+1,j] + pi-1pkpj
10.
if q < m[i,j]
// se costo calcolato è minore del
costo ottimo attuale
11.
then m[i,j] ← q
// aggiorna matrice costi
12.
s[i,j] ← k
// aggiorna matrice indici k
13. return m e s
3. Calcolo del valore di una soluzione
ottima con strategia bottom-up.
m
1
6
matrice
dimensione
A1
30 x 35
A2
35 x 15
A3
15 x 5
A4
5 x 10
A5
10 x 20
A6
20 x 25
15125
5
j
4
9375
3
2
7875
15750
1
11875
2
10500
7125
4375
2625
3
4
5375
2500
750
i
3500
1000
5
6
5000
0
0
0
0
0
0
A1
A2
A3
A4
A5
A6
3. Calcolo del valore di una soluzione
ottima con strategia bottom-up.
s
1
6
matrice
dimensione
A1
30 x 35
A2
35 x 15
A3
15 x 5
A4
5 x 10
A5
10 x 20
A6
20 x 25
3
5
j
3
4
3
3
1
2
1
3
3
3
2
2
3
3
4
3
3
i
5
5
4
5
((A1 ) (A2 A3)) ((A4 A5) A6) → s[1,6]=3; s[1,3]=1; s[4,6]=5.
3. Calcolo del valore di una soluzione
ottima con strategia bottom-up.
Osservazione importante:
Il numero di sottoproblemi è relativamente basso: un
problema per ogni scelta di i e j, con 1 ≤ i ≤ j ≤ n, per un totale
di  n 
   n  (n 2 )
numero di sottoproblemi
 2
2
Θ(n
Problemi di
Problemi di
lunghezza l>0 (m[i,j]) lunghezza 0 (m[i,i])
) =memoria necessaria per m e s
Sottoproblemi comuni
Se si facesse una ricerca esaustiva potrebbe succedere di
risolvere più volte lo stesso sottoproblema. Per esempio, la
soluzione ((A1 ) (A2 A3)) ((A4 A5) A6) e la soluzione
(A1) (((A2 A3) (A4 A5)) A6) hanno in comune (A2 A3) e (A4 A5).
4. Costruzione di
una soluzione ottima
La strategia per la costruzione di una soluzione ottima
dipende dalle informazioni dei sottoproblemi calcolate nelle
fasi precedenti.
Nel nostro caso specifico utilizziamo la matrice s:
A1 A2… An
A1 A2… As[1,n]
A1… As[1,s[1,n]] As[1,s[1,n]]+1… As[1,n]
As[1,n]+1As[1,n]+2… An
4. Costruzione di
una soluzione ottima
Nel nostro caso specifico utilizziamo la matrice s:
A1 A2 A3 A4 A5 A6
s[1,6]=3.
A1 A2 A3
s[1,3]=1;
s[4,6]=5.
A1
s[2,3]=2;
s[4,5]=4.
A4 A5 A6
A2 A3
A2
A3
Soluzione: ((A1 ) (A2 A3)) ((A4 A5) A6).
A4 A5
A4
A5
A6
4. Costruzione di
una soluzione ottima
MATRIX-CHAIN-MULTIPLY(A, s, i, j)
1. if j > i
2.
then X ← MATRIX-CHAIN-MULTIPLY(A, s, i, s[i,j])
3.
Y ← MATRIX-CHAIN-MULTIPLY(A, s, s[i,j]+1, j)
4.
return MATRIX-MULTIPLY(X,Y)
5.
else return Ai
MATRIX-CHAIN-MULTIPLY(A, s, 1, 6) calcola il prodotto
della sequenza di matrici secondo la parentizzazione:
((A1 ) (A2 A3)) ((A4 A5) A6).
Altri problemi
• La più lunga sottosequenza in comune
Dati due sequenze X e Y si cerca una sottosequenza Z
comune di lunghezza massima.
• Il problema della zaino
Dato degli oggetti O1, O2, …, On che hanno volume
V1, V2, …, Vn e valore Val1, Val2, …, Valn, si cerca di
riempire lo zaino di volume V massimizzando la somma
dei valori. Il problema consiste nel scegliere i vari oggetti in
modo che il volume complessivo sia al massimo V e la
somma dei loro valori sia ottimo.