Programmazione dinamica
Da Wikipedia, l'enciclopedia libera.
 |
Questa voce riguardante un argomento di informatica non è ancora stata tradotta completamente dalla lingua inglese. Terminala o riscrivila tu.
Nota: il testo da tradurre potrebbe essere nascosto: vai in modifica per visualizzarlo. |
 |
Nella tecnologia informatica, la programmazione dinamica è un metodo utilizzato per ridurre il tempo di esecuzione di un algoritmo mostrando le proprietà dei sottoproblemi e delle sottostrutture ottimale, come mostrato più avanti.
Indice |
[modifica] Storia
Il termine è stato inizialmente utilizzato negli anni quaranta dal matematico Richard Bellman per descrivere il processo di soluzione dei problemi nei quali sia necessario trovare la migliore soluzione, una dopo l'altra. Nel 1953 affinò il termine ad assumere il significato moderno. Questo metodo fu studiato per l'analisi di sistemi e scopi ingegneristici riconosciuti dall' IEEE.
La parola programmazione in "programmazione dinamica" non ha alcuna particolare attinenza con la programmazione informatica. Originariamente il termine programmazione dinamica si applicava unicamente alla soluzione di alcune tipologie di problemi operativi al di fuori dell'area informatica, esattamente come per la programmazione lineare. Un programma è semplicemente la pianificazione per l'azione che sarà prodotta. Per esempio, una lista mirata di eventi, nel caso di una esibizione, è talvolta chiamata programma. Programmare, in questo caso, significa trovare un piano d'azione accettabile.
[modifica] In generale
Sottostruttura ottimale significa che la soluzione ottimale al sottoproblema può essere utilizzata per trovare la soluzione ottimale dell'intero problema. Per esempio, il cammino minimo ad un punto di arrivo da un vertice in un grafo aciclico può essere trovato calcolando dapprima il cammino minimo al punto di arrivo da tutti i vertici adiacenti, e quindi utilizzarlo per trovare il miglior cammino completo, come mostrato in Figura 1. In generale, è possibile risolvere un problema con una sottostruttura ottimale utilizzando un processo a tre passi:
- Suddividere il problema in sottoproblemi più piccoli.
- Risolvere questi problemi in modo ottimale, utilizzando in modo ricorsivo questo processo a tre passi.
- Usare queste soluzioni ottimali per costruire una soluzione ottimale al problema originale.
I sottoproblemi sono, essi stessi, risolti suddividendoli in sotto-sottoproblemi, e così via, finché non si raggiungano alcuni casi semplici, facili da risolvere.
Dire che un problema ha sottoproblemi sovrapponibili equivale a dire che gli stessi sottoproblemi sono utilizzabili per risolvere diversi problemi più ampi. Per esempio, nella Successione di Fibonacci, F3 = F1 + F2 and F4 = F2 + F3 — il calcolo di ogni numero implica il calcolo di F2. Siccome entrambi F3 e F4 sono necessari per il calcolo di F5, un approccio naïve al calcolo di F5 può condurre a calcolare F2 due o più volte. Ciò si applica ogni qualvolta si presentino problemi sovrapponibili: un approccio naïve potrebbe sprecare del tempo ricalcolando la soluzione ottimale a sottoproblemi già risolti.
Al contrario, per evitare che ciò accada, occorre salvare la soluzione ai problemi già risolti. Quindi, se in seguito si necessita di risolvere lo stesso problema, è possibile riprendere e riutilizzare la soluzione già calcolata. Questo approccio è chiamato memoizzazione (non memorizzazione, anche se questo termine può risultare adeguato). Essendo sicuri che una particolare soluzione non sarà riutilizzata, è possibile liberarsene per risparmiare spazio. In alcuni casi, è possibile calcolare in anticipo delle soluzioni a sottoproblemi, sapendo che successivamente saranno necessarie.
In sostanza la programmazione dinamica fa uso di:
- Sottoproblemi sovrapponibili
- Sottostrutture ottimali
- Memoizzazione
La programmazione dinamica generalmente si basa su uno dei due seguenti approcci:
- Top-down: Il problema è spezzato in sottoproblemi, questi sono risolti, e la soluzione è ricordata, nel caso sia necessario risolverli ancora. Si tratta una combinazione di di ricorsività e memoizzazione.
- Bottom-up: Sono risolti innanzitutto tutti i sottoproblemi che possono essere necessari, e successivamente utilizzati per costruire la soluzione a problemi più ampi. Questo approccio è leggermente migliore come dimensione degli stack e numero di chiamate alle funzioni, ma talvolta risulta non risulta intuitivo prefigurarsi tutti i sottoproblemi necessari alla soluzione di un dato problema.
Alcuni linguaggi di programmazione possono memoizzare automaticamente con speciali estensioni [1] il risultato di una chiamata di funzione con un particolare insieme di argomenti, al fine di velocizzare la valutazione (meccanismo noto come call-by-need). Ciò è possibile solo per funzioni che non presentano effetti collaterali, cosa sempre vera in Haskell, ma raramente in linguaggi imperativi.
[modifica] Esempi
[modifica] Successione di Fibonacci
Una implementazione naïve di una funzione che cerchi lo n-mo membro della Successione di Fibonacci, basato direttamente sulla definizione matematica:
function fib(n)
if n = 0 or n = 1
return n
else
return fib(n − 1) + fib(n − 2)
Notare che se se si chiama fib(5), si produce un labero di chiamate che chiama più volte la medsima funzione sullo stesso valore:
fib(5)fib(4) + fib(3)(fib(3) + fib(2)) + (fib(2) + fib(1))((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
In particolare, fib(2) è stato calcolato interamente per due volte. In esmpi più estesi sono ricalcolati molti più valori di fib, o sottoproblemi, portando ad un algoritmo a tempi esponenziali.
Ora, si supponga di avere un semplice oggetto mappa, m, che mappi ogni valore fib calcolato al proprio risultato, e si modifichi la funzione al fine di utilizzarlo ed aggiornarlo. La funzione risultante richiede solo un tempo O(n) invece che un tempo esponenziale:
var m := map(0 → 1, 1 → 1)
function fib(n)
if map m does not contain key n
m[n] := fib(n − 1) + fib(n − 2)
return m[n]
Questa tecnica di salvataggio dei valori già calcolati è chiamata memoizzzione. Sitratta dell'approccio top-down, visto che prima è stato spezzato il problema in sottoproblemi, poi sono stati calcolati e salvati i valori.
Nel caso dell'approccio bottom-up, prima si calcola il più piccolo valore di fib, poi si costruiscono i valori più grandi a partire da questo. Anche questo metodo richiede un tempo O(n), visto che contiene un ciclo che si ripete n − 1 volte:
function fib(n)
var previousFib := 0, currentFib := 1
repeat n − 1 times
var newFib := previousFib + currentFib
previousFib := currentFib
currentFib := newFib
return currentFib
In entrambi questi esempi, si è calcolato fib(2) solo una volta, e poi lo si è utilizzato per calcolare sia fib(4) che fib(3), invece di calcolarlo ogni volta che quest ultimo valori vengono calcolati.
[modifica] Scacchiera
Si consideri ua scacchiera di n × n caselle, e una funzione costo c(i, j) che ritorni un costo associato alla casella i,j (con i la riga e j la colonna). Per esempio (su una scacchiera 5 × 5),
+---+---+---+---+---+
5 | 6 | 7 | 4 | 7 | 8 |
+---|---|---|---|---+
4 | 7 | 6 | 1 | 1 | 4 |
+---|---|---|---|---+
3 | 3 | 5 | 7 | 8 | 2 |
+---|---|---|---|---+
2 | 2 | 6 | 7 | 0 | 2 |
+---|---|---|---|---+
1 | 7 | 3 | 5 | 6 | 1 |
+---+---+---+---+---+
1 2 3 4 5
tale che c(1, 3) = 5
Si abbia una pedina che possa partire in ogni casella del primo livello e che si voglia conoscere il cammino minimo (somma dei costi delle caselle visitate) per arrivare all'ultimo livello, assumendo che la pedina si possa muovere solo in avanti o in diagonale a sinistra-avanti o destra-avanti. Cioè una pedina in (1,3) può spostarsi su (2,2) (2,3) (2,4)
+---+---+---+---+---+
5 | | | | | |
+---|---|---|---|---+
4 | | | | | |
+---|---|---|---|---+
3 | | | | | |
+---|---|---|---|---+
2 | | x | x | x | |
+---|---|---|---|---+
1 | | | O | | |
+---+---+---+---+---+
1 2 3 4 5
Questo problema mostra una optimal substructure. Cioè la soluzione dell'intero problema risiede nelle soluzioni dei sottoproblemi. Si definisca la funzione q(i, j) come
- q(i, j) = minimo costo per raggiungere la casella (i, j)
Se è possibile trovare i valori di questa funzione per tutte le caselle al livelo n, si prende il minimo e si segue il percorso inverso per arrivare al cammino minimo.
Data un qualsiasi casella, è facile vedere che q(i, j) è uguale al minimo costo per arrivare a qualsiasi delle tre caselle al di sotto (visto che queste sono le uniche dalle quali può essere raggiunta) più c(i, j). Per esempio:
+---+---+---+---+---+
5 | | | | | |
+---|---|---|---|---+
4 | | | A | | |
+---|---|---|---|---+
3 | | B | C | D | |
+---|---|---|---|---+
2 | | | | | |
+---|---|---|---|---+
1 | | | | | |
+---+---+---+---+---+
1 2 3 4 5
Ora si definisca q(i, j) in termini leggermente più geenerali:
Questa equazione è abbastanza diretta. La prima linea e là semplicemente per rendre più semplice la ricorsività. (quando si abbia a che fare con gli angoli, per cui si ha bisogno di una sola ricorsione). La seconda linea dice cosa succede al primo livello, per cui si ha qualcosa da cui partire. La terza linea, la ricorsione, è la parte impotante. É sostanzialmente lo stessa cosa che nell'esempio A,B,C,B. Da questa definizione è possibile creare un codice diretto e ricorsivo per q(i, j). Negli pseudocodici seguenti, n è la dimensione della scacchiera, c(i, j) è la funzione costo, e min() restituisce il minore di una certo numero di valori:
function minCost(i, j)
if j < 1 or j > n
return infinity
else if i = 1
return c(i, j)
else
return min( minCost(i-1, j-1), minCost(i-1, j), minCost(i-1, j+1) ) + c(i, j)
Va notato che questa funzione calcola solo il costo del cammino, non il reale cammino. Si arriverà presto al cammino. Questo, come nell'esempio dei numeri di Fibonacci, è terribilmente lento dato che spreca montagne di tempo per ricalcolare ogni volta il medesimo cammino minimo. Ad ogni modo è possibile calcolarlo molto più velocemente nella modalità bottom-up se si usa un array bidimensionale q[i, j] invece di una funzione. Perché lo si fa? Semplicemente perché quando si unsa una funzione si ricomputa ogni volta lo stesso cammino, ed è possibile scegliere in precedenza quaule valore calcolare.
C'è anche bisogno di sapere qual è il reale cammino. Il problema del cammino può essere risolto utilizzando un altro array p[i, j], un array predecessore. Questo array in sostanza dice qual è il cammino di provenienza. Si considerei il seguente codica:
function computeShortestPathArrays()
for x from 1 to n
q[1, x] := c(1, x)
for y from 1 to n
q[y, 0] := infinity
q[y, n + 1] := infinity
for y from 2 to n
for x from 1 to n
m := min(q[y-1, x-1], q[y-1, x], q[y-1, x+1])
q[y, x] := m + c(y, x)
if m = q[y-1, x-1]
p[y, x] := -1
else if m = q[y-1, x]
p[y, x] := 0
else
p[y, x] := 1
Ora il problema è semplicemente quello di individuare il minimo e stamparlo.
function computeShortestPath()
computeShortestPathArrays()
minIndex := 1
min := q[n, 1]
for i from 2 to n
if q[n, i] < min
minIndex := i
min := q[n, i]
printPath(n, minIndex)
function printPath(y, x)
print(x)
print("<-")
if y = 2
print(x + p[y, x])
else
printPath(y-1, x + p[y, x])
