---
title: "Programmazione dinamica"
source: "https://systems-analysis.info/int/Programmazione_dinamica"
wiki: "systems-analysis.info/int"
article: "Programmazione_dinamica"
language: "it"
categories:
  - "Category:Italian"
  - "Category:Operations research"
revision_id: 5894
wiki_created_at: 2026-09-06T23:55:32Z
wiki_modified_at: 2026-09-06T23:55:32Z
downloaded_at: 2026-09-07T23:10:55Z
---

# 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<sup>[\[1\]](https://systems-analysis.info/int/Programmazione_dinamica#cite_note-bigenc-dp-1)[\[2\]](https://systems-analysis.info/int/Programmazione_dinamica#cite_note-ru-wiki-dp-2)</sup>. 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<sup>[\[3\]](https://systems-analysis.info/int/Programmazione_dinamica#cite_note-rechetnikov-dp-3)</sup>. 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<sup>[\[4\]](https://systems-analysis.info/int/Programmazione_dinamica#cite_note-en-wiki-dp-4)</sup>.

## 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<sup>[\[3\]](https://systems-analysis.info/int/Programmazione_dinamica#cite_note-rechetnikov-dp-3)</sup>.

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**<sup>[\[1\]](https://systems-analysis.info/int/Programmazione_dinamica#cite_note-bigenc-dp-1)</sup>. 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) = \max\limits_{y \in U(x)}\{\varphi_{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$;
- $\varphi_{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<sup>[\[5\]](https://systems-analysis.info/int/Programmazione_dinamica#cite_note-mit-amp-5)</sup>.
- **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<sup>[\[6\]](https://systems-analysis.info/int/Programmazione_dinamica#cite_note-ru-wiki-curse-6)[\[7\]](https://systems-analysis.info/int/Programmazione_dinamica#cite_note-utexas-ormm-7)</sup>. 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

<sup>[\[1\]](https://systems-analysis.info/int/Programmazione_dinamica#cite_note-bigenc-dp-1)</sup> <sup>[\[2\]](https://systems-analysis.info/int/Programmazione_dinamica#cite_note-ru-wiki-dp-2)</sup> <sup>[\[3\]](https://systems-analysis.info/int/Programmazione_dinamica#cite_note-rechetnikov-dp-3)</sup> <sup>[\[4\]](https://systems-analysis.info/int/Programmazione_dinamica#cite_note-en-wiki-dp-4)</sup> <sup>[\[5\]](https://systems-analysis.info/int/Programmazione_dinamica#cite_note-mit-amp-5)</sup> <sup>[\[6\]](https://systems-analysis.info/int/Programmazione_dinamica#cite_note-ru-wiki-curse-6)</sup> <sup>[\[7\]](https://systems-analysis.info/int/Programmazione_dinamica#cite_note-utexas-ormm-7)</sup> \</references\>

1.  <span id="cite_note-bigenc-dp-1">↑ <sup>[1.0](https://systems-analysis.info/int/Programmazione_dinamica#cite_ref-bigenc-dp_1-0)</sup> <sup>[1.1](https://systems-analysis.info/int/Programmazione_dinamica#cite_ref-bigenc-dp_1-1)</sup> <sup>[1.2](https://systems-analysis.info/int/Programmazione_dinamica#cite_ref-bigenc-dp_1-2)</sup> "Динамическое программирование". *Большая российская энциклопедия*. <a href="https://bigenc.ru/c/dinamicheskoe-programmirovanie-00423a" class="external autonumber" rel="nofollow">[1]</a></span>
2.  <span id="cite_note-ru-wiki-dp-2">↑ <sup>[2.0](https://systems-analysis.info/int/Programmazione_dinamica#cite_ref-ru-wiki-dp_2-0)</sup> <sup>[2.1](https://systems-analysis.info/int/Programmazione_dinamica#cite_ref-ru-wiki-dp_2-1)</sup> "Динамическое программирование". *Википедия*. <a href="https://ru.wikipedia.org/wiki/Динамическое_программирование" class="external autonumber" rel="nofollow">[2]</a></span>
3.  <span id="cite_note-rechetnikov-dp-3">↑ <sup>[3.0](https://systems-analysis.info/int/Programmazione_dinamica#cite_ref-rechetnikov-dp_3-0)</sup> <sup>[3.1](https://systems-analysis.info/int/Programmazione_dinamica#cite_ref-rechetnikov-dp_3-1)</sup> <sup>[3.2](https://systems-analysis.info/int/Programmazione_dinamica#cite_ref-rechetnikov-dp_3-2)</sup> Решетников А. Н., Коченков А. В., Пиров Д. М., Рябоконь Д. А. (2011). *Динамическое программирование. Примеры применения*. Учебное пособие, ННГУ им. Лобачевского (ВМиК). <a href="https://itslearningakarmazyan.files.wordpress.com/2015/09/dynamic-programming.pdf" class="external autonumber" rel="nofollow">[3]</a></span>
4.  <span id="cite_note-en-wiki-dp-4">↑ <sup>[4.0](https://systems-analysis.info/int/Programmazione_dinamica#cite_ref-en-wiki-dp_4-0)</sup> <sup>[4.1](https://systems-analysis.info/int/Programmazione_dinamica#cite_ref-en-wiki-dp_4-1)</sup> "Dynamic programming". *Wikipedia*. <a href="https://en.wikipedia.org/wiki/Dynamic_programming" class="external autonumber" rel="nofollow">[4]</a></span>
5.  <span id="cite_note-mit-amp-5">↑ <sup>[5.0](https://systems-analysis.info/int/Programmazione_dinamica#cite_ref-mit-amp_5-0)</sup> <sup>[5.1](https://systems-analysis.info/int/Programmazione_dinamica#cite_ref-mit-amp_5-1)</sup> Bradley S. P., Hax A. C., Magnanti T. L. (1977). *Applied Mathematical Programming*. Addison-Wesley. <a href="http://web.mit.edu/15.053/www/AMP-Chapter-11.pdf" class="external autonumber" rel="nofollow">[5]</a></span>
6.  <span id="cite_note-ru-wiki-curse-6">↑ <sup>[6.0](https://systems-analysis.info/int/Programmazione_dinamica#cite_ref-ru-wiki-curse_6-0)</sup> <sup>[6.1](https://systems-analysis.info/int/Programmazione_dinamica#cite_ref-ru-wiki-curse_6-1)</sup> "Проклятие размерности". *Википедия*. <a href="https://ru.wikipedia.org/wiki/Проклятие_размерности" class="external autonumber" rel="nofollow">[6]</a></span>
7.  <span id="cite_note-utexas-ormm-7">↑ <sup>[7.0](https://systems-analysis.info/int/Programmazione_dinamica#cite_ref-utexas-ormm_7-0)</sup> <sup>[7.1](https://systems-analysis.info/int/Programmazione_dinamica#cite_ref-utexas-ormm_7-1)</sup> Jensen P. A. (2004). *Dynamic Programming – Models*. Operations Research Models and Methods, Univ. of Texas. <a href="https://utw11041.utweb.utexas.edu/ORMM/models/unit/dynamic/index.html" class="external autonumber" rel="nofollow">[7]</a></span>