Fibonacci și programarea dinamică
Cereți unui calculator al 40-lea număr Fibonacci în modul cel mai evident și va face peste 331 de milioane de apeluri. Cereți-i-l cu un tabel și îi vor fi suficiente 39 de adunări. Diferența este programarea dinamică, iar aproape toată lumea o întâlnește prima dată la numerele Fibonacci.
Problema
Numerele Fibonacci încep cu 0, 1, iar fiecare număr următor este suma celor două dinaintea lui: 0, 1, 1, 2, 3, 5, 8, 13, 21 și așa mai departe. Scrisă ca regulă: F(0) = 0, F(1) = 1 și F(n) = F(n − 1) + F(n − 2). Regula este recursivă și este ușor să o transformați direct într-un program recursiv, dar acest program se dovedește foarte lent.
De ce se repetă recursivitatea
Pentru a afla F(5), programul cere F(4) și F(3). F(4) cere F(3) și F(2), deci F(3) este calculat de două ori, F(2) de trei ori și F(1) de cinci ori. Desenate ca un arbore, apelurile aproape se dublează la fiecare nivel, iar totalul pentru F(n) este de 2·F(n + 1) − 1 apeluri. Problemele mai mici se suprapun: aceleași revin iar și iar. Acesta este semnul că programarea dinamică va ajuta.
Două moduri de a reține
Memoizarea păstrează recursivitatea, dar scrie fiecare răspuns într-un tabel, iar fiecare apel se uită în tabel înainte de a face vreun calcul. Tabelarea completează tabelul de jos în sus: întâi F(0) și F(1), apoi F(2) din ele, F(3) din F(2) și F(1) și așa mai departe până la F(n). În ambele cazuri fiecare termen este calculat o dată, deci F(n) costă n − 1 adunări în loc de un număr exponențial de apeluri.
Un exemplu
Metoda ascendentă pentru F(7): se pornește de la 0 și 1. Apoi 0 + 1 = 1, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8 și 5 + 8 = 13, deci F(7) = 13 după șase adunări. Recursivitatea simplă ar face 2·F(8) − 1 = 41 de apeluri pentru același răspuns. Cu metoda descendentă, primele apeluri coboară până la F(1) de-a lungul marginii din stânga a arborelui; la întoarcere, aproape fiecare al doilea apel își găsește răspunsul deja în tabel.
De unde vine numele
Richard Bellman a dat numele programării dinamice la începutul anilor 1950, pe când lucra la RAND Corporation. Mai târziu a scris că a ales „programare” în vechiul sens de planificare, iar „dinamică” pentru că suna impresionant și era greu de contestat. Metoda în sine, rezolvarea unei probleme prin răspunsurile la versiuni mai mici ale ei, funcționează azi în corectoarele ortografice, în planificatoarele de rute și în compararea ADN-ului.
Explorați
Deschideți aplicația și apăsați Pas. La metoda Ascendentă, celula portocalie este cea care se completează, iar cele două celule albastre sunt termenii pe care îi adună. Treceți la Descendentă și urmăriți cum stiva de apeluri de sub tabel crește până la n, apoi scade pe măsură ce răspunsurile se întorc; indicația de sub Adunări numără câte apeluri au primit răspunsul direct din tabel.
Întrebări frecvente
Ce sunt subproblemele suprapuse?
Probleme mai mici de care o soluție are nevoie de mai multe ori. F(n) și F(n − 1) au nevoie amândouă de F(n − 2), așa că recursivitatea simplă îl calculează de două ori, iar risipa se înmulțește mai jos. Programarea dinamică rezolvă fiecare dintre ele o singură dată și reține răspunsul.
Este memoizarea mai rapidă decât tabelarea?
Fac aceleași adunări. Tabelarea este de obicei puțin mai rapidă pentru că nu face apeluri și nu poate rămâne fără spațiu pe stivă; memoizarea este utilă când sunt necesare doar unele dintre răspunsurile mai mici, pentru că le calculează doar pe acelea.
Pot fi calculate numerele Fibonacci și mai repede?
Da. Folosind F(2k) = F(k)·(2·F(k + 1) − F(k)) și F(2k + 1) = F(k)² + F(k + 1)², metoda dublării rapide are nevoie doar de aproximativ log₂ n pași. Formula lui Binet cu secțiunea de aur dă aceleași numere, dar erorile de rotunjire o fac nesigură pentru n mare.
Câtă memorie necesită tabelul?
Un tabel complet conține n + 1 numere, dar fiecare termen nou are nevoie doar de cei doi dinaintea lui, așa că o buclă care păstrează două numere face aceeași treabă cu memorie constantă. Păstrarea întregului tabel este utilă când doriți toți termenii sau ca să vedeți cum funcționează metoda.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Încercați Fibonacci cu programare dinamică