Fibonacci och dynamisk programmering

Be en dator om det 40:e Fibonaccitalet på det självklara sättet, så gör den mer än 331 miljoner anrop. Be om det med en tabell, så behöver den 39 additioner. Skillnaden är dynamisk programmering, och det är genom Fibonaccitalen som nästan alla möter den för första gången.

En rad tabellceller med Fibonaccital, där cellen som fylls är orange och de två cellerna den adderar är blå
En rad tabellceller med Fibonaccital, där cellen som fylls är orange och de två cellerna den adderar är blå

Problemet

Fibonaccitalen börjar med 0, 1, och varje senare tal är summan av de två före det: 0, 1, 1, 2, 3, 5, 8, 13, 21 och så vidare. Skrivet som en regel: F(0) = 0, F(1) = 1 och F(n) = F(n − 1) + F(n − 2). Regeln är rekursiv, och att göra om den rakt av till ett rekursivt program är lätt, men det programmet visar sig vara mycket långsamt.

Varför rekursionen upprepar sig

För att hitta F(5) frågar programmet efter F(4) och F(3). F(4) frågar efter F(3) och F(2), så F(3) räknas ut två gånger, F(2) tre gånger och F(1) fem gånger. Ritade som ett träd nästan fördubblas anropen på varje nivå, och totalt gör F(n) 2·F(n + 1) − 1 anrop. De mindre problemen överlappar: samma problem kommer tillbaka om och om igen. Det är tecknet på att dynamisk programmering kommer att hjälpa.

Två sätt att komma ihåg

Memoisering behåller rekursionen men skriver varje svar i en tabell, och varje anrop tittar i tabellen innan det gör något arbete. Tabulering fyller tabellen nedifrån och upp: först F(0) och F(1), sedan F(2) ur dem, F(3) ur F(2) och F(1) och så vidare upp till F(n). Hur som helst räknas varje term ut en gång, så F(n) kostar n − 1 additioner i stället för ett exponentiellt antal anrop.

Ett exempel

Bottom-up för F(7): börja med 0 och 1. Sedan 0 + 1 = 1, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8 och 5 + 8 = 13, så F(7) = 13 efter sex additioner. Vanlig rekursion skulle göra 2·F(8) − 1 = 41 anrop för samma svar. Med top-down går de första anropen hela vägen ner till F(1) längs trädets vänstra kant; på vägen upp igen hittar nästan vartannat anrop sitt svar redan i tabellen.

Var namnet kommer ifrån

Richard Bellman gav dynamisk programmering dess namn i början av 1950-talet, när han arbetade på RAND Corporation. Han skrev senare att han valde ”programmering” i den gamla betydelsen planering, och ”dynamisk” för att det lät imponerande och var svårt att invända mot. Själva metoden, att lösa ett problem via svaren på mindre versioner av det, används i dag i stavningskontroller, ruttplanerare och jämförelser av DNA.

Richard Bellman 1962, fotograferad av Alfred Eisenstaedt. Han gav dynamisk programmering dess namn i början av 1950-talet, när han arbetade på RAND Corporation.
Richard Bellman 1962, fotograferad av Alfred Eisenstaedt. Han gav dynamisk programmering dess namn i början av 1950-talet, när han arbetade på RAND Corporation.

Utforska själv

Öppna appen och tryck på Steg. Med Bottom-up är den orange cellen den som fylls, och de två blå cellerna är termerna den adderar. Byt till Top-down och se stacken av anrop under tabellen växa till n och sedan krympa när svaren kommer tillbaka; texten under Additioner räknar hur många anrop som besvarades direkt ur tabellen.

Ofta ställda frågor

Vad är överlappande delproblem?

Mindre problem som en lösning behöver mer än en gång. F(n) och F(n − 1) behöver båda F(n − 2), så vanlig rekursion räknar ut det två gånger, och slöseriet mångdubblas längre ner. Dynamisk programmering löser vart och ett en gång och kommer ihåg svaret.

Är memoisering snabbare än tabulering?

De gör samma additioner. Tabulering är oftast lite snabbare eftersom den inte gör några anrop, och den kan inte få slut på stackutrymme; memoisering är praktisk när bara en del av de mindre svaren behövs, eftersom den bara räknar ut dem.

Kan Fibonaccital räknas ut ännu snabbare?

Ja. Med F(2k) = F(k)·(2·F(k + 1) − F(k)) och F(2k + 1) = F(k)² + F(k + 1)² behöver metoden med snabb fördubbling (fast doubling) bara ungefär log₂ n steg. Binets formel med gyllene snittet ger samma tal, men avrundningsfel gör den opålitlig för stora n.

Hur mycket minne behöver tabellen?

En full tabell rymmer n + 1 tal, men varje ny term behöver bara de två före den, så en loop som sparar två tal gör samma jobb med konstant minne. Att behålla hela tabellen är användbart när du vill ha alla termer, eller för att se hur metoden fungerar.

Redo att prova det?

Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.

Prova Fibonacci med dynamisk programmering