dynamic-programming Tutorial
Iniziare con la programmazione dinamica

Osservazioni

Introduzione alla programmazione dinamica

La programmazione dinamica risolve i problemi combinando le soluzioni ai sottoproblemi. Può essere analogo al metodo divide e conquista, in cui il problema è suddiviso in sottoproblemi disgiunti, i sottoproblemi vengono risolti in modo ricorsivo e quindi combinati per trovare la soluzione del problema originale. Al contrario, la programmazione dinamica si applica quando i sottoproblemi si sovrappongono, ovvero quando i sottoproblemi condividono problemi secondari. In questo contesto, un algoritmo divide et impera fa più lavoro del necessario, risolvendo ripetutamente i problemi secondari comuni. Un algoritmo di programmazione dinamica risolve ogni sottosproblema una sola volta e poi salva la sua risposta in una tabella, evitando così il lavoro di ricalcolare la risposta ogni volta che risolve ogni sottosistema.

Diamo un'occhiata a un esempio. Il matematico italiano Leonardo Pisano Bigollo , che comunemente conosciamo come Fibonacci, ha scoperto una serie numerica considerando la crescita idealizzata della popolazione di conigli . La serie è:

1, 1, 2, 3, 5, 8, 13, 21, ......

Possiamo notare che ogni numero dopo i primi due è la somma dei due numeri precedenti. Ora, formuliamo una funzione F (n) che ci restituirà l'ennesimo numero di Fibonacci, che significa,

F(n) = nth Fibonacci Number

Finora, lo sapevamo,

F(1) = 1
F(2) = 1
F(3) = F(2) + F(1) = 2
F(4) = F(3) + F(2) = 3

Possiamo generalizzarlo con:

F(1) = 1
F(2) = 1
F(n) = F(n-1) + F(n-2)

Ora se vogliamo scriverlo come funzione ricorsiva, abbiamo F(1) e F(2) come nostro caso base. Quindi la nostra funzione Fibonacci sarebbe:

Procedure F(n):                //A function to return nth Fibonacci Number
if n is equal to 1
    Return 1
else if n is equal to 2
    Return 1
end if
Return F(n-1) + F(n-2)

Ora, se chiamiamo F(6) , chiameremo F(5) e F(4) , che chiameremo ancora. Rappresentiamo graficamente questo:

Dalla foto, possiamo vedere che F(6) chiamerà F(5) e F(4) . Ora F(5) chiamerà F(4) e F(3) . Dopo aver calcolato F(5) , possiamo sicuramente dire che tutte le funzioni chiamate da F(5) sono già state calcolate. Ciò significa che abbiamo già calcolato F(4) . Ma stiamo ancora calcolando F(4) come indica il figlio destro di F(6) . Abbiamo davvero bisogno di ricalcolare? Quello che possiamo fare è, una volta calcolato il valore di F(4) , lo memorizzeremo in un array chiamato dp e lo riutilizzeremo quando necessario. Inizializzeremo il nostro array dp con -1 (o qualsiasi valore che non verrà nel nostro calcolo). Quindi chiameremo F (6) dove apparirà la nostra F (n) modificata:

Procedure F(n):
if n is equal to 1
    Return 1
else if n is equal to 2
    Return 1
else if dp[n] is not equal to -1            //That means we have already calculated dp[n]
    Return dp[n]
else
    dp[n] = F(n-1) + F(n-2)
    Return dp[n]
end if

Abbiamo svolto lo stesso compito di prima, ma con una semplice ottimizzazione. Cioè, abbiamo usato la tecnica di memoizzazione . All'inizio, tutti i valori dell'array dp saranno -1 . Quando viene chiamato F(4) , controlliamo se è vuoto o no. Se memorizza -1 , calcoleremo il suo valore e lo memorizzeremo in dp [4] . Se memorizza qualcosa tranne -1 , ciò significa che abbiamo già calcolato il suo valore. Quindi restituiremo semplicemente il valore.

Questa semplice ottimizzazione mediante la memoizzazione si chiama programmazione dinamica .

Un problema può essere risolto utilizzando la programmazione dinamica se ha alcune caratteristiche. Questi sono:

• sottoproblemi:
  Un problema DP può essere suddiviso in uno o più sottoproblemi. Ad esempio: F(4) può essere suddiviso in sottoproblemi più piccoli F(3) e F(2) . Poiché i sottoproblemi sono simili al nostro problema principale, questi possono essere risolti utilizzando la stessa tecnica.
• Sottoproblemi sovrapposti:
  Un problema DP deve avere sottoproblemi sovrapposti. Ciò significa che deve esserci una parte comune per cui la stessa funzione viene chiamata più di una volta. Ad esempio: F(5) e F(6) hanno F(3) e F(4) in comune. Questo è il motivo per cui abbiamo memorizzato i valori nel nostro array.

