lunedì 5 marzo 2012

Tecniche di Programmazione: Programmazione Dinamica



In questo post ho cercato di scrivere quello che avevo capito di una delle tecniche di programmazione più note, la programmazione dinamica, basandomi sugli appunti presi a lezione e sul libro di testo (Algoritmi e Strutture Dati di Demetrescu, Italiano, Finocchi edito dalla McGraw Hill). Per qualsiasi suggerimento o altro lasciate un commento o contattateci!

Principio:
Utilizzare una struttura di supporto per memorizzare alcune soluzioni parziali, mediante le quali giungeremo alla soluzione del nostro problema. L'uso di "tabelle" di supporto è utile per evitare di ricalcolare informazioni più volte. Il nome di questa tecnica deriva proprio dalla struttura di supporto: si programma dinamicamente la soluzione finale mediante alcuni passi intermedi presenti nella tabella delle soluzioni. Un approccio che utilizza la programmazione dinamica segue alcuni passi:
  1. Identificare i sottoproblemi e il criterio di scomposizione delle varie soluzioni
  2. Creare una tabella di supporto che conterrà le soluzioni dei sottoproblemi e alcuni valori di “default”, cioè le soluzioni dei sottoproblemi minimi (in genere i sottoproblemi unitari o comunque i più immediati, di cui si dispone già la soluzione)
  3. Utilizzare le soluzioni memorizzate in precedenza per generare la soluzione i-esima, sino ad arrivare alla posizione/soluzione voluta.
Il problema viene scomposto in modo bottom-up, ovvero partiamo dalle soluzioni dei sottoproblemi unitari per calcolare le partizioni del problema più complesse che a loro volta ci serviranno per ottenere la soluzione al problema stesso.


Esempio: Minimizzare il prodotto tra matrici
I metodi per moltiplicare 3 o più matrici sono più di uno e tutti si basano sulla “parentesizzazione” che adottiamo, cioè la priorità che diamo alle varie moltiplicazioni.
Moltiplicare (M1*M2) * M3, in genere, ha un costo diverso che moltiplicare M1*(M2*M3).

Innanzitutto analizziamo il costo di moltiplicazione tra due matrici:

algoritmo MoltiplicaMatrici ( matrice M1, matrice M2 ) matrice
assert (M1.colonne == M2.righe )
Matrice M3 {vuota};
k, i, j 0
for ( i= 0; i < M1.righe; i++)
for ( j=0; j < M2.colonne; j++)
for ( k = 0, k < M1.colonne, k++)
M3 [i] [j] += M1[i] [k] * M2 [k] [j]
return M3;

(Nota: Due matrici si possono moltiplicare solo se il numero di colonne della prima è uguale al numero delle righe della seconda).
Questo semplice algoritmo agisce così:

>>Definisci 3 indici k, i e j e inizializzali a 0. L'indice i serve a scandire le righe di M1, l'indice j scandisce le colonne di M2 e l'indice K ci fa da contatore per far compiere esattamente M1.colonne volte (o M2.righe, che è uguale) l'operazione di moltiplicazione nelle posizioni corrette delle matrici M1 ed M2.

>> Posizionati sulla riga i-esima della matrice M1; posizionati sulla colonna j-esima della matrice M2; esegui la sommatoria della moltiplicazione degli elementi M1[i][k] e M2[k][j] che di fatto significa moltiplicare, due per volta, gli elementi della riga i di M1 e gli elementi della colonna J di M2 e addizionare il loro risultato alla posizione della matrice risultato M3 nella posizione (i,j).P

>>Risulterà che l'elemento M3[i][j] è stato prodotto dalla sommatoria di tutti gli elementi M1[i][k] e M2[k][j] moltiplicati fra loro.
Moltiplicazione tra due matrici. [Wikipedia]

