Rilasciato · in miglioramento
Algorithm
La programmazione dinamica memorizza e riutilizza le soluzioni dei sottoproblemi sovrapposti, trasformando ricerche esponenziali in algoritmi tabellari.
La programmazione dinamica (DP) è una tecnica di progettazione degli algoritmi che scompone un problema in sottoproblemi più piccoli, risolve ciascuno una sola volta, ne memorizza la risposta e la riutilizza ogni volta che lo stesso sottoproblema si ripresenta. Formalizzata da Richard Bellman negli anni Cinquanta, si applica quando i sottoproblemi si sovrappongono e quando una soluzione ottima si può costruire a partire dalle soluzioni ottime dei sottoproblemi.
Molti problemi che con la ricorsione semplice o la forza bruta richiedono tempo esponenziale si risolvono così in un tempo proporzionale al numero di stati. La programmazione dinamica è alla base degli strumenti diff, della distanza di edit nei correttori ortografici, dell'allineamento di sequenze di DNA, dell'algoritmo di Viterbi nel riconoscimento vocale e della scelta dell'ordine dei join negli ottimizzatori dei database. È anche uno degli argomenti più frequenti nei colloqui tecnici.
Per iniziare, usa Fibonacci per capire la differenza tra memoizzazione (top-down) e tabulazione (bottom-up), poi affronta i classici: resto con il minor numero di monete, zaino 0/1, sottosequenza crescente più lunga, sottosequenza comune più lunga e distanza di edit. Per ogni problema scrivi prima lo stato, la ricorrenza, i casi base e l'ordine di calcolo, verifica la ricorrenza riempiendo a mano una piccola tabella e solo dopo scrivi il codice.
Quando lo stesso sottoproblema compare più volte viene calcolato una sola volta e salvato, così il lavoro ripetuto diventa una lettura dalla tabella.
Una soluzione ottima deve potersi costruire da soluzioni ottime dei sottoproblemi; è questa proprietà a giustificare la ricorrenza.
Si implementa top-down aggiungendo una cache alla ricorsione (functools.cache) oppure bottom-up riempiendo una tabella con dei cicli.
Lo stato contiene solo i parametri che determinano la risposta e, con gli array a scorrimento, in memoria restano solo le righe necessarie.
knapsack risolve il problema dello zaino 0/1 in modo bottom-up con una sola riga, scorrendo le capacità dalla più grande alla più piccola perché ogni oggetto sia usato al massimo una volta. lcs calcola la lunghezza della sottosequenza comune più lunga in modo top-down, con memoizzazione tramite functools.cache. Eseguendo python dynamic_programming.py si ottengono 9 e 4.
dynamic_programming.py
from functools import cache
def knapsack(weights, values, capacity):
"""0/1 knapsack: best total value within capacity (bottom-up, one row)."""
best = [0] * (capacity + 1)
for w, v in zip(weights, values):
for c in range(capacity, w - 1, -1): # high to low: each item used at most once
best[c] = max(best[c], best[c - w] + v)
return best[capacity]
def lcs(a, b):
"""Length of the longest common subsequence (top-down, memoized)."""
@cache
def solve(i, j):
if i == len(a) or j == len(b):
return 0
if a[i] == b[j]:
return 1 + solve(i + 1, j + 1)
return max(solve(i + 1, j), solve(i, j + 1))
return solve(0, 0)
print(knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7)) # 9
print(lcs("ABCBDAB", "BDCABA")) # 4
python dynamic_programming.pySei capitoli che ti accompagnano dall'installazione ai concetti chiave di Programmazione dinamica.
Fai domande, condividi la tua esperienza e scambia opinioni su Programmazione dinamica.
Ancora nessuna discussione. Avvia la prima.
0 commenti
Accedi · Accedi per lasciare un commento.
Scrivi tu il primo commento.