Skip to content
Torna ai risultati

Programmazione Dinamica

Introdotto da
Richard Bellman
Anno
1957
Tipo
Exact combinatorial optimization via recursive decomposition
Famiglia
Mathematical programming

Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese

Dimensione del carattere

A cosa serve?

La Programmazione Dinamica (PD) è una tecnica di ottimizzazione esatta introdotta da Richard Bellman nel 1957 per risolvere problemi decisionali a più stadi.

Essa scompone un problema complesso in sotto-problemi più semplici e sovrapposti, risolve ciascun sotto-problema una sola volta e memorizza i risultati per evitare calcoli ridondanti. Basata sul Principio di Ottimalità, la PD garantisce soluzioni globalmente ottimali quando il problema presenta sotto-problemi sovrapposti e una sottostruttura ottima.

L’intuizione alla base del metodo

Immagina di pianificare il percorso più breve attraverso una città trovando prima i percorsi più brevi tra ogni coppia di incroci vicini, per poi combinare queste piccole soluzioni verso l'alto. Invece di riesplorare ogni possibile percorso completo da zero, riutilizzi risposte locali pre-calcolate. La Programmazione Dinamica funziona allo stesso modo: memorizza le soluzioni di piccoli sotto-problemi in modo che la costruzione della risposta completa richieda solo consultazioni di tabelle anziché ripetuti calcoli intensivi.

Storia

Richard Bellman coniò il termine 'programmazione dinamica' nel 1957 mentre lavorava alla RAND Corporation, scegliendo deliberatamente la parola 'programmazione' per riferirsi alla pianificazione piuttosto che alla codifica informatica. Il Principio di Ottimalità da lui enunciato divenne il fondamento teorico per la teoria del controllo, la ricerca operativa e, successivamente, l'apprendimento per rinforzo. Algoritmi classici di PD — l'algoritmo di Dijkstra per il percorso più breve, l'algoritmo di Viterbi e l'algoritmo di Needleman-Wunsch per l'allineamento di sequenze — derivano tutti direttamente dal quadro di Bellman.

Quando usarlo

La Programmazione Dinamica è appropriata quando un problema presenta sotto-problemi sovrapposti e sottostruttura ottima — proprietà comuni nei processi decisionali sequenziali, nell'allocazione delle risorse, nella pianificazione e nei compiti di allineamento di stringhe. Richiede che lo spazio degli stati sia completamente enumerabile e di dimensioni gestibili; il metodo soffre della maledizione della dimensionalità quando le variabili di stato sono molte o continue. Per problemi con spazi degli stati intrattabili, la PD approssimata o l'apprendimento per rinforzo sono alternative preferibili.

Limiti e considerazioni

  • Soffre della maledizione della dimensionalità: i requisiti di memoria e tempo crescono esponenzialmente con il numero di variabili di stato.
  • Richiede la conoscenza a priori completa della struttura di transizione e della funzione di ricompensa; inapplicabile ad ambienti sconosciuti senza approssimazione.
  • Lo spazio degli stati deve essere discreto o discretizzabile; problemi continui ad alta dimensionalità richiedono schemi di approssimazione che sacrificano l'esattezza.
  • La formulazione della corretta rappresentazione dello stato e della relazione di ricorrenza richiede una notevole intuizione specifica del problema.

Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.

Punti di forza

  • Garantisce soluzioni esatte globalmente ottimali per problemi che soddisfano il Principio di Ottimalità.
  • Elimina calcoli ridondanti tramite memoizzazione, ottenendo tempo polinomiale nel numero di stati.
  • Produce una politica ottima esplicita, non solo un valore ottimo, consentendo un supporto decisionale diretto.
  • Ampiamente applicabile in diversi domini, tra cui teoria del controllo, bioinformatica, economia e ricerca operativa.

Applicazioni

  • Problemi di percorso più breve e di routing in reti (varianti di Bellman-Ford, Dijkstra).
  • Allineamento di sequenze in biologia computazionale (algoritmi di Needleman-Wunsch, Smith-Waterman).
  • Allocazione ottimale delle risorse e problemi combinatori di tipo zaino nella ricerca operativa.
  • Riconoscimento vocale e della scrittura a mano tramite l'algoritmo di Viterbi su Modelli di Markov Nascosti.
  • Controllo ottimale e ottimizzazione di portafoglio multi-periodo in economia e ingegneria.

Come funziona

Come funziona

1

Il problema di ottimizzazione complessivo è espresso come una relazione di ricorrenza. Per ogni stato s e stadio decisionale n, la funzione valore V_n(s) è uguale alla migliore ricompensa immediata più il valore scontato dello stato successivo risultante. Questa equazione di Bellman formalizza il Principio di Ottimalità: ogni sotto-percorso di un percorso ottimale deve essere esso stesso ottimale.

Formula
V_n(s) = \max_{a \in A(s)} \left[ r(s,a) + \gamma V_{n-1}(T(s,a)) \right]
2

La ricorrenza viene risolta iterativamente o ricorsivamente. Nell'iterazione del valore, V^*(s) viene aggiornato ripetutamente su tutti gli stati fino alla convergenza, utilizzando la stima corrente dei valori degli stati vicini. Ogni aggiornamento sostituisce il vecchio valore con la migliore ricompensa ottenibile più il valore futuro, propagando informazioni di ottimalità attraverso lo spazio degli stati.

Formula
V^*(s) = \max_{a \in A(s)} \left[ r(s,a) + \gamma V^*(s') \right], \quad s' = T(s,a)
3

I valori calcolati vengono memorizzati in una tabella indicizzata per stato. Gli stati terminali ricevono un valore base di zero (o una ricompensa nota), e tutte le altre voci vengono riempite man mano che i sotto-problemi vengono risolti. La memoizzazione assicura che ogni stato venga valutato al massimo una volta, riducendo la ricerca ricorsiva esponenziale a tempo polinomiale nel numero di stati e stadi.

Formula
\text{Table}[s] = \begin{cases} 0 & \text{if } s \in S_{\text{terminal}} \\ V^*(s) & \text{otherwise} \end{cases}
4

Una volta completata la tabella dei valori, la politica ottima pi^*(s) viene recuperata tramite un semplice passaggio greedy: per ogni stato, si seleziona l'azione che massimizza la ricompensa immediata più il valore memorizzato dello stato successore. Questa estrazione in un unico passaggio è computazionalmente economica e fornisce una regola decisionale deterministica e globalmente ottimale.

Formula
\pi^*(s) = \arg\max_{a \in A(s)} \left[ r(s,a) + \gamma \, \text{Table}[T(s,a)] \right]

Errori comuni

  • Definire una rappresentazione dello stato insufficientemente espressiva porta a ricorrenze errate e soluzioni subottimali.
  • Confondere la memoizzazione top-down con la tabulazione bottom-up può causare errori di stack overflow o un ordinamento errato della valutazione dei sotto-problemi.
  • Applicare la PD a problemi che mancano di sottostruttura ottima (ad esempio, il percorso più lungo in un grafo generale) produce risultati errati senza preavviso.
  • Ignorare la precisione numerica nei calcoli cumulativi delle ricompense può causare sottili errori di ottimalità nelle implementazioni in virgola mobile.

Domande frequenti

Qual è la differenza tra programmazione dinamica e divide-and-conquer?

Entrambi scompongono i problemi in sotto-problemi, ma divide-and-conquer assume sotto-problemi indipendenti risolti una sola volta naturalmente. La programmazione dinamica si rivolge a sotto-problemi sovrapposti — lo stesso sotto-problema appare in più rami — e memorizza i risultati per evitare lavoro ridondante. Senza sotto-problemi sovrapposti, la PD non offre alcun vantaggio computazionale rispetto alla ricorsione diretta.

Quando dovrei usare la memoizzazione top-down rispetto alla tabulazione bottom-up?

La memoizzazione top-down è più facile da implementare direttamente dalla ricorrenza e calcola solo i sotto-problemi necessari, avvantaggiando spazi degli stati sparsi. La tabulazione bottom-up evita l'overhead della ricorsione e i limiti dello stack, si adatta a spazi degli stati densi ed è spesso più veloce in pratica. Scegli top-down quando è difficile prevedere l'insieme dei sotto-problemi necessari, bottom-up quando tutti i sotto-problemi saranno necessari.

Come si relaziona la programmazione dinamica all'apprendimento per rinforzo?

La PD classica richiede un modello completo e noto del Processo Decisionale di Markov (probabilità di transizione e ricompense). L'apprendimento per rinforzo estende le idee della PD a contesti in cui il modello è sconosciuto, utilizzando invece l'esperienza campionata. Algoritmi come Q-learning e metodi di gradiente di politica sono procedure di PD approssimata che apprendono funzioni di valore dall'interazione piuttosto che da un modello esplicito.

Metodi correlati

Fonti

  1. Bellman, R. (1957). Dynamic Programming. Princeton University Press.

    ISBN: 978-0-691-07951-6
    Copiato.