La complessità è di O(n^3) essendoci 3 for innestati. Dunque se L1 ed L2 sono rispettivamente il numero delle righe e il numero delle colonne di una matrice M1, L3 ed L4 indicano la stessa cosa ma su una matrice M2 con il vincolo che L2 sia uguale ad L3, avremo un costo di moltiplicazione pari a:
L1 x L2 x L4
Possiamo notare che, avendo tre matrici o più, il costo varia a seconda dell'ordine di moltiplicazioni che facciamo. Ad esempio:
[ formato : nRighe x nColonne ]

M1 [100 x 300 ]
M2 [300 x 1000]
M3 [1000 x 5]


Analizziamo i costi:

(M1 x M2 ) x M3 = M1/2 x M3;
Ricordiamo che la matrice risultante M1/2 avrà L1 righe ed L3 colonne.
costoTot = costo (M1 x M2) + costo (M1/2 x M3);
costo (M1 x M2 ) = 100 x 300 x 1000 = 30.000.000
costo (M1/2 x M3) = 100 x 1000 x 5 = 500.000

>>costoTot = 30.500.000 operazioni.

Analogamente:
M1 x ( M2 x M3 ) =
M1 x M2/3;
costoTot = costo (M2 x M3 ) + costo (M1 x M2/3)
costo (M2 x M3) = 300 x 1000 x 5 = 1.500.000
costo (M1 x M2/3) = 100 x 300 x 5 = 150.000
>>costoTot = 1.650.000 operazioni

La variazione dei costi dipende proprio dalle dimensioni della matrice risultato delle prime moltiplicazioni: nel primo caso abbiamo a che fare con una matrice M1/2 che ha 100 righe e 1000 colonne; nel secondo caso la matrice M2/3 ha 300 righe e 5 colonne!
Applichiamo una idea che segue la programmazione dinamica per calcolare il costo minore per effettuare le moltiplicazioni e quindi la giusta priorità da dare alle moltiplicazioni delle matrici.
Date un numero di matrici n superiore a 3, i sottoproblemi possono riguardare la moltiplicazione di una parte di questo blocco intero di matrici, ad esempio dalla matrice i alla matrice j. Come problema base, notiamo che se i fosse uguale a j, il costo sarebbe unitario e proprio uguale a 0. Dunque abbiamo trovato i valori da assegnare alla nostra struttura appoggio di programmazione dinamica: tutte le operazioni che coinvolgono la stessa matrice avranno costo 0. Ma, allargando il nostro orizzonte in vista della soluzione finale, avremo bisogno di tutti i costi per poter scegliere il migliore. Adottiamo dunque come struttura dati supporto, una matrice quadrata avente numero di righe/colonne uguale al numero di matrici che vogliamo moltiplicare. La matrice così creata avrà la diagonale principale nulla, dato che i costi di moltiplicazione delle matrici Mi e Mi è 0. In ogni altra casella (i, j) avremo la soluzione OTTIMA del problema adattato alle matrici Mi x Mi+1 x.....x Mj. Infine il passo di avanzamento nella nostra matrice di programmazione dinamica è il seguente:

M [i,j] = M[i,r] + M[r+1,j] + Li * Lr+1 * Lj+1

Ovvero:
Il costo della moltiplicazione fra le matrici [Mi x … x Mj] è uguale al costo della moltiplicazione delle matrici [Mi x …. Mr] sommato al costo della moltiplicazione delle matrici [Mr+1 x …. Mj ] sommato al costo di moltiplicazione di questi due blocchi di matrici che è appunto Li x Lr+1 x Lj+1. Spieghiamo meglio questo svolgimento: noi spezziamo il costo di moltiplicazione tra le matrici (i,j) in 2 tronconi, divisi dall'indice r. Questo indice r, compreso tra i e j-1, fa sì che noi dividiamo il problema in modo tale che possiamo sommare i costi dei due pezzi ( il costo da Mi ad Mr e il costo da Mr+1 ad Mj). Infine dobbiamo sommare il costo della moltiplicazione di questi due pezzi, che è la formula detta in precedenza. (si noti che la matrice risultato del primo blocco avrà righe pari alle righe di Mi e colonne pari alle colonne della matrice Mr ; la matrice risultato del secondo blocco avrà righe pari alle righe della matrice Mr+1 e colonne pari alle colonne della matrice Mj)

