Programmazione dinamica

La programmazione dinamica è un metodo di ricerca operativa, ottimizzazione e algoritmica che risolve problemi complessi scomponendoli in sottoproblemi più piccoli collegati da una ricorrenza. È particolarmente efficace quando una decisione attuale modifica lo stato del sistema e lascia un problema residuo dello stesso tipo.

L’idea è associata a Richard Bellman e al principio di ottimalità: se una politica è ottima, allora dopo la prima decisione anche la politica residua deve essere ottima per lo stato raggiunto. In altre parole, una soluzione globale può essere costruita a partire da soluzioni ottime locali, purché lo stato conservi tutte le informazioni rilevanti.

Idea fondamentale

Un problema è adatto alla programmazione dinamica quando possiede due proprietà:

Proprietà	Significato operativo
sottostruttura ottima	una soluzione ottima contiene soluzioni ottime di sottoproblemi
sottoproblemi sovrapposti	gli stessi sottoproblemi ricompaiono molte volte durante il calcolo

La prima proprietà giustifica la ricorrenza. La seconda giustifica la memorizzazione: invece di ricalcolare lo stesso valore più volte, lo si calcola una sola volta e lo si riusa.

Questo distingue la programmazione dinamica da una semplice ricorsione. Una ricorsione ingenua può esplorare ripetutamente gli stessi rami; una formulazione dinamica riconosce gli stati equivalenti e li raccoglie in una tabella o in una memoria.

Stato, azione e valore

Una formulazione dinamica richiede tre elementi:

uno stato $s$ , che riassume la situazione corrente;
un insieme di azioni ammissibili $A(s)$ ;
una funzione valore $V(s)$ o $V_t(s)$ , che misura il costo ottimo residuo o il beneficio massimo ottenibile.

Nei problemi a orizzonte finito si usa spesso un indice temporale $t$ ; la ricorrenza risultante è una forma dell’equazione di Bellman:

V_t(s)= \min_{a\in A(s)} \left\{ c_t(s,a)+V_{t+1}(T(s,a)) \right\}.

$s$ è lo stato corrente, $a$ è l’azione scelta, $c_t(s,a)$ è il costo immediato, $T(s,a)$ è la transizione deterministica allo stato successivo e $V_{t+1}$ è il valore ottimo del problema residuo.

Se invece l’obiettivo è massimizzare un ricavo, una probabilità di successo o un punteggio, la stessa struttura si scrive con $\max$ al posto di $\min$ .

Condizione terminale

La ricorrenza da sola non basta: serve una condizione terminale. Per un orizzonte $T$ si assegna un valore finale:

V_T(s)=g(s),

dove $g(s)$ è costo finale, penalità terminale o valore residuo. Il calcolo procede poi all’indietro:

V_{T-1},\ V_{T-2},\ \ldots,\ V_0.

Questo metodo è detto backward induction. È naturale nei problemi in cui le scelte sono ordinate nel tempo: pianificazione della produzione, scorte, manutenzione, scheduling, controllo ottimo discreto, budget di investimento, percorsi su grafi aciclici.

Memoizzazione e tabulazione

Esistono due modi comuni per implementare la programmazione dinamica:

Approccio	Come lavora	Quando conviene
memoizzazione	ricorsione top-down con cache dei valori già calcolati	quando solo una parte degli stati è effettivamente raggiungibile
tabulazione	riempimento bottom-up di una tabella ordinata	quando l’ordine dei sottoproblemi è chiaro e la griglia degli stati è gestibile

La memoizzazione mantiene la forma naturale della ricorsione; la tabulazione rende esplicito l’ordine di calcolo. In entrambi i casi l’obiettivo è lo stesso: ogni stato rilevante deve essere valutato una volta sola.

Esempio: zaino zero-uno

Nel problema dello zaino zero-uno si hanno oggetti con valore $v_i$ , peso $w_i$ e capacità totale $C$ . Ogni oggetto può essere preso oppure escluso. Definiamo:

F(i,c)= \text{valore massimo ottenibile usando i primi } i \text{ oggetti con capacità } c.

Le condizioni iniziali sono:

F(0,c)=0, \qquad F(i,0)=0.

Se l’oggetto $i$ può entrare nella capacità residua, cioè se $w_i\le c$ , la ricorrenza è:

F(i,c)= \max \left\{ F(i-1,c),\ F(i-1,c-w_i)+v_i \right\}.

I due termini rappresentano le due alternative: non prendere l’oggetto $i$ , oppure prenderlo e aggiungere il suo valore consumando capacità.

Se invece $w_i$ supera la capacità disponibile, l’oggetto non può essere scelto:

F(i,c)= F(i-1,c).

La complessità della tabella è proporzionale a $nC$ , dove $n$ è il numero di oggetti. Questo è un punto delicato: il metodo è efficiente quando $C$ è moderata, ma non rende il problema dello zaino facile in senso assoluto se i pesi sono grandi o non interi.

