Fibonacci und dynamische Programmierung

Fragen Sie einen Computer auf dem naheliegenden Weg nach der 40. Fibonacci-Zahl, und er macht mehr als 331 Millionen Aufrufe. Fragen Sie ihn mit einer Tabelle, und er braucht 39 Additionen. Der Unterschied heißt dynamische Programmierung, und bei den Fibonacci-Zahlen begegnet sie fast jedem zum ersten Mal.

Eine Reihe von Tabellenzellen mit Fibonacci-Zahlen; die Zelle, die gerade gefüllt wird, ist orange, die beiden Zellen, die sie addiert, sind blau
Eine Reihe von Tabellenzellen mit Fibonacci-Zahlen; die Zelle, die gerade gefüllt wird, ist orange, die beiden Zellen, die sie addiert, sind blau

Das Problem

Die Fibonacci-Zahlen beginnen mit 0, 1, und jede weitere Zahl ist die Summe der beiden davor: 0, 1, 1, 2, 3, 5, 8, 13, 21 und so weiter. Als Regel geschrieben: F(0) = 0, F(1) = 1 und F(n) = F(n − 1) + F(n − 2). Die Regel ist rekursiv, und sie direkt in ein rekursives Programm umzusetzen ist leicht, doch dieses Programm erweist sich als sehr langsam.

Warum sich die Rekursion wiederholt

Um F(5) zu finden, fragt das Programm nach F(4) und F(3). F(4) fragt nach F(3) und F(2), also wird F(3) zweimal berechnet, F(2) dreimal und F(1) fünfmal. Als Baum gezeichnet, verdoppeln sich die Aufrufe auf jeder Ebene fast, und insgesamt braucht F(n) 2·F(n + 1) − 1 Aufrufe. Die Teilprobleme überlappen sich: Dieselben kommen immer wieder vor. Das ist das Zeichen, dass dynamische Programmierung hilft.

Zwei Arten, sich zu merken

Memoisation behält die Rekursion bei, schreibt aber jedes Ergebnis in eine Tabelle, und jeder Aufruf schaut in der Tabelle nach, bevor er etwas berechnet. Tabulation füllt die Tabelle bottom-up: zuerst F(0) und F(1), dann F(2) aus diesen, F(3) aus F(2) und F(1) und so weiter bis F(n). So oder so wird jedes Glied einmal berechnet, also kostet F(n) n − 1 Additionen statt einer exponentiellen Zahl von Aufrufen.

Ein Beispiel

Bottom-up für F(7): Beginnen Sie mit 0 und 1. Dann 0 + 1 = 1, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8 und 5 + 8 = 13, also F(7) = 13 nach sechs Additionen. Einfache Rekursion bräuchte für dasselbe Ergebnis 2·F(8) − 1 = 41 Aufrufe. Bei Top-down gehen die ersten Aufrufe am linken Rand des Baums ganz hinunter bis F(1); auf dem Weg zurück nach oben findet fast jeder zweite Aufruf sein Ergebnis schon in der Tabelle.

Woher der Name kommt

Richard Bellman gab der dynamischen Programmierung Anfang der 1950er-Jahre ihren Namen, als er bei der RAND Corporation arbeitete. Später schrieb er, er habe „Programmierung“ im alten Sinn von Planung gewählt und „dynamisch“, weil es eindrucksvoll klang und man schwer etwas dagegen einwenden konnte. Die Methode selbst, ein Problem über die Lösungen kleinerer Versionen davon zu lösen, steckt heute in Rechtschreibprüfungen, Routenplanern und im Vergleich von DNA.

Richard Bellman im Jahr 1962, fotografiert von Alfred Eisenstaedt. Er gab der dynamischen Programmierung Anfang der 1950er-Jahre ihren Namen, als er bei der RAND Corporation arbeitete.
Richard Bellman im Jahr 1962, fotografiert von Alfred Eisenstaedt. Er gab der dynamischen Programmierung Anfang der 1950er-Jahre ihren Namen, als er bei der RAND Corporation arbeitete.

Selbst ausprobieren

Öffnen Sie die App und drücken Sie Schritt. Bei Bottom-up ist die orange Zelle die, die gerade gefüllt wird, und die beiden blauen Zellen sind die Glieder, die sie addiert. Wechseln Sie zu Top-down und sehen Sie zu, wie der Stapel der Aufrufe unter der Tabelle auf n wächst und wieder schrumpft, wenn die Ergebnisse zurückkommen; der Hinweis unter Additionen zählt, wie viele Aufrufe direkt aus der Tabelle beantwortet wurden.

Häufig gestellte Fragen

Was sind überlappende Teilprobleme?

Kleinere Probleme, die eine Lösung mehr als einmal braucht. F(n) und F(n − 1) brauchen beide F(n − 2), also berechnet einfache Rekursion es zweimal, und weiter unten vervielfacht sich die Verschwendung. Dynamische Programmierung löst jedes nur einmal und merkt sich das Ergebnis.

Ist Memoisation schneller als Tabulation?

Beide führen dieselben Additionen aus. Tabulation ist meist etwas schneller, weil sie keine Aufrufe macht, und ihr kann der Stapelspeicher nicht ausgehen; Memoisation ist praktisch, wenn nur einige der kleineren Ergebnisse gebraucht werden, weil sie nur diese berechnet.

Lassen sich Fibonacci-Zahlen noch schneller berechnen?

Ja. Mit F(2k) = F(k)·(2·F(k + 1) − F(k)) und F(2k + 1) = F(k)² + F(k + 1)² braucht das Verfahren der schnellen Verdopplung (Fast Doubling) nur etwa log₂ n Schritte. Die Formel von Binet mit dem Goldenen Schnitt liefert dieselben Zahlen, aber Rundungsfehler machen sie für große n unzuverlässig.

Wie viel Speicher braucht die Tabelle?

Eine vollständige Tabelle enthält n + 1 Zahlen, aber jedes neue Glied braucht nur die beiden davor, also erledigt eine Schleife, die zwei Zahlen speichert, dieselbe Aufgabe mit konstantem Speicher. Die ganze Tabelle zu behalten lohnt sich, wenn Sie alle Glieder haben oder sehen möchten, wie die Methode funktioniert.

Bereit, es auszuprobieren?

Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

Fibonacci mit dynamischer Programmierung ausprobieren