Programmazione dinamica

La programmazione dinamica (PD; ingl. dynamic programming, DP) è un metodo per la risoluzione di problemi complessi di ottimizzazione, basato sulla scomposizione del problema originale in una sequenza di sottoproblemi più semplici. Il metodo si applica a processi decisionali a più fasi, in cui la soluzione ottimale dell'intero problema può essere costruita a partire dalle soluzioni ottimali dei suoi sottoproblemi.

Il termine fu introdotto dal matematico americano Richard Bellman negli anni '50. In questo contesto, la parola «programmazione» è usata nel significato di «pianificazione» o «elaborazione di un piano d'azione ottimale», e non di scrittura di codice informatico.

Proprietà fondamentali e teoremi

L'applicabilità della programmazione dinamica a un problema è determinata dalla presenza di due proprietà fondamentali.

Principio di ottimalità di Bellman

Il concetto centrale del metodo è il principio di ottimalità di Bellman (ingl. Bellman's principle of optimality). Esso afferma: qualunque siano lo stato iniziale e la decisione iniziale, le decisioni successive devono costituire una strategia ottimale rispetto allo stato risultante dalla prima decisione.

In altre parole, qualsiasi parte di una traiettoria ottimale è essa stessa ottimale. Questa proprietà consente di scomporre il problema generale in una sequenza di sottoproblemi più semplici e di risolverli in modo ricorsivo.

Sottoproblemi sovrapposti

Un problema possiede la proprietà dei sottoproblemi sovrapposti (ingl. overlapping subproblems) se, durante la sua risoluzione ricorsiva, gli stessi sottoproblemi si presentano più volte. La PD permette di evitare calcoli ripetuti memorizzando le soluzioni dei sottoproblemi già incontrati (questa tecnica è chiamata memoizzazione o tabulazione), il che aumenta significativamente l'efficienza rispetto alla ricerca ricorsiva ingenua.

Equazione di Bellman

Dal principio di ottimalità deriva la relazione di ricorrenza fondamentale del metodo: l'equazione di Bellman. Essa collega il «valore» (guadagno ottimale o costo) dello stato corrente con i valori degli stati successivi. In forma generale, per un processo deterministico a più fasi con funzione obiettivo additiva, essa assume la forma:

$V_{k-1}(x)=\underset{y\in U(x)}{max}\{{\phi }_k(x,y)+V_k(f_k(x,y))\}$

dove:

• $k$ — numero del passo (da $m$ a 1);
• $x$ — stato del sistema al passo $k-1$;
• $y$ — decisione di controllo presa al passo $k$;
• ${\phi }_k(x,y)$ — guadagno (o costo) al passo k;
• $f_k(x,y)$ — funzione che definisce il nuovo stato del sistema;
• $V_k(s)$ — valore ottimale della funzione obiettivo per il sottoproblema che inizia al passo $k$ nello stato $s$.

L'equazione viene risolta in modo sequenziale, di norma «partendo dalla fine», procedendo dall'ultimo passo al primo.

Esempi di applicazione

• Problema del cammino minimo in un grafo: Questo problema possiede la proprietà della sottostruttura ottimale, poiché qualsiasi segmento del cammino minimo è esso stesso un cammino minimo. Gli algoritmi di Bellman-Ford e di Floyd-Warshall sono esempi classici di applicazione della PD per la risoluzione di questo problema.
• Problema dello zaino: Il problema del riempimento ottimale di uno zaino di capacità limitata con oggetti di diverso valore e peso. La PD consente di risolvere questo problema esaminando gli oggetti in sequenza e calcolando a ogni passo il valore massimo per tutti i possibili valori della capacità rimanente.
• Problema di allocazione delle risorse: Distribuzione di una risorsa limitata (ad esempio, investimenti) tra più progetti al fine di massimizzare l'effetto complessivo.

Limitazioni

Il principale limite del metodo è la maledizione della dimensionalità (ingl. curse of dimensionality) — termine introdotto da Bellman per designare la crescita esponenziale del numero di stati e, di conseguenza, della complessità computazionale, all'aumentare del numero di variabili che descrivono lo stato del sistema. Ciò limita l'applicazione pratica della PD esatta a problemi di dimensioni molto elevate.

Concetti correlati

• Ricerca operativa
• Teoria del controllo ottimale
• Processo decisionale di Markov (generalizzazione stocastica)
• Equazione di Hamilton — Jacobi — Bellman (analogo per il tempo continuo)

Note

</references>