In questo tutorial imparerai cos'è la programmazione dinamica. Inoltre, troverai il confronto tra programmazione dinamica e algoritmi avidi per risolvere i problemi.
La programmazione dinamica è una tecnica di programmazione informatica che aiuta a risolvere in modo efficiente una classe di problemi che hanno sottoproblemi sovrapposti e proprietà di sottostruttura ottimali.
Tali problemi implicano il calcolo ripetuto del valore degli stessi sottoproblemi per trovare la soluzione ottimale.
Esempio di programmazione dinamica
Prendiamo il caso di generare la sequenza di Fibonacci.
Se la sequenza è F (1) F (2) F (3)… F (50), segue la regola F (n) = F (n-1) + F (n-2)
F (50) = F (49) + F (48) F (49) = F (48) + F (47) F (48) = F (47) + F (46)…
Nota come ci sono sottoproblemi sovrapposti, dobbiamo calcolare F (48) per calcolare sia F (50) che F (49). Questo è esattamente il tipo di algoritmo in cui brilla la programmazione dinamica.
Come funziona la programmazione dinamica
La programmazione dinamica funziona memorizzando il risultato dei sottoproblemi in modo che quando le loro soluzioni sono richieste, siano a portata di mano e non sia necessario ricalcolarle.
Questa tecnica di memorizzare il valore dei sottoproblemi è chiamata memoizzazione. Salvando i valori nell'array, risparmiamo tempo per i calcoli di problemi secondari che abbiamo già incontrato.
var m = map (0 → 0, 1 → 1) funzione fib (n) se la chiave n non è nella mappa mm (n) = fib (n - 1) + fib (n - 2) return m (n)
La programmazione dinamica mediante memoizzazione è un approccio top-down alla programmazione dinamica. Invertendo la direzione in cui funziona l'algoritmo, cioè partendo dal caso base e lavorando verso la soluzione, possiamo anche implementare la programmazione dinamica in modo bottom-up.
funzione fib (n) if n = 0 return 0 else var prevFib = 0, currFib = 1 repeat n - 1 volte var newFib = prevFib + currFib prevFib = currFib currFib = newFib return currentFib
Ricorsione vs programmazione dinamica
La programmazione dinamica viene applicata principalmente agli algoritmi ricorsivi. Questa non è una coincidenza, la maggior parte dei problemi di ottimizzazione richiede la ricorsione e per l'ottimizzazione viene utilizzata la programmazione dinamica.
Ma non tutti i problemi che utilizzano la ricorsione possono utilizzare la programmazione dinamica. A meno che non vi sia una presenza di sottoproblemi sovrapposti come nel problema della sequenza di Fibonacci, una ricorsione può raggiungere la soluzione solo utilizzando un approccio divide et impera.
Questo è il motivo per cui un algoritmo ricorsivo come Merge Sort non può utilizzare la programmazione dinamica, perché i sottoproblemi non si sovrappongono in alcun modo.
Algoritmi avidi vs programmazione dinamica
Greedy Algorithms sono simili alla programmazione dinamica nel senso che sono entrambi strumenti per l'ottimizzazione.
Tuttavia, gli algoritmi avidi cercano soluzioni ottimali a livello locale o, in altre parole, una scelta avida, nella speranza di trovare un ottimo globale. Quindi gli algoritmi avidi possono fare un'ipotesi che sembra ottimale al momento ma diventa costosa in futuro e non garantisce un ottimo globale.
La programmazione dinamica, d'altra parte, trova la soluzione ottimale ai sottoproblemi e quindi fa una scelta informata per combinare i risultati di quei sottoproblemi per trovare la soluzione ottimale.