Nel nostro algoritmo dobbiamo cercare tutti i possibili valori di r, che fungerà da separatore delle moltiplicazioni; servirà, cioè, a stabilire il vero costo ottimo della moltiplicazioni delle matrici. (per capirci nell'esempio precedente r valeva “2”, dato che M1 x (M2 x M3) era meglio di (M1 x M2) x M3 e dunque poniamo la separazione sulla seconda moltiplicazione).
R sarà calcolato trovando il minimo dei vari costi.

Algoritmo moltiplicazioneOttima ( array InfoMatrici ) intero
n size (InfoMatrici)
matrice M di n x n
for ( i = 1 to n ) do M[i,i] 0
for ( d = 1 to ( n-1) do
for ( i = 1; to (n-d) do
j d +1
M[i,j] MAX_INT
for r = i to (j-1) do
M[i,j] min ( M[i,j], M[i,r] + M [r+1,j] + InfoMatrici[i] * InfoMatrici[r+1] * InfoMatrici[j+1]}
return M[1,n]

Ricevuto un array con le informazioni sulle matrici (nRigheM1,nColonneM1,nColonneM2,nColonneM3 […] ) l'algoritmo crea la matrice M che servirà da supporto e mette a 0 i costi unitari ( M1 x M1, M2 x M2 […] quindi azzera M[i,i]). Una volta fatto questo si pone un indice d, che segnerà la diagonale, che parte da 1 e arriva ad n-1 (ad n c'è uno 0, è inutile). Ad ogni ciclo di d viene fatto partire un indice i che segnerà la nostra riga corrente ed andrà da 1 fino ad n-d, cioé fino alla fine della matrice senza sforarla. L'indice j parte invece dalla prima posizione utile della matrice supporto, cioè da una posizione dopo la diagonale azzerata, e sarà il nostro indice di colonna. Mettiamo il massimo intero rappresentabile ( per simboleggiare infinito) nella posizione i,j della matrice M e procediamo provando tutti gli r: così facendo calcoliamo tutti i costi partizionando l'espressione in tutti i modi possibili e sovrascrivendo la cella i,j con il minore tra questi valori (quello già precedente e quello calcolato nel generico passo i).

Per esempio nella prima chiamata:
i = 1, d = 1, j = 2, r = i = 1.
Stiamo guardando la cella M[1][2] che rappresenta il costo della moltiplicazione tra le matrici M1 x M2. Dato che c'è un unico modo per moltiplicare queste matrici, il ciclo che vede r “protagonista” ciclerà una sola volta: r è uguale ad i ed è già j-1 dato che i è 1 e j è 2. Dunque verrà posizionato nella posizione M[i,j] il valore M[i,i] + M[r+1][j] + Li * Lr+1 * Lj+1, dato che è sicuramente minore di MAX_INT. Il valore sarà M[1,1] (che è zero) + M[1,1] (che è 0 dato che r=i) + M[2,2] ( che è uguale a 0 anch'esso) + il costo di queste due matrici: nRigheM1 x nColonneM1 x nColonneM2, che si possono trovare nell'array contenente le info delle matrici, alle rispettive posizioni ( i, r+1 e j+1 cioé 1,2,3).

In un generico passo l'algoritmo si troverà sulla riga i e confronterà i vari costi della moltiplicazione delle matrici spezzettandole su r; il costo minore rimarrà memorizzato sulla cella opportuna. Da notare che la matrice si crea dinamicamente e che tutte le informazioni utili non vengono ricalcolate, ma vengono “prelevate” dalla matrice dato che essa contiene di volta in volta i costi ottimi. Quindi se per calcolare il costo ottimo del passo i, spezzo le matrici nel punto r, cercherò i costi minimi di quelle due matrici nella tabella.

Foto post: IBM

1 commento: