Quanti modi ci sono di salire una scala di 30 gradini facendo passi da uno o da due gradini alla volta? Una soluzione ricorsiva ingenua si scrive in due righe: i modi per arrivare al gradino n sono i modi per arrivare al gradino n − 1 più quelli per arrivare al gradino n − 2. Eseguita così com'è, però, questa funzione per n = 30 fa più di un milione di chiamate, e per n = 50 non termina in tempi ragionevoli. Con una piccola modifica risponde istantaneamente anche per n = 500.
Quella modifica è l'idea centrale della programmazione dinamica (PD): non ricalcolare mai due volte la stessa cosa. Il nome, introdotto da Richard Bellman negli anni Cinquanta, non ha niente a che fare con la programmazione dei computer in senso moderno né con qualcosa di «dinamico»: indica una tecnica di pianificazione per stadi.
Le due condizioni
La programmazione dinamica funziona quando il problema ha due proprietà.
Sottostruttura ottima: la soluzione ottima del problema si costruisce a partire dalle soluzioni ottime di sottoproblemi più piccoli. Per esempio, se il cammino più breve da Milano a Roma passa per Bologna, il suo tratto da Milano a Bologna è a sua volta il cammino più breve tra queste due città.
Sottoproblemi sovrapposti: gli stessi sottoproblemi compaiono più volte. Nella scala, il numero di modi per arrivare al gradino 10 serve sia per calcolare il gradino 11 sia per il 12. Se i sottoproblemi non si ripetono, come nel merge sort, si parla di «divide et impera» e la PD non porta vantaggi.
Memoization: dall'alto verso il basso
Il primo modo di applicare la PD è tenere la ricorsione naturale e aggiungere una cache dei risultati già calcolati:
from functools import lru_cache
@lru_cache(maxsize=None)
def modi(n):
if n <= 1:
return 1
return modi(n - 1) + modi(n - 2)
Ogni valore di n viene calcolato una volta sola; le chiamate successive leggono il risultato dalla cache. Il costo passa da esponenziale a lineare. Questo approccio si chiama memoization ed è il più facile da ottenere partendo da una ricorsione corretta.
Lo svantaggio è la profondità della ricorsione: per n molto grandi si supera il limite dello stack.
Tabulazione: dal basso verso l'alto
Il secondo modo è riempire una tabella a partire dai casi più piccoli, in un ordine che garantisca che ogni valore necessario sia già pronto:
def modi(n):
a, b = 1, 1 # modi per i gradini 0 e 1
for _ in range(n - 1):
a, b = b, a + b
return b if n >= 1 else 1
Qui la tabella si riduce a due variabili, perché ogni valore dipende solo dai due precedenti. Questa riduzione della memoria è frequente: se una riga della tabella dipende solo dalla precedente, basta tenerne due.
| Aspetto | Memoization | Tabulazione |
|---|---|---|
| Ordine di calcolo | deciso dalla ricorsione | deciso dal programmatore |
| Sottoproblemi calcolati | solo quelli necessari | tutti quelli della tabella |
| Rischio di stack overflow | sì | no |
| Ottimizzazione della memoria | difficile | spesso semplice |
Un metodo in cinque passi
Quando si affronta un problema nuovo conviene seguire sempre lo stesso schema.
- Definire lo stato: quale informazione minima descrive un sottoproblema? Per la scala basta il numero del gradino. Per altri problemi servono due o tre indici.
- Scrivere la ricorrenza: come si ottiene il valore di uno stato dai valori di stati più piccoli?
- Fissare i casi base: i sottoproblemi abbastanza piccoli da conoscere la risposta direttamente.
- Scegliere l'ordine di calcolo: gli stati vanno risolti dopo quelli da cui dipendono. In termini di grafi, le dipendenze tra stati formano un DAG, e l'ordine di calcolo è un suo ordinamento topologico.
- Ricostruire la soluzione: oltre al valore ottimo, spesso serve la scelta che lo realizza. Si memorizza, per ogni stato, quale opzione ha dato il migliore risultato, e alla fine si ripercorre la catena.
Un esempio di ottimizzazione: il resto con meno monete
Un distributore deve dare un resto di R centesimi usando monete di certi tagli e vuole usarne il meno possibile. Stato: l'importo r. Ricorrenza: monete(r) = 1 + minimo di monete(r − t) per ogni taglio t ≤ r. Caso base: monete(0) = 0.
Con tagli da 1, 3 e 4 e un resto di 6, l'approccio avido prende prima la moneta più grande (4) e poi due da 1, totale tre monete. La PD trova invece 3 + 3, due monete. È un esempio tipico in cui la scelta che sembra migliore localmente non è quella ottima, e la PD, esaminando sistematicamente tutti i sottoproblemi, non si lascia ingannare.
Dove si incontra
La programmazione dinamica è ovunque nell'informatica: confronto tra testi e versioni di file, correttori ortografici, riconoscimento vocale con l'algoritmo di Viterbi, allineamento di sequenze genetiche, cammini minimi come Bellman-Ford e Floyd-Warshall, problemi dello zaino e di taglio, analisi sintattica di grammatiche, pianificazione di scorte e investimenti nel tempo.
In sintesi
- La PD si applica quando ci sono sottostruttura ottima e sottoproblemi sovrapposti.
- La memoization aggiunge una cache a una ricorsione già corretta.
- La tabulazione riempie una tabella dal basso ed evita i limiti della ricorsione.
- Stato, ricorrenza, casi base, ordine e ricostruzione sono i cinque passi da seguire.
- Dove le scelte avide falliscono, la PD esamina tutte le alternative senza ripetere calcoli.