• Sottostruttura ottimale:
  Diciamo che ti viene chiesto di minimizzare la funzione g(x) . Sai che il valore di g(x) dipende da g(y) e g(z) . Ora, se possiamo minimizzare g(x) minimizzando entrambi g(y) e g(z) , solo allora possiamo dire che il problema ha una sottostruttura ottimale. Se g(x) è minimizzato minimizzando solo g(y) e se minimizzare o massimizzare g(z) non ha alcun effetto su g(x) , allora questo problema non ha una sottostruttura ottimale. In parole semplici, se è possibile trovare la soluzione ottimale di un problema dalla soluzione ottimale del suo sottoproblema, allora possiamo dire che il problema ha una proprietà di sottostruttura ottimale.

Comprensione dello stato nella programmazione dinamica

Discutiamo con un esempio. Da n elementi, in quanti modi puoi scegliere r elementi? Sai che è denotato da . Ora pensa a un singolo oggetto.

• Se non selezioni l'oggetto, dopo di ciò devi prendere r oggetti dai rimanenti n-1 elementi, che è dato da .
• Se selezioni l'oggetto, dopo devi prendere gli oggetti r-1 dai restanti n-1 elementi, che è dato da .

La sommatoria di questi due ci dà il numero totale di modi. Questo è:

Se pensiamo a nCr(n,r) come a una funzione che prende n e r come parametro e determina , possiamo scrivere la relazione di cui sopra come:

nCr(n,r) = nCr(n-1,r) + nCr(n-1,r-1)

Questa è una relazione ricorsiva. Per terminarlo, dobbiamo determinare il caso (i) di base. Lo sappiamo, e . Usando questi due come casi base, il nostro algoritmo per determinare sarà:

Procedure nCr(n, r):
if r is equal to 1
    Return n
else if n is equal to r
    Return 1
end if
Return nCr(n-1,r) + nCr(n-1,r-1)

Se osserviamo graficamente la procedura, possiamo vedere che alcune ricorsioni vengono chiamate più di una volta. Ad esempio: se prendiamo n = 8 e r = 5 , otteniamo:

Possiamo evitare questa ripetuta chiamata usando un array, dp . Dato che ci sono 2 parametri, avremo bisogno di un array 2D. Inizializzeremo l'array dp con -1 , dove -1 indica che il valore non è stato ancora calcolato. La nostra procedura sarà:

Procedure nCr(n,r):
if r is equal to 1
    Return n
else if n is equal to r
    Return 1
else if dp[n][r] is not equal to -1        //The value has been calculated
    Return dp[n][r]
end if
dp[n][r] := nCr(n-1,r) + nCr(n-1,r-1)
Return dp[n][r]

Determinare , avevamo bisogno di due parametri n e r . Questi parametri sono chiamati stato . Possiamo semplicemente dedurre che il numero di stati determina il numero di dimensioni dell'array dp . La dimensione dell'array cambierà in base alle nostre necessità. I nostri algoritmi di programmazione dinamica manterranno il seguente schema generale:

Procedure DP-Function(state_1, state_2, ...., state_n)
Return if reached any base case
Check array and Return if the value is already calculated.
Calculate the value recursively for this state
Save the value in the table and Return

Determinare lo stato è una delle parti più cruciali della programmazione dinamica. Consiste nel numero di parametri che definiscono il nostro problema e nell'ottimizzazione del loro calcolo, possiamo ottimizzare l'intero problema.

Costruire una soluzione DP

Non importa quanti problemi risolvi usando la programmazione dinamica (DP), può comunque sorprendervi. Ma come ogni altra cosa nella vita, la pratica ti rende migliore. Tenendo presente ciò, considereremo il processo di costruzione di una soluzione per i problemi DP. Altri esempi su questo argomento ti aiuteranno a capire che cos'è DP e come funziona. In questo esempio, cercheremo di capire come creare una soluzione DP da zero.

Iterativo VS ricorsivo:
Esistono due tecniche per la costruzione della soluzione DP. Loro sono:

• Iterativo (usando i cicli)
• Ricorsivo (usando la ricorsione)

Ad esempio, l'algoritmo per calcolare la lunghezza della più lunga sequenza secondaria di due stringhe s1 e s2 dovrebbe avere il seguente aspetto:

Procedure LCSlength(s1, s2):
Table[0][0] = 0
for i from 1 to s1.length
    Table[0][i] = 0
endfor
for i from 1 to s2.length
    Table[i][0] = 0
endfor
for i from 1 to s2.length
    for j from 1 to s1.length
        if s2[i] equals to s1[j]
            Table[i][j] = Table[i-1][j-1] + 1
        else
            Table[i][j] = max(Table[i-1][j], Table[i][j-1])
        endif
    endfor
