Algoritmi e Strutture Dati (Mod. B)

Programmazione Dinamica

(Parte II)

Calcolo del valore di una soluzione ottima

Il terzo passo consiste nel calcolare il valore della soluzione ottima (alla parentesizza-zione) in termini delle soluzioni ottime (alle parentesizzazioni) dei sottoproblemi.

Calcolo del valore di una soluzione ottima

A partire dall’equazione sotto, sarebbe facile definire un algoritmo ricorsivo che calcola il costo minimo m(1,n) di A1…n

Purtroppo vedremo che tale approccio porta ad un algoritmo di costo esponenziale, non migliore dell’enumerazione esaustiva.

rlcccrkmklm

rlrlm

rklrkl

se

se

}),1(),({min

0),(

1

6

5

4

3

2

1

654321L R

-----6

----5

---4

--3

-2

1

654321L R

m(l,r) = 0 se l = r, m(l,r) = minlk<r{ m(l,k) + m(k+1,r) + cl-1ckcr } altrimenti

06

05

04

03

02

01

654321L R

m(1,2) = min1 k < 2{ m(1,k) + m(k+1,2) + c1ckc2 }= m(1,1) + m(2,2) + c0c1c2

6

5

4

3

2

1

654321L R

-----6

----5

---4

--3

-2

1

654321L R

m(l,r) = 0 se l = r, m(l,r) = minlk<r{ m(l,k) + m(k+1,r) + cl-1ckcr } altrimenti

06

05

04

03

02

01

654321L R

m(2,4) = min2k<4{ m(2,k) + m(k+1,4) + c1ckc4 }= min { m(2,2) + m(3,4) + c1c2c4 ,

m(2,3) + m(4,4) + c1c3c4 }

6

5

4

3

2

1

654321L R

-----6

----5

---4

--3

-2

1

654321L R

m(l,r) = 0 se l = r, m(l,r) = minlk<r{ m(l,k) + m(k+1,r) + cl-1ckcr } altrimenti

06

05

04

03

02

01

654321L R

m(2,5) = min2k<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 }

6

5

4

3

2

1

654321L R

-----6

----5

---4

--3

-2

1

654321L R

m(l,r) = 0 se l = r, m(l,r) = minlk<r{ m(l,k) + m(k+1,r) + cl-1ckcr } altrimenti

06

05

04

03

02

01

654321L R

m(1,5) = min1k<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 }

6

5

4

3

2

1

654321L R

-----6

----5

---4

--3

-2

1

654321L R

m(l,r) = 0 se l = r, m(l,r) = minlk<r{ m(l,k) + m(k+1,r) + cl-1ckcr } altrimenti

06

05

04

03

02

01

654321L R

m(1,6) = min1k<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 }

L’importante osservazione è che ci sono un numero limitato di sottoproblemi, uno per ogni scelta di l e r (con 1 l r n), quindi in totale

