Fibonacci-Zahlen berechnen - dynamische Programmierung

Einige Strategien, um Algorithmen zu entwerfen, treten immer wieder auf, weil sie so erfolgreich sind - so zum Beispiel auch die Strategie, die als dynamische Programmierung bezeichnet wird.

Dynamische Programmierung

Der Begriff dynamische Programmierung ist historisch bedingt, er beschreibt unglückseligerweise nicht das Wesentliche dieser Entwurfsmethode. Eine wirklich treffende Bezeichnung ist noch niemandem eingefallen – vielleicht kommt akkumulierende Berechnung der Sache am nächsten.

Es geht bei der Berechnung nämlich darum, anfallende Ergebnisse von Teilproblemen zu speichern und für das Gesamtergebnis weiterzuverwenden.

Fibonacci-Zahlen berechnen

Ein Paradebeispiel ist die Berechnung der $n$ -ten Fibonacci-Zahl $f_{n}$ . Die Fibonacci-Folge $f_{0}, f_{1}, f_{2}, . . .$ lautet

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

Die Fibonacci-Zahl $f_{n}$ berechnest du aus der Summe der beiden vorhergehenden Fibonacci-Zahlen $f_{n - 1}$ und $f_{n - 2}$ .

Um also $f_{n}$ zu berechnen, musst du zuerst $f_{n - 1}$ und $f_{n - 2}$ berechnen,
um $f_{n - 1}$ zu berechnen, musst du $f_{n - 2}$ und $f_{n - 3}$ berechnen,
um $f_{n - 2}$ zu berechnen, musst du $f_{n - 3}$ und $f_{n - 4}$ berechnen
usw.

Du siehst, dass du $f_{n - 2}$ an mehreren Stellen benötigst, ebenso $f_{n - 3}$ usw. Statt diese Werte immer wieder von vorne zu berechnen, berechnest du sie nur einmal und speicherst sie für eine spätere Weiterverwendung.

Iterative Berechnung: Zwischenergebnisse speichern

Du füllst hierzu eine Liste $f$ nach und nach mit der Fibonacci-Folge, indem du schon berechnete Fibonacci-Zahlen in der Liste speicherst.

Du initialisierst die Liste mit $[1, 1]$ und berechnest dann jeweils den nächsten Wert, indem du einfach die beiden letzten berechneten Werte $f [- 1]$ und $f [- 2]$ aus der Liste ausliest, addierst und diesen neuen Wert an die Liste anhängst.

In der Programmiersprache Python sieht das so aus:

# berechnet die Fibonacci-Folge f[0],...,f[n]
def fibo(n):
    f=[1, 1]
    for _ in range(n-1):
        f+=[f[-1]+f[-2]]
    return f[n]

Das Ganze beansprucht nur lineare Zeit, also $n$ Schritte für die $n$ -te Fibonacci-Zahl.

Wenn dich nur die $n$ -te Fibonacci-Zahl $f_{n}$ interessiert, dann brauchst du auch nicht die ganze Liste zu speichern, weil du ja immer nur die beiden letzten Werte $f [- 1]$ und $f [- 2]$ der Liste benötigst. Du speicherst die jeweiligen letzten beiden Werte einfach in zwei Variablen $f$ und $g$ .

# berechnet die n-te Fibonacci-Zahl (iterativ)
def fibo(n):
    f, g = 1, 1
    for _ in range(n-1):
        f, g = g, f+g
    return g

Rekursive Berechnung

Wenn du dagegen jede Fibonacci-Zahl jedes Mal von vorne berechnest, benötigst du exponentielle Zeit, etwa in der folgenden rekursiven Implementierung:

# berechnet die n-te Fibonacci-Zahl (rekursiv)
def fibo(n):
    if n==0 or n==1:
        return 1
    else:
        return fibo(n-1) + fibo(n-2)

Achtung: Don't use it. Dieses Programm ist ein Beispiel dafür, wie du es nicht machen solltest.

Programme ausprobieren

Probiere einmal die iterative und die rekursive Berechnung aus.

Bereits bei fibo(35) tritt dem rekursiven Programm der Schweiß auf die Stirn…

Für die iterative Implementierung ist selbst fibo(100) kein Problem (Ergebnis: 573147844013817084101)

Mit der angegebenen rekursiven Implementierung ist die Berechnung von fibo(100) dagegen völlig undurchführbar.

Beispiele für dynamische Programmierung

Es gibt eine ganze Reihe von Algorithmen, die auf dynamischer Programmierung bzw. akkumulierender Berechnung basieren. Meist wird dabei ein zweidimensionales Array mit Zwischenergebnissen gefüllt.

Einfach zu verstehen ist die Berechnung der Editierdistanz, um die Ähnlichkeit von zwei Wörtern zu bestimmen (zum Beispiel von DSCHUNGEL und DUSCHGEL).

Weitere Beispiele sind der Floyd-Algorithmus zur Berechnung der kürzesten Wege zwischen allen Knoten in einem Graphen sowie der CYK-Algorithmus zur Erkennung von Wörtern einer kontextfreien Grammatik.

Dieses Werk steht unter der freien Lizenz
CC BY-SA 4.0 → Was bedeutet das? serlo.org