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, …\)

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.