endfor
Return Table[s2.length][s1.length]

Questa è una soluzione iterativa. Ci sono alcuni motivi per cui è codificato in questo modo:

• L'iterazione è più veloce della ricorsione.
• Determinare la complessità di tempo e spazio è più semplice.
• Il codice sorgente è breve e pulito

Osservando il codice sorgente, puoi facilmente capire come e perché funziona, ma è difficile capire come arrivare a questa soluzione. Tuttavia i due approcci menzionati sopra si traducono in due diversi pseudo-codici. Uno usa l'iterazione (Bottom-Up) e un altro usa l'approccio ricorsivo (Top-Down). Quest'ultima è anche nota come tecnica di memoizzazione. Tuttavia, le due soluzioni sono più o meno equivalenti e una può essere facilmente trasformata in un'altra. Per questo esempio, mostreremo come trovare una soluzione ricorsiva per un problema.

Esempio di problema:
Diciamo che hai N ( 1, 2, 3, ...., N ) vini messi uno accanto all'altro su uno scaffale. Il prezzo della i-esima vino è p [i]. Il prezzo dei vini aumenta ogni anno. Supponiamo che sia anno 1, in anno y prezzo dell'i-esimo vino sarà: anno * prezzo del vino = y * p [i]. Vuoi vendere i vini che hai, ma devi vendere esattamente un vino all'anno, a partire da quest'anno. Ancora una volta, ogni anno, è consentito vendere solo il vino più a sinistra o più a destra e non è possibile riorganizzare i vini, il che significa che devono rimanere nello stesso ordine in cui sono all'inizio.

Ad esempio: supponiamo di avere 4 vini nello scaffale e i loro prezzi sono (da sinistra a destra):

+---+---+---+---+
| 1 | 4 | 2 | 3 |
+---+---+---+---+

La soluzione ottimale sarebbe quella di vendere i vini nell'ordine 1 -> 4 -> 3 -> 2 , che ci darà un profitto totale di:

Approccio avido:
Dopo un brainstorming per un po ', potresti trovare la soluzione per vendere il vino costoso il più tardi possibile. Quindi la tua strategia golosa sarà:

Every year, sell the cheaper of the two (leftmost and rightmost) available wines.

Anche se la strategia non menziona cosa fare quando i due vini costano lo stesso, la strategia sembra giusta. Ma sfortunatamente non lo è. Se i prezzi dei vini sono:

+---+---+---+---+---+
| 2 | 3 | 5 | 1 | 4 |
+---+---+---+---+---+

La strategia avida li venderebbe nell'ordine 1 -> 2 -> 5 -> 4 -> 3 per un profitto totale di:

Ma possiamo fare meglio se vendiamo i vini nell'ordine 1 -> 5 -> 4 -> 2 -> 3 per un profitto totale di:

Questo esempio dovrebbe convincerti che il problema non è così facile come sembra a prima vista. Ma può essere risolto utilizzando la programmazione dinamica.

backtracking:
Per trovare la soluzione di memoizzazione per un problema, trovare una soluzione di backtrack è a portata di mano. La soluzione Backtrack valuta tutte le risposte valide per il problema e sceglie quella migliore. Per la maggior parte dei problemi è più facile trovare una soluzione del genere. Ci possono essere tre strategie da seguire nell'affrontare una soluzione di backtrack:

1. dovrebbe essere una funzione che calcola la risposta usando la ricorsione.
2. dovrebbe restituire la risposta con la dichiarazione di ritorno .
3. tutte le variabili non locali devono essere utilizzate come di sola lettura, ovvero la funzione può modificare solo le variabili locali e i relativi argomenti.

Per il nostro esempio di esempio, proveremo a vendere il vino più a sinistra o più a destra e ricorsivamente calcolare la risposta e restituire il migliore. La soluzione di backtrack sarebbe simile a:

// year represents the current year
// [begin, end] represents the interval of the unsold wines on the shelf
Procedure profitDetermination(year, begin, end):
if begin > end                  //there are no more wines left on the shelf
    Return 0
Return max(profitDetermination(year+1, begin+1, end) + year * p[begin], //selling the leftmost item
           profitDetermination(year+1, begin, end+1) + year * p[end])   //selling the rightmost item

Se chiamiamo la procedura usando profitDetermination(1, 0, n-1) , dove n è il numero totale di vini, restituirà la risposta.

Questa soluzione cerca semplicemente tutte le possibili combinazioni valide di vendita dei vini. Se ci sono n vini all'inizio, controllerà possibilità. Anche se ora otteniamo la risposta corretta, la complessità temporale dell'algoritmo cresce esponenzialmente.