Esempio: cammini minimi

La programmazione dinamica compare anche nei problemi di cammino minimo e più in generale nell’ottimizzazione su reti. Se $d_j$ è il costo minimo per raggiungere il nodo $j$ , una forma di ricorrenza è:

d_j= \min_{(i,j)\in A} \left\{ d_i+c_{ij} \right\}, \qquad d_s=0.

La quantità $c_{ij}$ è il costo dell’arco da $i$ a $j$ , mentre $s$ è la sorgente. Il principio è lo stesso: se il cammino ottimo verso $j$ passa per $i$ , allora il tratto fino a $i$ deve essere già ottimo.

Su grafi aciclici il calcolo segue un ordinamento topologico. Su reti più generali servono algoritmi specializzati, come Dijkstra o Bellman-Ford, ma l’idea di rilassare ricorrenze di ottimalità resta la stessa.

Caso stocastico

Quando la transizione non è deterministica, la ricorrenza include un valore atteso. Una forma tipica è:

V_t(s)= \min_{a\in A(s)} \left\{ c_t(s,a)+ \mathbb{E} \left[ V_{t+1}(S_{t+1}) \mid S_t=s,\ A_t=a \right] \right\}.

Se gli stati successivi sono discreti, l’attesa si può scrivere come somma:

V_t(s)= \min_{a\in A(s)} \left\{ c_t(s,a)+ \sum_{s'}p(s'\mid s,a)V_{t+1}(s') \right\}.

Questa forma collega la programmazione dinamica a decisioni in incertezza, programmazione stocastica, catene di Markov, processi decisionali di Markov e apprendimento per rinforzo. Nei problemi di controllo si ritrova anche nelle ricorrenze di costo associate a modelli lineari quadratici, come l’equazione algebrica di Riccati e la ricorsione di Riccati discreta.

Complessità e maledizione della dimensionalità

La programmazione dinamica è potente quando lo stato è compatto. Il costo di calcolo dipende spesso dal prodotto:

\text{numero di stati} \times \text{numero di azioni} \times \text{numero di stadi}.

Se lo stato ha molte componenti, la tabella può crescere in modo esplosivo. Per esempio, discretizzare $m$ variabili con $q$ livelli ciascuna produce:

q^m

stati possibili. Questo fenomeno è la maledizione della dimensionalità: aggiungere una variabile di stato può moltiplicare il costo computazionale, non soltanto aumentarlo di poco.

Per questo nei casi reali si usano approssimazioni, decomposizioni, euristiche, metodi Monte Carlo, apprendimento per rinforzo o formulazioni alternative, soprattutto quando il modello ha stato continuo o incertezza elevata.

Differenza rispetto ad altre programmazioni

Il termine “programmazione” può confondere. Nella programmazione lineare e nella programmazione intera indica una classe di modelli di ottimizzazione con variabili e vincoli espliciti. Nella programmazione dinamica indica invece una tecnica ricorsiva per problemi sequenziali.

Le famiglie possono però interagire. Un problema di pianificazione può avere variabili intere, vincoli lineari e struttura temporale; a quel punto si può scegliere se modellarlo come programma intero, come ricorrenza dinamica o come combinazione dei due. La scelta dipende da dimensione, struttura, accuratezza richiesta e disponibilità di algoritmi efficienti.

Applicazioni

Applicazioni tipiche includono:

Ambito	Esempi
gestione industriale	scorte, lotti, manutenzione, sostituzione di macchine
logistica	instradamento, carico, scheduling, reti acicliche
finanza	allocazione di portafoglio, esercizio di opzioni, decisioni multiperiodali
informatica	allineamento di sequenze, parsing, cammini minimi, compressione
automatica	controllo ottimo discreto, regolazione con costo quadratico
intelligenza artificiale	processi decisionali di Markov e apprendimento per rinforzo

Il criterio ingegneristico è sempre lo stesso: la formulazione deve rendere lo stato abbastanza ricco da prevedere il futuro, ma abbastanza compatto da essere calcolabile.

Errori comuni

Un primo errore è scegliere uno stato incompleto. Se lo stato non contiene una variabile necessaria per determinare costi e transizioni future, la ricorrenza diventa falsa anche se le formule sembrano corrette.

Un secondo errore è usare la programmazione dinamica quando non c’è sottostruttura ottima. Se una scelta locale modifica vincoli futuri in modo non riassumibile dallo stato, i sottoproblemi non sono indipendenti nel modo richiesto.

Un terzo errore è ignorare la dimensione della tabella. Una ricorrenza elegante può essere inutilizzabile se il numero di stati cresce troppo. Prima di implementare il metodo bisogna stimare memoria, tempo di calcolo e granularità della discretizzazione.