Post on 02-May-2015
Studieremo alcune tecniche per il progetto di algoritmi e di strutture dati:
Programmazione dinamica
Algoritmi golosi
Analisi ammortizzata
Vedremo poi alcuni tipi di strutture dati importanti per le applicazioni:
B-alberi
Strutture dati per insiemi disgiunti
Esempio: taglio delle aste
Problema del taglio delle asteE’ data un’asta metallica di lunghezza n che deve essere tagliata in pezzi di lunghezza intera (con un costo di taglio trascurabile). Per ogni lunghezza l = 1,…,n è dato il prezzo pl a cui si possono vendere i pezzi di quella lunghezza.Si vuole decidere come tagliare l’asta in modo da rendere massimo il ricavo della vendita dei pezzi ottenuti.
Programmazione Dinamica
Esempio l 1 2 3 4 5 6 7 8 9 10
pl 1 5 8 9 10 17 17 20 24 30
Lunghezza asta n Ricavo massimo rn Suddivisione ottima
1 1 1
2 5 2
3 8 3
4 10 2+2
5 13 2+3
6 17 6
7 18 1+6 o 2+2+3
8 22 2+6
9 25 3+6
10 30 10
Un’asta di lunghezza n può essere tagliata in 2n-1 modi distinti in quanto abbiamo una opzione tra tagliare o non tagliare in ogni posizione intera 1,…,n-1.Ad esempio per n = 4 abbiamo i seguenti 8 modi
Suddivisioni4 1+1+21+3 1+2+12+2 2+1+13+1 1+1+1+1
In generale il ricavo massimo rn o è il costo pn dell’asta intera oppure si ottiene effettuando un primo taglio in posizione i e quindi sommando i ricavi massimi del primo e del secondo pezzo, ossia rn= ri + rn-i
Quindi
1 se),...,,,max(
1 se
112211
1
nrrrrrrp
npr
nnnnn
Osserviamo che la soluzione ottima del problema di ottiene da soluzioni ottime di sottoproblemi. Diciamo che il problema ha sottostruttura ottima.
Otteniamo una struttura ricorsiva più semplice se invece di scegliere la posizione i di un primo taglio intermedio scegliamo la lunghezza i del primo pezzo per cui rn= pi + rn-i
0 se)(max
0 se0
1nrp
nr
inini
n
Cut-Road(p, n) if n == 0 return 0 q = -1 for i =1 to n q = max(q, p[i]+Cut-Road(p, n-i)) return q
nn
j
jTnT 2)(1)(1
0
Albero di ricorsione per n = 4
0
001
0
012
3
4
001
2 01
Lo stesso problema di dimensione 2 viene risolto due volte, quello di dimensione 1 quattro volte e quello di dimensione 0 otto volte.
Questo spiega la complessità 2n.
Ripetizione dei sottoproblemi!!
Possiamo ridurre la complessità evitando di risolvere più volte gli stessi problemi.
Un primo modo per farlo è dotare l’algoritmo di un blocco note in cui ricordare le soluzioni dei problemi già risolti: metodo top-down con annotazione.
Un secondo modo per farlo è calcolare prima i problemi più piccoli memorizzandone le soluzioni e poi usare tali soluzioni per risolvere i problemi più grandi: metodo bottom-up.
Versione top-down con annotazione:Memoized-Cut-Road(p, n) for i = 0 to n // inizializza il blocco note r[i] = -1 return Cut-Road-Aux(p, n, r)
Cut-Road-Aux(p, j, r) if r[j] ≥ 0 // il problema è già stato risolto return r[j] if j == 0 q = 0 else q = -1 for i = 1 to j q = max(q, p[i] + Cut-Road-Aux(p, j-i, r)) r[j] = q return q
)()( 2nnT
Versione bottom-up:
Bottom-Up-Cut-Road(p, n) r[0] = 0 // il problema più semplice for j = 1 to n q = -1 for i = 1 to j q = max(q, p[i] + r[j-i]) r[ j] = q return r[n] )()( 2nnT
Versione bottom-up estesa per calcolare la soluzione ottima e non solo il suo valoreExtended-Bottom-Up-Cut-Road( p, n) r[0] = 0 for j = 1 to n q = -1 for i = 1 to j if q < p[i]+r[ j - i] q = p[i]+r[ j - i] s[ j] = i // memorizzo il taglio ottimo r[ j] = q return r ed s
La seguente procedura calcola e stampa la soluzione ottima:
Print-Cut-Road-Solution( p, n) (r, s) = Extended-Bottom-Up-Cut-Road( p, n) j = n while j > 0 print s[j] j = j - s[j]
Moltiplicazione di matrici
Esso richiede pqr prodotti scalari
L’algoritmo per moltiplicare due matrici A e B di dimensioni pq e qr è:
Matrix-Multiply(A, B) for i = 1 to A.rows for j = 1 to B.columns C[i, j] = 0 for k = 1 to A.columns C[i, j] = C[i, j] + A[i, k] B[k, j] return C
Problema della moltiplicazione di matrici
Si deve calcolare il prodotto
A1 A2 ... An
di n matrici di dimensioni
p0p1 , p1p2 , ... , pn-1pn
Poiché il prodotto di matrici è associativo possiamo calcolarlo in molti modi.
Esempio:
Per calcolare il prodotto A1 A2 A3 di 3 matrici di dimensioni 2005, 5100, 1005 possiamo:
a) moltiplicare A1 per A2 (100000 prodotti scalari) e poi moltiplicare per A3 la matrice 200100 ottenuta (100000 prodotti scalari).
In totale 200000 prodotti scalari.
b) moltiplicare A2 per A3 (2500 prodotti scalari) e poi moltiplicare A1 per la matrice 55 ottenuta (5000 prodotti scalari).
In totale 7500 prodotti scalari.
Vogliamo trovare il modo per minimizzare il numero totale di prodotti scalari.
In quanti modi possiamo calcolare il prodotto?
Tanti quante sono le parentesizzazioni possibili del prodotto A1 A2 ... An .
Ad esempio per n = 4:(A1 (A2 (A3 A4)))
(A1 ((A2 A3) A4))
((A1 A2) (A3 A4))
((A1 (A2 A3)) A4)
(((A1 A2) A3) A4)
Il numero P(n) di parentesizzazioni possibili del prodotto A1 A2 ... An di n matrici si esprime ricorsivamente come segue:
1 se)()(
1 se1)(
1
1
nknPkP
nnP
n
k
Si può dimostrare che P(n) cresce in modo esponenziale.
Quindi, tranne per valori di n molto piccoli, non è possibile enumerare tutte le parentesizzazioni.
Passo 1: struttura di una parentesizzazione ottima
Supponiamo che una parentesizzazione ottima di A1 A2 ... An preveda come ultima operazione il prodotto tra la matrice A1..k (prodotto delle prime k matrici A1 ... Ak) e la matrice Ak+1..n (prodotto delle ultime n-k matrici Ak+1 ... An).Le parentesizzazioni di A1 ... Ak e di Ak+1 ... An sono parentesizzazioni ottime per il calcolo di A1..k e di Ak+1..n .
Perché?
Passo 2: soluzione ricorsiva
Di conseguenza la matrice prodotto parziale Ai..j è una matrice pi-1pj con lo stesso numero pi-1 di righe della prima matrice Ai e lo stesso numero pj di colonne dell’ultima matrice Aj .
Prendiamo come sottoproblemi il calcolo dei prodotti parziali Ai..j delle matrici Ai ... Aj .
Ricordiamo che la generica matrice Ai ha dimensioni pi-1pi .
Se i = j allora Ai..j = Ai ed m[i,i] = 0.
jipppjkmkim
jijim
jkijki
se)],1[],[(min
se0],[
1
Se i < j allora Ai..j = Ai ... Aj si può calcolare come prodotto delle due matrici Ai..k e Ak+1..j con k compreso tra i e j-1.
Il costo di questo prodotto è pi-1 pk pj .
Quindi
Passo 3Esempio
A1 3035A2 3515A3 155A4 510A5 1020A6 2025
i
1 65432
1
2
3
4
5
6
A1..1
0
A2..2
0
A3..3
0
A4..4
0
A5..5
0
A6..6
0
j
30
35
15
5
10
20
p
35 252010515 p
mk
mk
mk
mk
mk
mk
A1..2
157501
A2..3
26252
A3..4
7503
A4..5
10004
A5..6
50005
A1..3
79001
A2..4
43753
A3..5
15004
A4..6
35005
A1..4
94003
A2..5
71253
A3..6
53753
A1..5
119003
A2..6
105003
A1..6
151253
A1..1A2..2: 303515 = 15750A2..2A3..3: 35155 = 2625A1..1A2..3: 0+2650+30355 = 7900A1..2A3..3: 15750+0+30155 = 18000A3..3A4..4: 15510 = 750A2..2A3..4: 0+750+351510 = 6000A2..3A4..4: 2625+0+35510 = 4375A1..1A2..4: 0+4375+303510 = 14875A1..2A3..4: 15750+750+301510 = 21000A1..3A4..4: 7900+0+30510 = 9400
A4..4A5..5: 0+0+51020 = 1000A3..3A4..5: 0+1000+15520 = 2500A3..4A5..5: 750+0+15105 = 1500A2..2A3..5: 0+1500+351520 = 12000A2..3A4..5: 2625+1000+35520 = 7125A2..4A5..5: 4375+0+351020 = 11375
A1..1A2..5: 0+7125+303520 = 28125A1..2A3..5: 15750+1500+301520 = 26250A1..3A4..5: 7900+1000+30520 = 11900A1..4A5..5: 9400+0+301020 = 15400
A5..5A6..6: 0+0+102025 = 5000A4..4A5..6: 0+5000+51025 = 6250A4..5A6..6: 1000+0+52025 = 3500A3..3A4..6: 0+3500+15525 = 5375A3..4A5..6: 750+5000+151025 = 9500A3..5A6..6: 1500+0+152025 = 9000
A2..2A3..6: 0+5375+351525 = 18500A2..3A4..6: 2625+3500+35525 = 10500A2..4A5..6: 750+5000+351025 = 14500A2..5A6..6: 1500+0+352025 = 19000
A1..1A2..6: 0+10500+303525 = 36750A1..2A3..6: 15750+5375+301525 = 32375A1..3A4..6: 7900+3500+30525 = 15150A1..4A5..6: 9400+5000+301025 = 21900A1..5A6..6: 11900+0+302025 = 26900