Fibonacci e programmazione dinamica

Chiedi a un computer il 40° numero di Fibonacci nel modo più ovvio e farà più di 331 milioni di chiamate. Chiediglielo con una tabella e gli bastano 39 addizioni. La differenza è la programmazione dinamica, e quasi tutti la incontrano per la prima volta proprio con i numeri di Fibonacci.

Una riga di celle di tabella con numeri di Fibonacci, con la cella che si sta riempiendo in arancione e le due celle che somma in blu
Una riga di celle di tabella con numeri di Fibonacci, con la cella che si sta riempiendo in arancione e le due celle che somma in blu

Il problema

I numeri di Fibonacci iniziano con 0, 1, e ogni numero successivo è la somma dei due precedenti: 0, 1, 1, 2, 3, 5, 8, 13, 21 e così via. Scritta come regola: F(0) = 0, F(1) = 1 e F(n) = F(n − 1) + F(n − 2). La regola è ricorsiva, e trasformarla direttamente in un programma ricorsivo è facile, ma quel programma si rivela molto lento.

Perché la ricorsione si ripete

Per trovare F(5), il programma chiede F(4) e F(3). F(4) chiede F(3) e F(2), quindi F(3) viene calcolato due volte, F(2) tre volte e F(1) cinque volte. Disegnate come un albero, le chiamate quasi raddoppiano a ogni livello, e il totale per F(n) è di 2·F(n + 1) − 1 chiamate. I problemi più piccoli si sovrappongono: gli stessi ritornano più e più volte. È il segnale che la programmazione dinamica può aiutare.

Due modi di ricordare

La memoizzazione mantiene la ricorsione ma scrive ogni risposta in una tabella, e ogni chiamata guarda nella tabella prima di fare qualsiasi calcolo. La tabulazione riempie la tabella dal basso verso l'alto: prima F(0) e F(1), poi F(2) da questi, F(3) da F(2) e F(1), e così via fino a F(n). In entrambi i casi ogni termine viene calcolato una volta, quindi F(n) costa n − 1 addizioni invece di un numero esponenziale di chiamate.

Un esempio

Bottom-up per F(7): si parte da 0 e 1. Poi 0 + 1 = 1, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8 e 5 + 8 = 13, quindi F(7) = 13 dopo sei addizioni. La ricorsione semplice farebbe 2·F(8) − 1 = 41 chiamate per la stessa risposta. Con il top-down, le prime chiamate scendono fino a F(1) lungo il bordo sinistro dell'albero; risalendo, quasi una chiamata su due trova la risposta già nella tabella.

Da dove viene il nome

Richard Bellman diede il nome alla programmazione dinamica all'inizio degli anni Cinquanta, mentre lavorava alla RAND Corporation. In seguito scrisse di aver scelto «programmazione» nel vecchio senso di pianificazione, e «dinamica» perché suonava d'effetto ed era difficile da contestare. Il metodo in sé, risolvere un problema attraverso le risposte a sue versioni più piccole, oggi lavora nei correttori ortografici, nei navigatori e nel confronto del DNA.

Richard Bellman nel 1962, fotografato da Alfred Eisenstaedt. Diede il nome alla programmazione dinamica all’inizio degli anni Cinquanta, mentre lavorava alla RAND Corporation.
Richard Bellman nel 1962, fotografato da Alfred Eisenstaedt. Diede il nome alla programmazione dinamica all’inizio degli anni Cinquanta, mentre lavorava alla RAND Corporation.

Esploralo

Apri l'app e premi Passo. Con Bottom-up, la cella arancione è quella che si sta riempiendo e le due celle blu sono i termini che somma. Passa a Top-down e guarda la pila delle chiamate sotto la tabella crescere fino a n, poi ridursi man mano che tornano le risposte; il suggerimento sotto Addizioni conta quante chiamate hanno trovato la risposta direttamente nella tabella.

Domande frequenti

Che cosa sono i sottoproblemi sovrapposti?

Problemi più piccoli di cui una soluzione ha bisogno più di una volta. F(n) e F(n − 1) hanno entrambi bisogno di F(n − 2), quindi la ricorsione semplice lo calcola due volte, e lo spreco si moltiplica più in basso. La programmazione dinamica risolve ciascuno una sola volta e ne ricorda la risposta.

La memoizzazione è più veloce della tabulazione?

Fanno le stesse addizioni. La tabulazione di solito è un po' più veloce perché non fa chiamate, e non può esaurire lo spazio sullo stack; la memoizzazione è comoda quando servono solo alcune delle risposte più piccole, perché calcola solo quelle.

Si possono calcolare i numeri di Fibonacci ancora più velocemente?

Sì. Usando F(2k) = F(k)·(2·F(k + 1) − F(k)) e F(2k + 1) = F(k)² + F(k + 1)², il metodo del raddoppio veloce richiede solo circa log₂ n passi. La formula di Binet con la sezione aurea dà gli stessi numeri, ma gli errori di arrotondamento la rendono inaffidabile per n grandi.

Quanta memoria richiede la tabella?

Una tabella completa contiene n + 1 numeri, ma ogni nuovo termine ha bisogno solo dei due precedenti, quindi un ciclo che tiene due numeri fa lo stesso lavoro con memoria costante. Tenere l'intera tabella è utile quando vuoi tutti i termini, o per vedere come funziona il metodo.

Pronto a provarlo?

Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.

Prova Fibonacci con la programmazione dinamica