Calcolo del valore di una soluzione ottima

)(2

2nnn

Sottoproblemi

con l r

corrispondenti alle celle riempite di una matrice nn.

Utilizzando quindi una matrice m[nn] possiamo risolvere facilmente il problema in tempo polinomiale.

Sottoproblemicon l = r

Utilizzando quindi una matrice m[n,n] possiamo risolvere facilmente il problema in tempo polinomiale.

Ogni sottoproblema è risolvibile utilizzando solo le soluzioni di sottoproblemi ricorrenti più volte che possono essere calcolati prima e memorizzati nella matrice m[n,n].

In tal modo non si calcola mai più di una volta la soluzione ad un sottoproblema.

Questa è l’idea chiave della programmazione dinamica.

Calcolo del valore di una soluzione ottima

L’algoritmo MCO (Matrix-Chain-Order)

• prende in ingresso un array c[] contenente i le dimensioni delle matrici (c[0] è il numero di righe della prima matrice, c[i] è il numero di colonne della matrice Ai

• utilizza (e ritorna) due matrici nn ausiliarie:• m[l,r] che contiene i costi minimi dei sottoproblemi

Al…r

• s[l,r] che contiene il valore di k che minimizza il costo per il sottoproblema

Calcolo del valore di una soluzione ottima

Calcolo del valore di una soluzione ottima

MCO(c[]: array di intero) n = lunghezza[c] - 1 for i = 1 to n do m[i,i] = 0 for l = 2 to n do for i = 1 to n - l + 1 do j = i + l - 1 m[i,j] =

for k = i to j - 1 do q = m[i,k] + m[k+1,j] + c[i-1]c[k]c[j] if q < m[i,j] then m[i,j] = q s[i,j] = k return m[] e s[]

Il costo è zero nel casodi una sola matrice

Calcola tutti i possibili valori e conserva solo il più piccolo

l varia sulle diagonali sopraquella principale

i e j assumono i valori dellecelle nella diagonale l

0-----6

0----5

0---4

0--3

0-2

01

654321L R

06

9005

3004

2403

6402

22401

654321L R

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

06

9005

903004

702403

1126402

17622401

654321L R

06

9005

903004

138702403

1741126402

21817622401

654321L R

06

9005

903004

138702403

2501741126402

35027621817622401

654321L R

TempoO(n3)

66

55

34

23

42

81

70

cii

06

9005

903004

138702403

2501741126402

27621817622401

654321L R

06

05

304

7003

6402

17622401

65321L R

m[ ]

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

66

55

34

23

42

81

70

cii

06

505

5404

3303

3202

1101

654321L R

s[ ]

6

5

3

2

3 1

L R

3

33

3 3

Calcolo del valore di una soluzione ottima

• L’algoritmo MCO calcola i costi minimi riempiendo le matrici partendo dalla diagonale principale (tutti 0) e proseguendo in ordine con le diagonali successive alla principale.

• Ad ogni passo il valore di m[i,j] dipende solo dai valori, calcolati precedentemente, delle celle m[i,k] e m[k+1,j], che infatti stanno nelle diagonali sottostanti a quella di m[i,j]

• Il valore di ogni cella m[i,j] viene calcolato una sola volta durante la processazione della diagonale (indicata dall’indice l) in cui compare.

Costruzione della soluzione ottima

Il quarto passo consiste nel costruire il la soluzione ottima (al prodotto delle n matrici), cioè quello il cui costo ottimo è stato calcolato al terzo passo.

• Infatti terzo passo calcola il costo (e gli indici k ottimali) della soluzione ottima ma non ci calcola il prodotto corrispondente.

Costruzione della soluzione ottima

• Possiamo definire un algoritmo che costruisce la soluzione a partire dalla informazione calcolata da MCO.

• La matrice s[ ] ci permette di determinare il modo migliore di moltiplicare le matrici.

• s[i,j] contiene infatti il valore di k su cui dobbiamo spezzare il prodotto Ai…j ...

• … ci dice cioè che per calcolare Ai…j dobbiamo prima calcolare Ai…k e Ak+1…j e poi moltiplicarle tra loro.

• Ma questo è un processo facilmente realizzabile tra-mite un algoritmo ricorsivo

Costruzione della soluzione ottima

MCM(A[]:array ; s[]: matrici; i,j: intero) if j > i then k = s[i,j] X = MCM(A,s,i,k) Y = MCM(A,s,k + 1,j) return Prod-Matrici(X,Y) else return A[i]

• A[] un array di lunghezza n che contiene le matrici [A1 , A2 ,… , An ] • s[] la matrice nn che contiene il valore di k ottimo

per ogni coppia di indici (l,r)

Costruzione della soluzione ottima

06

505

5404

33303

333202

3331101

654321L R

A1…6 = A1…kAk+1…6

= A1…3A4…6

A1…3 = A1…kAk+1…3

=A1A2…3

A4…6 = A4…kAk+1…6

=A4..5A6

A2…3 = A2…kAk+1…3

= A2A3

A4…5 = A4…kAk+1…5

=A4A5

A1…6 = ( ( A1 (A2A3) )( (A4A5 ) A6) )

s[ ]

Versione ricorsiva di MCO

rlcccrkmklm

rlrlm

rklrkl

se

se

}),1(),({min

0),(

1

R-MCO(c[]: array di intero; i,j:intero) if i = j then return 0 else m[i,j] = for k = i to j-1 do Costo = R-MCO(c,i,k) + R-MCO(c,k+1,j) +

+ c[i-1]c[k]c[j] if Costo < m[i,j] then m[i,j] = Costo return m[i,j]

Versione ricorsiva di MCO

• Definiamo l’equazione di ricorrenza per m[1,n] dell’algoritmo ricorsivo appena visto:

1 se)1)()((1

1 se1)( 1

1nknTkT

nnT n

k

assumendo che i due if abbiano costo almenounitario (comunque costante).

Versione ricorsiva di MCO

• Definiamo l’equazione di ricorrenza per m[1,n] dell’algoritmo ricorsivo appena visto:

1 se)1)()((1

1 se1)( 1

1nknTkT

nnT n

k

1 se )( 211)(1

1

nkTnnT

n

k

1 se )( 2)(1

1

nkTnnT

n

k

Versione ricorsiva di MCO

• Dimostriamo per sostituzione che l’equazoine di ri-correnza ha soluzione esponenziale (2n) [T(n)2n-1] :

1 se )( 2)(1

1

nkTnnT

n

k

• Caso Base: T(1) 1 = 20 = 21-1

• Caso Induttivo: nnTn

i

i

1

1

122)(

nn

i

i

2

022

Versione ricorsiva di MCO

1 se )( 2)(1

1

nkTnnT

n

k

• Caso Base: T(1) 1 = 20

• Caso Induttivo: nnTn

i

i

2

022)(

nn )12(2 1

22 nn n2 per n2

• Dimostriamo per sostituzione che l’equazoine di ri-correnza ha soluzione esponenziale (2n) [T(n)2n-1] :

Versione ricorsiva di MCO

)2()( nnT

• Quindi il tempo di esecuzione di R-MCO è almeno esponenziale nel numero di matrici da moltiplicare, cioè:

• Cerchiamo di capire da dove deriva questa ineficienza dell’algoritmo ricorsivo.

Versione ricorsiva di MCO

1…4

1…1 2…4 1…2 3…4 1…3 4…4

1…1 2…22…2 3…4 2…3 4…4 3…3 4…4 1…1 2…3 1…2 3…3

3…3 4…4 2…2 3…3 2…2 3…3 1…1 2…2

Ricorsione e Programmazione Dinamica

• Ancora una volta, l’inefficienza della versione ricorsiva deriva dal fatto che i sottoproblemi non danno luogo a computazioni indipendenti.

• cioè, molti sottoproblemi ricorrono più volte e devono quindi essere risolti ogni volta.

• Questo fenomeno viene anche indicato con: sovrapposizione dei sottoproblemi.

Programmazione Dinamica

• La Programmazione Dinamica evita di ripetere la computazione per i sottoproblemi che si ripetono.

• col supporto di memoria aggiuntiva (tabella) risolve i sottoproblemi al più una sola volta.

La sovrapposizione di sottoproblemi è uno degli indicatori che la Programmazione Dinamica potrebbe fornire una soluzione efficiente.

Programmazione Dinamica

• Prima di tentare di definire l’algoritmo, si deve però dimostrare la proprietà per il problema dato.

• Una tecnica standard per dimostrare la proprietà • si assume che esista una soluzione migliore per un

sottoproblema arbitraro e

• si dimostra che da tale assunzione segue una contrad-dizione con l’ipotesi di ottimalità

La sovrapposizione di sottoproblemi è uno degli indicatori che la Programmazione Dinamica potrebbe fornire una soluzione efficiente.

Programmazione Dinamica

• La Programmazione Dinamica sfurtta la proprietà della struttura della soluzione ottima.

• Affinché la Programmazione Dinamica sia appli-cabile, è necessario che la soluzione ottima del problema esibisca la proprietà della sottostruttura ottima

La sottostruttura ottima è il secondo indicatore che la Programmazione Dinamica potrebbe fornire una soluzione efficiente.

Ricorsione con memorizzazione

• É una variante della Programmazione Dinamica.• L’idea è quella di fondere la memorizzazione in

tabella tipico della Progr. Dinamica con l’approc-cio ricorsivo tipico del Divede-et-Impera.

• Quando un sottoproblema viene risolto per la prima volta, viene memorizzto in una tabella:• ogni volta che si deve risolvere un sotto-

problema, si controlla nella tabella se è già stato risolto precedentemente

• se lo è già stato, si usa il risultato della tabella

• altrimenti lo si calcola e si memorizza il risultato

Ricorsione con memorizzazione

• Quando un sottoproblema viene risolto per la prima volta, viene memorizzto in una tabella:• ogni volta che si deve risolvere un sotto-

problema, si controlla nella tabella se è già stato risolto precedentemente

• se lo è già stato, si usa il risultato della tabella

• altrimenti lo si calcola e si memorizza il risultato

• In tal modo, ogni sottoproblema viene calcolato una sola volta e memorizzato come nel caso precedente.

• Dal momento che abbiamo solo (n2) sottopro-blemi, il tempo di esecuzione sarà identico.

Versione ricorsiva con memorizzazione

Mem-MCO(c[]: array di intero) n = lunghezza[c] - 1 for i = 1 to n do for j = i to n do m[i,j] = return Cerca-MC(c,1,n)

Cerca-MC(c[]: array of intero; i,j:intero) if m[i,j] < then return m[i,j] if i = j then m[i,j] = 0 else for k = i to j-1 do Costo = Cerca-MC(c,i,k) + Cerca-MC(c,k+1,j)

+ c[i-1]c[k]c[j] if Costo < m[i,j] then m[i,j] = Costo return m[i,j]

Confronto tra i due approcci

• Iterativo Bottom-up :• quando tutti i sottoproblemi devono essere risolti

almeno una volta, è più efficiente, non avendo il problema di gestire le chiamate ricorsive.

• in alcuni casi, la regolarità degli accessi alla tabella può essere sfruttata per ridurre ulteriormente tempo e/o spazio (come per Numeri di Fibonacci)

• Ricrsione con memorizzazione:• quando alcuni sottoproblemi possono non essere risolti

affatto, può essere vantaggiosa, perché risolve solo i sottoproblemi richiesti per ottenere la soluzione finale.

Confronto con Divide-et-ImperaLa soluzione dei problemi è costruita a partire dalle soluzione

dei sottoproblemi. • Divide-et-Impera : Merge Sort

• Ogni suddivisione del problema in sottoproglemi porta alla stessa soluzione

• I sottoproblemi sono disgiunti• Il calcolo avviene in maniera “top-down”

Confronto con Divide-et-Impera

• Programmazione Dinamica : Moltiplicazioni tra Matrici• Differenti suddivisioni del problema portano a differenti

soluzioni. La maggior parte di queste non porta ad una soluzione ottima.

• I sottoproblemi si sovrappongono (non sono indipende-nti)

• Il calcolo avviene in maniera “bottom-up”

La soluzione dei problemi è costruita a partire dalle soluzione dei sottoproblemi.

• Divide-et-Impera : Merge Sort• Ogni suddivisione del problema in sottoproglemi porta alla stessa

soluzione• I sottoproblemi sono disgiunti• Il calcolo avviene in maniera “top-down”

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 sesso ordine nella sequenza risultante, anche se non devono essere necessariamente conti-gui in S.

Esempio

S = AAAATTGA S’ = AAATA

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 sesso 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 Zk è una LCS di Xm-1 e Y.3 se xm yn e zk yn, allora Zk è 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 Zk è una LCS di Xm-1 e Y.3 se xm yn e zk yn, allora Zk è 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 Zk è una LCS di Xm-1 e Y.3 se xm yn e zk yn, allora Zk è 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 Zk è una LCS di Xm-1 e Y.3 se xm yn e zk yn, allora Zk è una LCS di X e Yn-1.

Dimostrazione: 2 Se xm yn e zk xm, allora Zk è 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 Zk è una LCS di X e Yn-1

La dinostrazione è simmetrica a quella del punto 2