algorithm
Applicazioni della programmazione dinamica
Ricerca…
introduzione
L'idea alla base della programmazione dinamica è la rottura di un problema complesso fino a diversi piccoli e semplici problemi che vengono ripetuti. Se è possibile identificare un sottoprocesso semplice che viene ripetutamente calcolato, le probabilità sono che vi sia un approccio di programmazione dinamica al problema.
Poiché questo argomento è intitolato Applicazioni di programmazione dinamica , si concentrerà maggiormente sulle applicazioni piuttosto che sul processo di creazione di algoritmi di programmazione dinamica.
Osservazioni
definizioni
Memoizzazione : una tecnica di ottimizzazione utilizzata principalmente per accelerare i programmi di computer memorizzando i risultati di costose chiamate di funzione e restituendo il risultato memorizzato nella cache quando si verificano nuovamente gli stessi input.
Programmazione dinamica : un metodo per risolvere un problema complesso suddividendolo in una raccolta di sottoproblemi più semplici, risolvendo ciascuno di questi sottoproblemi una sola volta e memorizzando le loro soluzioni.
Numeri di Fibonacci
I numeri di Fibonacci sono un argomento privilegiato per la programmazione dinamica poiché l'approccio ricorsivo tradizionale effettua molti calcoli ripetuti. In questi esempi userò il caso base di f(0) = f(1) = 1 .
Ecco un esempio di albero ricorsivo per fibonacci(4) , si noti i calcoli ripetuti: 
Programmazione non dinamica O(2^n) Complessità di runtime, O(n) Complessità dello stack
def fibonacci(n):
if n < 2:
return 1
return fibonacci(n-1) + fibonacci(n-2)
Questo è il modo più intuitivo per scrivere il problema. Al massimo lo spazio di stack sarà O(n) mentre discendi il primo ramo ricorsivo effettuando chiamate a fibonacci(n-1) finché non colpisci il caso base n < 2 .
La prova di complessità di runtime O(2^n) che può essere vista qui: Computational complex of Fibonacci Sequence . Il punto principale da notare è che il runtime è esponenziale, il che significa che il runtime per questo raddoppierà per ogni termine successivo, fibonacci(15) impiegherà il doppio del tempo di fibonacci(14) .
Memoized O(n) Complessità di runtime, O(n) Complessità dello spazio, O(n) Complessità dello stack
memo = []
memo.append(1) # f(1) = 1
memo.append(1) # f(2) = 1
def fibonacci(n):
if len(memo) > n:
return memo[n]
result = fibonacci(n-1) + fibonacci(n-2)
memo.append(result) # f(n) = f(n-1) + f(n-2)
return result
Con l'approccio memoized introduciamo un array che può essere pensato come tutte le chiamate di funzione precedenti. Il memo[n] posizione memo[n] è il risultato della funzione chiamata fibonacci(n) . Ciò ci consente di negoziare la complessità dello spazio di O(n) per un runtime O(n) quanto non è più necessario calcolare chiamate di funzione duplicate.
Programmazione dinamica Iterativa O(n) Complessità di runtime, O(n) Complessità dello spazio, Nessuna pila ricorsiva
def fibonacci(n):
memo = [1,1] # f(0) = 1, f(1) = 1
for i in range(2, n+1):
memo.append(memo[i-1] + memo[i-2])
return memo[n]
Se suddividiamo il problema nei suoi elementi principali, noteremo che per calcolare fibonacci(n) abbiamo bisogno di fibonacci(n-1) e fibonacci(n-2) . Inoltre possiamo notare che il nostro caso base apparirà alla fine di quell'albero ricorsivo come visto sopra.
Con queste informazioni, ora ha senso calcolare la soluzione al contrario, iniziando dai casi base e lavorando verso l'alto. Ora per calcolare fibonacci(n) calcoliamo prima tutti i numeri di fibonacci fino a e attraverso n .
Questo vantaggio principale qui è che ora abbiamo eliminato lo stack ricorsivo mantenendo il tempo di esecuzione di O(n) . Sfortunatamente, abbiamo ancora una complessità di spazio O(n) ma può anche essere modificata.
Programmazione dinamica Iterativa avanzata O(n) Complessità di runtime, O(1) Complessità dello spazio, Nessuna pila ricorsiva
def fibonacci(n):
memo = [1,1] # f(1) = 1, f(2) = 1
for i in range (2, n):
memo[i%2] = memo[0] + memo[1]
return memo[n%2]
Come notato sopra, l'approccio iterativo di programmazione dinamica parte dai casi base e funziona fino al risultato finale. L'osservazione chiave da fare per arrivare alla complessità dello spazio a O(1) (costante) è la stessa osservazione che abbiamo fatto per lo stack ricorsivo - abbiamo solo bisogno di fibonacci(n-1) e fibonacci(n-2) per costruire fibonacci(n) . Ciò significa che dobbiamo solo salvare i risultati per fibonacci(n-1) e fibonacci(n-2) in qualsiasi punto della nostra iterazione.
Per memorizzare questi ultimi 2 risultati, utilizzo una matrice di dimensione 2 e semplicemente capovolgo l'indice a cui sto assegnando usando i % 2 che si alternerà in questo modo: 0, 1, 0, 1, 0, 1, ..., i % 2 .
Aggiungo entrambi gli indici dell'array perché sappiamo che l'addizione è commutativa ( 5 + 6 = 11 e 6 + 5 == 11 ). Il risultato viene quindi assegnato al più vecchio dei due punti (indicato da i % 2 ). Il risultato finale viene quindi memorizzato nella posizione n%2
Gli appunti
- È importante notare che a volte potrebbe essere meglio creare una soluzione memo iterata per funzioni che eseguono ripetuti calcoli di grandi dimensioni mentre si crea una cache della risposta alle chiamate di funzione e le chiamate successive possono essere
O(1)se è già stato calcolato.