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.
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.
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