Fibonacci en dynamisch programmeren
Vraag een computer op de voor de hand liggende manier om het 40e Fibonacci-getal en hij doet meer dan 331 miljoen aanroepen. Vraag het met een tabel en hij heeft 39 optellingen nodig. Het verschil is dynamisch programmeren, en bijna iedereen maakt er voor het eerst kennis mee via de Fibonacci-getallen.
Het probleem
De Fibonacci-getallen beginnen met 0, 1, en elk volgend getal is de som van de twee ervoor: 0, 1, 1, 2, 3, 5, 8, 13, 21 enzovoort. Als regel geschreven: F(0) = 0, F(1) = 1 en F(n) = F(n − 1) + F(n − 2). De regel is recursief, en hem rechtstreeks omzetten in een recursief programma is makkelijk, maar dat programma blijkt erg traag.
Waarom recursie zichzelf herhaalt
Om F(5) te vinden, vraagt het programma F(4) en F(3) op. F(4) vraagt F(3) en F(2) op, dus F(3) wordt twee keer berekend, F(2) drie keer en F(1) vijf keer. Als boom getekend verdubbelen de aanroepen bijna op elk niveau, en in totaal doet F(n) 2·F(n + 1) − 1 aanroepen. De kleinere problemen overlappen: dezelfde komen steeds weer terug. Dat is het teken dat dynamisch programmeren gaat helpen.
Twee manieren om te onthouden
Memoïsatie houdt de recursie, maar schrijft elk antwoord in een tabel, en elke aanroep kijkt in de tabel voordat hij iets berekent. Tabulatie vult de tabel bottom-up: eerst F(0) en F(1), dan F(2) daaruit, F(3) uit F(2) en F(1), en zo verder tot F(n). Hoe dan ook wordt elke term één keer berekend, dus F(n) kost n − 1 optellingen in plaats van een exponentieel aantal aanroepen.
Een voorbeeld
Bottom-up voor F(7): begin met 0 en 1. Dan 0 + 1 = 1, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8 en 5 + 8 = 13, dus F(7) = 13 na zes optellingen. Gewone recursie zou voor hetzelfde antwoord 2·F(8) − 1 = 41 aanroepen doen. Bij top-down gaan de eerste aanroepen langs de linkerrand van de boom helemaal omlaag naar F(1); op de weg terug omhoog vindt bijna elke tweede aanroep zijn antwoord al in de tabel.
Waar de naam vandaan komt
Richard Bellman gaf dynamisch programmeren begin jaren 1950 zijn naam, toen hij bij de RAND Corporation werkte. Later schreef hij dat hij ‘programmeren’ koos in de oude betekenis van plannen, en ‘dynamisch’ omdat het indrukwekkend klonk en je er moeilijk bezwaar tegen kon maken. De methode zelf, een probleem oplossen via de antwoorden op kleinere versies ervan, zit nu in spellingcontroles, routeplanners en het vergelijken van DNA.
Zelf ontdekken
Open de app en druk op Stap. Bij Bottom-up is de oranje cel de cel die gevuld wordt, en de twee blauwe cellen zijn de termen die hij optelt. Schakel over naar Top-down en zie de stapel aanroepen onder de tabel groeien tot n en weer krimpen als de antwoorden terugkomen; de hint onder Optellingen telt hoeveel aanroepen direct uit de tabel beantwoord zijn.
Veelgestelde vragen
Wat zijn overlappende deelproblemen?
Kleinere problemen die een oplossing meer dan eens nodig heeft. F(n) en F(n − 1) hebben allebei F(n − 2) nodig, dus gewone recursie berekent die twee keer, en verderop vermenigvuldigt de verspilling zich. Dynamisch programmeren lost elk ervan één keer op en onthoudt het antwoord.
Is memoïsatie sneller dan tabulatie?
Ze doen dezelfde optellingen. Tabulatie is meestal iets sneller omdat het geen aanroepen doet, en het kan niet zonder stackruimte komen te zitten; memoïsatie is handig als maar een deel van de kleinere antwoorden nodig is, omdat het alleen die berekent.
Kunnen Fibonacci-getallen nog sneller berekend worden?
Ja. Met F(2k) = F(k)·(2·F(k + 1) − F(k)) en F(2k + 1) = F(k)² + F(k + 1)² heeft de methode van snelle verdubbeling (fast doubling) maar ongeveer log₂ n stappen nodig. De formule van Binet met de gulden snede geeft dezelfde getallen, maar door afrondingsfouten is die voor grote n onbetrouwbaar.
Hoeveel geheugen heeft de tabel nodig?
Een volledige tabel bevat n + 1 getallen, maar elke nieuwe term heeft alleen de twee ervoor nodig, dus een lus die twee getallen bewaart doet hetzelfde werk met constant geheugen. De hele tabel bewaren is handig als je alle termen wilt hebben, of om te zien hoe de methode werkt.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Probeer Fibonacci met dynamisch programmeren