La funzione di backtrack scritta correttamente dovrebbe sempre rappresentare una risposta a una domanda ben formulata. Nel nostro esempio, la procedura profitDetermination rappresenta una risposta alla domanda: qual è il miglior profitto che possiamo ottenere dalla vendita dei vini con i prezzi memorizzati nell'array p, quando l'anno corrente è l'anno e l'intervallo dei vini invenduti si estende attraverso [inizio , fine], incluso? Dovresti sempre provare a creare una tale domanda per la tua funzione di backtrack per vedere se hai capito bene e capire esattamente cosa fa.

Stato determinante:
Stato è il numero di parametri utilizzati nella soluzione DP. In questo passaggio, dobbiamo pensare a quale degli argomenti che passi alla funzione sono ridondanti, cioè possiamo costruirli dagli altri argomenti o non ne abbiamo affatto bisogno. Se ci sono tali argomenti, non abbiamo bisogno di passarli alla funzione, li calcoleremo all'interno della funzione.

Nell'esempio function profitDetermination mostrato sopra, l'argomento year è ridondante. È equivalente al numero di vini che abbiamo già venduto più uno. Può essere determinato utilizzando il numero totale di vini dall'inizio meno il numero di vini che non abbiamo venduto più uno. Se memorizziamo il numero totale di vini n come variabile globale, possiamo riscrivere la funzione come:

Procedure profitDetermination(begin, end):
if begin > end
    Return 0
year := n - (end-begin+1) + 1        //as described above
Return max(profitDetermination(begin+1, end) + year * p[begin],
           profitDetermination(begin, end+1) + year * p[end])

Dobbiamo anche pensare alla gamma di valori possibili dei parametri che possono ottenere da un input valido. Nel nostro esempio, ciascuno dei parametri begin e end può contenere valori da 0 a n-1 . In un input valido, ci aspettiamo anche che begin <= end + 1 . Possono esserci O(n²) diversi argomenti con cui la nostra funzione può essere chiamata.

Memoizzazione:
Ora abbiamo quasi finito. Trasformare la soluzione di backtrack con la complessità del tempo in soluzione di memoizzazione con complessità temporale , useremo un piccolo trucco che non richiede molto sforzo.

Come notato sopra, ci sono solo diversi parametri con cui la nostra funzione può essere chiamata. In altre parole, ci sono solo cose diverse che possiamo effettivamente calcolare. Allora, dove lo fa la complessità del tempo viene e cosa calcola !!

La risposta è: la complessità temporale esponenziale deriva dalla ricorsione ripetuta e, per questo motivo, calcola sempre gli stessi valori. Se si esegue il codice menzionato sopra per un array arbitrario di n = 20 vini e si calcola quante volte è stata richiamata la funzione per argomenti begin = 10 e end = 10 , si otterrà il numero 92378 . Questo è un enorme spreco di tempo per calcolare la stessa risposta molte volte. Quello che potremmo fare per migliorare questo è memorizzare i valori dopo averli calcolati e ogni volta che la funzione richiede un valore già calcolato, non è necessario eseguire di nuovo l'intera ricorsione. Avremo un array dp [N] [N] , inizializzarlo con -1 (o qualsiasi valore che non verrà nel nostro calcolo), dove -1 indica che il valore non è stato ancora calcolato. La dimensione dell'array è determinata dal valore massimo possibile di inizio e fine, poiché memorizzeremo i valori corrispondenti di determinati valori iniziali e finali nel nostro array. La nostra procedura sarebbe simile a:

Procedure profitDetermination(begin, end):
if begin > end
    Return 0
if dp[begin][end] is not equal to -1                //Already calculated
    Return dp[begin][end]
year := n - (end-begin+1) + 1
dp[begin][end] := max(profitDetermination(year+1, begin+1, end) + year * p[begin],
           profitDetermination(year+1, begin, end+1) + year * p[end])
Return dp[begin][end]

Questa è la nostra soluzione DP richiesta. Con il nostro trucco molto semplice, la soluzione funziona tempo, perché ci sono diversi parametri con cui la funzione può essere chiamata con e per ognuno di essi, la funzione viene eseguita una sola volta con complessità.

Summery:
Se è possibile identificare un problema che può essere risolto utilizzando DP, attenersi alla seguente procedura per costruire una soluzione DP:

• Crea una funzione di backtrack per fornire la risposta corretta.
• Rimuovere gli argomenti ridondanti.
• Stimare e minimizzare la gamma massima di valori possibili dei parametri di funzione.
• Cerca di ottimizzare la complessità temporale di una chiamata di funzione.
• Memorizza i valori in modo che non sia necessario calcolarlo due volte.

La complessità di una soluzione DP è: gamma di valori possibili la funzione può essere chiamata con * la complessità temporale di ogni chiamata .