Programmazione dinamica e i numeri di Fibonacci¶
A cura di Mohamad Ali Mohamad Almgerbi, basato sulle lezioni di Cecilia Verri
Le soluzioni di molti problemi possono essere descritte in forma ricorsiva. In questo caso, il problema originale è suddiviso in alcuni sotto-problemi e viene risolto ripetutamente e quindi combinato in una soluzione finale. Tuttavia, se la descrizione del problema contiene sotto-problemi identici, tale implementazione è inefficace in quanto gli stessi sotto-problemi vengono risolti indipendentemente l’uno dall’altro più e più volte. Questo tipo di ricalcolo non necessario può spesso essere evitato usando tecniche di programmazione dinamica.
La programmazione dinamica (DP) è una tecnica per risolvere i problemi in modo più efficiente. La programmazione dinamica è efficace nel trovare soluzioni ottimali per casi con molti sotto-problemi sovrapposti. Nella programmazione dinamica memorizziamo la soluzione di questi sotto-problemi in modo da non doverli risolvere di nuovo, questo si chiama memoization. Onde evitare di ricalcolare più volte la soluzione di uno stesso sotto-problema, i sotto-problemi vengono risolti con una strategia bottom-up (vale a dire: dal sotto-problema più “piccolo” al sotto-problema più “grande”) e le soluzioni a questi sotto-problemi vengono memorizzate in apposite tabelle di modo che siano disponibili, se necessario, alla soluzione di altri sotto-problemi.
Di seguito mostreremo il calcolo dei numeri di Fibonacci mediante programmazione dinamica, risolvendo il problema con la proprietà dei sotto-problemi sovrapposti.
La sequenza di Fibonacci¶
La sequenza di Fibonacci è una sequenza infinita di numeri interi positivi, a partire da 0 e 1, dove ogni elemento successivo è uguale alla somma dei suoi due elementi precedenti. Se indichiamo il numero alla posizione n come Fib(n), possiamo definire formalmente la sequenza di Fibonacci come:
\(Fib(n) = 0\) if \(n = 0\)
\(Fib(n) = 1\) if \(n = 1\)
\(Fib(n) = Fib(n-1) + Fib(n-2)\) if \(n > 1\)
Pertanto, l’inizio della sequenza è: \(0, 1, 1, 2, 3, 5, 8, 13, …\)
| Valore | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 |
|---|---|---|---|---|---|---|---|---|
| Indice | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
def Fib(n):
# il primo numero di Fibonacci
if n==0:
return 0
# il secondo numero di Fibonacci
elif n==1:
return 1
else:
return Fib(n-1)+Fib(n-2)
n=5
print(Fib(n))
Nel codice sopra abbiamo definito una funzione chiamata Fib, che ha preso \(n\) come input e ha restituito il numero \(n\)-esimo nella sequenza di Fibonacci.
All’interno di questa funzione, per prima cosa controlliamo se l’input è uguale a 0 e restituiamo 0 in questo caso. Controlliamo anche se l’input è uguale a 1 e restituiamo 1 in questo caso. Altrimenti, ovvero se l’input è diverso da 0 e diverso da 1, usiamo la funzione ricorsiva, richiamando la funzione stessa. La funzione chiamata farà altrettanto fin quando l’input diventerà uguale a 1 o 0. Se supponiamo di voler calcolare Fib(5), dal momento che 5 è diverso da 0 e 1, abbiamo Fib (5) = Fib (4) + Fib (3). Le chiamate a Fib (4) e Fib (3), dal momento che 4 e 3 sono diversi da 0 e 1, useranno ancora la regola ricorsiva. Il processo andrà avanti fino a quando non troveremo i casi base. Dunque:
- \(Fib (5) = Fib (4) + Fib (3)\)
Dove ciascuna delle due chiamate, internamente, procede come segue:
- \(Fib (4) = Fib (3) + Fib (2)\)
- \(Fib (3) = Fib (2) + Fib (1)\)
per cui,
- \(Fib (5) = (Fib (3) + Fib (2)) + (Fib (2) + Fib (1))\)
Applicando ancora la ricorsione, usando:
- \(Fib (3) = Fib (2) + Fib (1)\)
- \(Fib (2) = Fib (1) + Fib (0)\)
si ottiene,
- \(Fib (5) = (Fib (2) + Fib (1)) + (Fib (1) + Fib (0)) + (Fib (1) + Fib (0) + Fib (1))\)
La regola ricorsiva viene di nuovo applicata per Fib (2). Viene invece applicato il caso base per Fib (1) e Fib (0), perché il valore di \(n\) è in questo caso uguale a 1 e 0:
- \(Fib (5) = ((Fib (1) + Fib (0)) + Fib (1)) + (Fib (1) + Fib (0)) + (Fib (1) + Fib (0) + Fib (1)) = 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1 = 5\)
La complessità temporale di Fibonacci¶
Vogliamo analizzare quanto è veloce l’algoritmo. Come si vede dall’esempio sopra, Fib (3) viene ripetuto 2 volte, Fib (2) viene ripetuto 3 volte, Fib(1) viene ripetuto 5 volte e Fib (0) viene ripetuto 3 volte. A causa di molte chiamate identiche ripetute, l’algoritmo risulta inefficiente. Come mostrato sotto il numero di chiamate ricorsive è il seguente ad ogni livello.
\(2^0=1\) chiamata: Fib(n)
\(2^1=2\) chiamate: Fib(n-1), Fib(n-2)
\(2^2=4\) chiamate: Fib(n-2), Fib(n-3), Fib(n-3), Fib(n-4)
\(2^3=8\) chiamate: Fib(n-3), Fib(n-4), Fib(n-4), Fib(n-5), Fib(n-4), Fib(n-5), Fib(n-5), Fib(n-6)
\(...\)
\(2^n-1\) chiamate
Usando \(T(n)\) per indicare la complessità temporale di Fib(n) otteniamo \(T(n) = T(n - 1) + T(n -2) + 1 \leq O(2^n)\). Questo algoritmo è esponenziale, ovvero non riusciamo a vedere la sua fine per esempio passando \(n=64\) (https://en.wikipedia.org/wiki/Wheat_and_chessboard_problem). Ci sono molte altre soluzioni alternative per trovare l’n-esimo numero di Fibonacci, una delle quali applica la Programmazione Dinamica. L’idea di questo approccio è evitare il lavoro ripetuto, memorizzando il risultato dei sotto-problemi, per evitare di calcolarlo ancora.
La programmazione dinamica - Fibonacci¶
Per trovare il numero n-esimo di Fibonacci, applichiamo la programmazione dinamica, mediante due possibili approcci.
4.1. Top-down con Memoization¶
In questo approccio, cerchiamo di risolvere il problema più grande trovando ricorsivamente la soluzione a piccoli problemi secondari. Ogni volta che risolviamo un sotto-problema, memorizziamo nella cache il suo risultato in modo da non risolverlo ripetutamente se viene chiamato più volte e restituire semplicemente il risultato salvato in precedenza. Questa tecnica di memorizzazione dei risultati di sottoproblemi già risolti si chiama Memoization.
Esempio:
def calculateFibonacci(n):
memoize = [-1 for x in range(n+1)]
return calculateFibonacciRecur(memoize, n)
def calculateFibonacciRecur(memoize, n):
if n < 2:
return n
if memoize[n] >= 0:
return memoize[n]
memoize[n] = calculateFibonacciRecur(memoize, n - 1) + calculateFibonacciRecur(memoize, n - 2)
return memoize[n]
print(calculateFibonacci(5))
L’output è 5
4.2. Bottom-up con tabulazione¶
La tabulazione è l’opposto dell’approccio top-down. In questo approccio, risolviamo il problema “dal basso verso l’alto” (ovvero risolvendo prima tutti i sotto-problemi correlati). Questo viene generalmente eseguito compilando una tabella n-dimensionale. Sulla base dei risultati nella tabella, viene quindi calcolata la soluzione al problema principale/originale.
Esempio:
def calculateFibonacci(n):
dp = [0, 1]
for i in range(2, n + 1):
dp.append(dp[i - 1] + dp[i - 2])
return dp[n]
print(calculateFibonacci(5))
L’output è 5
Conclusione¶
Un esempio tipico di algoritmo ricorsivo è l’algoritmo per trovare il numero n-esimo di Fibonacci. La risoluzione del problema in modo ricorsivo è abbastanza naturale in quanto sfrutta la definizione della serie stessa. Tuttavia, un’applicazione diretta della definizione implica la risoluzione di uno stesso sotto-problema molte volte. Questa inefficienza porta ad avere una complessità esponenziale. La programmazione dinamica permette di evitare questo problema: suddivide il problema in problemi più piccoli e memorizza i valori dei sotto-problemi per un uso successivo. Per determinare se un problema può essere risolto con la programmazione dinamica, dovremmo capire se questo problema può essere risolto in modo ricorsivo e il risultato dei sotto-problemi può aiutarci a risolvere il problema originale. Abbiamo visto due tecniche di applicazione della programmazione dinamica, quali Bottom-up e Top-down, le quali entrambe usano tempo O(n), lineare anziché esponenziale.