Fibonacci og dynamisk programmering
Beder du en computer om det 40. Fibonacci-tal på den oplagte måde, laver den mere end 331 millioner kald. Beder du om det med en tabel, skal den kun bruge 39 additioner. Forskellen er dynamisk programmering, og det er med Fibonacci-tallene, næsten alle møder det første gang.
Problemet
Fibonacci-tallene starter med 0, 1, og hvert senere tal er summen af de to før det: 0, 1, 1, 2, 3, 5, 8, 13, 21 og så videre. Skrevet som en regel: F(0) = 0, F(1) = 1 og F(n) = F(n − 1) + F(n − 2). Reglen er rekursiv, og det er let at omsætte den direkte til et rekursivt program, men det program viser sig at være meget langsomt.
Hvorfor rekursion gentager sig selv
For at finde F(5) spørger programmet efter F(4) og F(3). F(4) spørger efter F(3) og F(2), så F(3) beregnes to gange, F(2) tre gange og F(1) fem gange. Tegnet som et træ bliver kaldene næsten fordoblet på hvert niveau, og i alt laver F(n) 2·F(n + 1) − 1 kald. De mindre problemer overlapper: de samme kommer igen og igen. Det er tegnet på, at dynamisk programmering vil hjælpe.
To måder at huske på
Memoisering beholder rekursionen, men skriver hvert svar i en tabel, og hvert kald kigger i tabellen, før det gør noget arbejde. Tabulering fylder tabellen bottom-up: først F(0) og F(1), så F(2) ud fra dem, F(3) ud fra F(2) og F(1) og så videre op til F(n). Uanset hvad beregnes hvert led én gang, så F(n) koster n − 1 additioner i stedet for et eksponentielt antal kald.
Et eksempel
Bottom-up for F(7): start med 0 og 1. Så 0 + 1 = 1, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8 og 5 + 8 = 13, så F(7) = 13 efter seks additioner. Almindelig rekursion ville lave 2·F(8) − 1 = 41 kald for det samme svar. Ved top-down går de første kald hele vejen ned til F(1) langs træets venstre kant; på vej op igen finder næsten hvert andet kald sit svar allerede i tabellen.
Hvor navnet kommer fra
Richard Bellman gav dynamisk programmering sit navn i begyndelsen af 1950'erne, mens han arbejdede hos RAND Corporation. Han skrev senere, at han valgte »programmering« i den gamle betydning planlægning, og »dynamisk«, fordi det lød imponerende og var svært at indvende noget imod. Selve metoden, at løse et problem via svarene på mindre udgaver af det, kører i dag i stavekontroller, ruteplanlæggere og sammenligning af DNA.
Udforsk det
Åbn appen og tryk på Trin. Ved Bottom-up er den orange celle den, der bliver fyldt, og de to blå celler er de led, den lægger sammen. Skift til Top-down, og se stakken af kald under tabellen vokse til n og så skrumpe, efterhånden som svarene kommer tilbage; teksten under Additioner tæller, hvor mange kald der blev besvaret direkte fra tabellen.
Ofte stillede spørgsmål
Hvad er overlappende delproblemer?
Mindre problemer, som en løsning har brug for mere end én gang. F(n) og F(n − 1) har begge brug for F(n − 2), så almindelig rekursion beregner det to gange, og spildet ganges op længere nede. Dynamisk programmering løser hvert af dem én gang og husker svaret.
Er memoisering hurtigere end tabulering?
De laver de samme additioner. Tabulering er som regel lidt hurtigere, fordi den ikke laver kald, og den kan ikke løbe tør for plads på stakken; memoisering er praktisk, når kun nogle af de mindre svar er nødvendige, fordi den kun beregner dem.
Kan Fibonacci-tal beregnes endnu hurtigere?
Ja. Med F(2k) = F(k)·(2·F(k + 1) − F(k)) og F(2k + 1) = F(k)² + F(k + 1)² kræver metoden med hurtig fordobling (fast doubling) kun omkring log₂ n trin. Binets formel med det gyldne snit giver de samme tal, men afrundingsfejl gør den upålidelig for store n.
Hvor meget hukommelse kræver tabellen?
En fuld tabel rummer n + 1 tal, men hvert nyt led kræver kun de to før det, så en løkke, der gemmer to tal, gør det samme arbejde med konstant hukommelse. Det er nyttigt at beholde hele tabellen, når du vil have alle leddene, eller for at se, hvordan metoden virker.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Prøv Fibonacci med dynamisk programmering