Dynamische Programmierung
Die dynamische Programmierung kann man anwenden, wenn eine Methode mehrfach mit identischen Argumenten aufgerufen wird. Die Idee der dynamischen Programmierung besteht darin, das Ergebnis des jeweils ersten Aufrufs in einer Datenstruktur zu speichern. Beim zweiten Aufruf wird dann nicht die gleiche Berechnung noch einmal durchgeführt, sondern das zuvor berechnete Ergebnis wird in der Datenstruktur nachgeschlagen. Damit dieser Ansatz eine Implementierung liefert, die effizienter ist als die ursprüngliche Implementierung, muss das Nachschlagen der Ergebnisse in der Datenstruktur entsprechend effizient sein. Häufig wird für die Datenstruktur daher ein Array verwendet. Um in einem Array das Ergebnis effizient nachschlagen zu können, müssen wir in der Lage sein, für die Argumente der Methode einen Index zu berechnen, der das Ergebnis der Methode speichert.
Beispiel
Um die Methode der dynamischen Programmierung zu motivieren, die wir uns im Folgenden anschauen, wollen wir uns die Implementierung der Methode fib noch mal etwas genauer anschauen.
Wir wollen uns einmal anschauen, welche Aufrufe der Methode fib für den Aufruf fib(5) durchgeführt werden.
Bei der Struktur, welche die Aufrufe der Methode darstellt, handelt es sich um einen Baum.
Daher wird die Struktur auch als Rekursionsbaum bezeichnet.
Jeder Knoten des Baumes ist ein Aufruf der Methode fib.
Ein Knoten hat dann jeweils die rekursiven Aufrufe der Methode als Nachfolger.
Der Knoten fib(5) hat zum Beispiel die Nachfolger fib(4) und fib(3).
fib(5)Abbildung 3 zeigt, dass viele Aufrufe der Methode fib mehrfach durchgeführt werden.
Zum Beispiel taucht der Aufruf fib(2) dreimal im Baum auf.
Diese Aufrufe liefern alle das gleiche Ergebnis, daher sollten wir vermeiden, Aufrufe wie fib(2) mehrfach auszuführen.
Mithilfe der dynamischen Programmierung können wir die mehrfache Berechnung dieser Werte vermeiden.
Bei der dynamischen Programmierung werden die Ergebnisse einer Methode in einer Datenstruktur gespeichert. Wird die Methode dann mit den gleichen Argumenten noch einmal aufgerufen, so wird das Ergebnis nicht erneut berechnet, sondern in der Datenstruktur nachgeschlagen. Wir können diese Methode nutzen, um die Berechnung einer Fibonacci-Zahl effizienter durchzuführen. Um uns die Mehrfachberechnungen zu sparen, merken wir uns einfach die bereits berechneten Werte in einem Array.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static int fibDyn(int n) {
var memo = new Integer[n + 1];
return fibDyn(memo, n);
}
private static int fibDyn(Integer[] memo, int n) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
if (memo[n] == null) {
memo[n] = fibDyn(memo, n - 1) + fibDyn(memo, n - 2);
}
return memo[n];
}
}
Um zu verstehen, wie die Aufrufe im Array memo nachgeschlagen werden, müssen wir wissen, dass Java die Argumente einer Methode von links nach rechts auswertet.
Das heißt, beim Aufruf fibDyn(memo, n - 1) + fibDyn(memo, n - 2) wird der Aufruf fibDyn(memo, n - 1) ausgeführt bevor der Aufruf fibDyn(memo, n - 2) ausgeführt wird.
Die folgende Abbildung zeigt die Aufrufstruktur mithilfe der dynamischen Programmierung.
fibDyn(5)Da wir die ersten beiden Einträge des Arrays gar nicht verwenden, können wir den Speicherverbrauch der Implementierung noch optimieren, indem wir ein Array der Größe Math.max(0, n - 1) anlegen und jeweils memo[n - 2] nutzen.
Wir müssen die Funktion Math.max nutzen, da Java einen Laufzeitfehler wirft, wenn wir versuchen, ein Array mit einer negativen Größe zu erzeugen.
Diese Implementierung spart zwei Arrayeinträge, hat aber den Nachteil, dass sie schwieriger zu verstehen ist.
Die Idee der dynamischen Programmierung kann auf verschiedene Arten angewendet werden. Wir beschäftigen uns hier nur damit, wie man dynamische Programmierung anwenden kann und dabei die grundlegende Struktur der Originalimplementierung möglichst erhält. Es gibt aber auch Ansätze, bei denen das Füllen der Datenstruktur und das Auslesen stärker getrennt werden. Zur Implementierung der Fibonacci-Funktion können wir zum Beispiel ein Array mit Zahlen füllen und anschließend im gefüllten Array den entsprechenden Wert nachschlagen.
Abschätzung der Laufzeit
Um noch einmal den Ansatz der dynamischen Programmierung zu motivieren, wollen wir uns Gedanken über die Laufzeiten der beiden Implementierungen machen.
Zuerst geben wir eine Rekurrenz für die Laufzeit der Methode fib an.
Um das Problem etwas zu vereinfachen, gehen wir davon aus, dass alle konstanten Aufwände, die in der Methode vorkommen, identisch sind.
Wir könnten für die Konstante \(c_1\) hier zum Beispiel das Maximum der tatsächlichen Konstanten nutzen.
Um zu bestimmen, wie häufig die Konstante \(c_1\) aufaddiert wird, wenn wir den Wert von \(T_{\texttt{fib}}\) berechnen, wollen wir die Anzahl der Knoten im Rekursionsbaum abschätzen.
Zuerst führen wir ein paar Begriffe ein, die sich auf Baumstrukturen beziehen.
Ein Pfad in einem Baum ist in einem Baum ein Weg von einer Wurzel zu einem Blatt.
Ein Pfad wird durch die Knoten beschrieben, die er besucht.
In Abbildung 3 gibt es zum Beispiel den Pfad fib(5), fib(4), fib(3) fib(2), fib(1) und den Pfad fib(5), fib(4), fib(2) fib(0).
Die Höhe eines Baumes ist die Länge des längsten Pfades.
Die Höhe des Baumes in Abbildung 3 ist zum Beispiel 5, da fib(5), fib(4), fib(3) fib(2), fib(1) der längste Pfad in diesem Baum ist.
Um die Anzahl der Blätter im Rekursionsbaum abzuschätzen, observieren wir zuerst, dass man die Anzahl der Blätter in einem vollständigen Binärbaum berechnen kann, wenn man die Höhe kennt. Ein vollständiger Binärbaum ist ein Binärbaum, dessen Pfade alle die gleiche Länge haben. Abbildung 4 zeigt einen vollständigen Binärbaum der Höhe 4.
Ein vollständiger Binärbaum der Höhe \(h\) hat \(2^h - 1\) Knoten. Diese Zahl ergibt sich als Summe von Zweierpotenzen. Ein vollständiger Binärbaum hat einen Wurzelknoten. Auf der ersten Ebene hat er zwei Knoten, auf der zweiten Ebene vier, auf der dritten Ebene acht und so weiter. Um die gesamte Zahl der Knoten zu berechnen, muss man diese Zahlen addieren. Wenn \(h\) die Höhe ist, erhalten wir also
\[\sum_{i = 0}^{h} 2^i = 2^{h + 1} - 1\]Knoten. Bei der Formel \(\sum_{i = 0}^{h} 2^i\) handelt es sich um die Partialsumme einer geometrische Reihe. Das Ergebnis einer solchen Partialsumme lässt sich mit der Formel \(\frac{1 - 2^{h+1}}{1 - 2} = \frac{1 - 2^{h+1}}{-1} = 2^{h+1} - 1\) bestimmen.
Um die Anzahl der Knoten im Rekursionsbaum der Methode fib abzuschätzen, wollen wir die Anzahl der Knoten in einem vollständigen Binärbaum bestimmen, der auf jeden Fall mehr Knoten hat als der Rekursionsbaum in Abbildung 3.
Um eine obere Schranke für die Laufzeit der Methode zu erhalten, suchen wir also nach einem vollständigen Binärbaum, der mehr Knoten hat als der Rekursionsbaum.
Dazu bestimmen wir die Länge des längsten Pfades in diesem Rekursionsbaum.
Der längste Pfad ist der linkeste Pfad.
Dieser Pfad hat die Länge \(n\), wenn wir fib(n) berechnen.
Ein vollständiger Binärbaum der Höhe \(n\) hat
Knoten.
Damit ist die Laufzeit der Methode fib in \(\mathcal{O}(2^n)\), wobei \(n\) der Index ist, für den wir die Fibonacci-Zahl berechnen.
Es stellt sich jetzt die Frage, ob wir die Laufzeit der Methode mit dieser Schätzung sehr stark überschätzen.
Eine Größenordnung wie \(\mathcal{O}(2^n)\) gibt ja nur eine obere Schranke an.
Das heißt, die Laufzeit der Methode fib könnte immer noch linear sein, auch wenn wir wissen, dass sie in \(\mathcal{O}(2^n)\) ist.
Intuitiv möchten wir auch ausdrücken können, dass die Lösung für ein bestimmtes Problem genau exponentiell viele Schritte benötigt.
Um diese Eigenschaft formal auszudrücken, definieren wir zuerst den Begriff der unteren Schranke.
Definition 3 (Asymptotische untere Schranke)
Sei \(f \colon \mathbb{N} \rightarrow \mathbb{R}\). Dann definieren wir
\[\Omega(f) := \{ g \colon \mathbb{N} \rightarrow \mathbb{R} \mid f \le_{\text{as}} g \}.\]Die Menge \(\Omega(f)\) ähnelt sehr stark der Definition \(\mathcal{O}(f)\). Der einzige Unterschied ist, dass wir hier ein \(f \le_{\text{as}} g\) schreiben, während die Definition von \(\mathcal{O}(f)\) an dieser Stelle \(g \le_{\text{as}} f\) nutzt.
Wir wollen jetzt noch eine untere Schranke für die Laufzeit der Methode fib angeben.
Dazu identifizieren wir einen Binärbaum, der die Anzahl der Knoten im Rekursionsbaum nach unten abschätzt.
Dazu betrachten wir den kürzesten Pfad im Rekursionsbaum von fib.
Der kürzeste Pfad in diesem Baum ist der rechteste Pfad.
Dieser Pfad entsteht, wenn wir immer wieder dem rekursiven Aufruf fib(n - 2) folgen.
In diesem Fall verringern wir bei jedem Schritt das ursprüngliche Argument um 2.
Dieser Prozess endet, wenn der Zahlenwert entweder 1 oder 0 ist.
Das heißt, wir möchten wissen, wie häufig wir 2 subtrahieren müssen, bis wir bei 1 oder 0 ankommen.
Bei einer ungeraden Zahl landen wir am Ende bei 1, während wir bei einer geraden Zahl bei 0 enden.
Im Fall einer geraden Zahl hat der Pfad \(\frac{n}{2} + 1\) Knoten.
Bei einer ungeraden Zahl haben wie \(\frac{n + 1}{2}\) Knoten.
Wir wollen nun die Anzahl der Knoten bestimmen, die der vollständige Binärbaum jeweils hat.
Fall n gerade ist, erhalten wir
Knoten.
Falls n ungerade ist, erhalten wir
Knoten.
In beiden Fällen ist die Anzahl der Knoten und damit die Laufzeit der Methode fib also in \(\Omega\left({\sqrt 2}^n\right)\).
Als erstes stellt sich nun die Frage, ob es bei einer Größenordnung mit einem exponentiellen Wachstum einen Unterschied macht, welche Basis die Funktion verwendet. Anders ausgedrückt, müssen wir uns Gedanken darüber machen, ob Mengen wie \(\mathcal{O}(2^n)\) und \(\mathcal{O}({\sqrt{2}}^n)\) identisch sind.
Professor Klein behauptet, dass für die Funktionen \(f(x) = 2^x\) und \(g(x) = {\sqrt 2}^x\) die Relation \(f \le_{\text{as}} g\) gilt. Das heißt, Professor Klein gibt ein \(c\) und ein \(n_0\) an, so dass für alle \(n \in \mathbb{N}\) gilt, dass \(f(n) \le c \cdot g(n)\), \(2^n \le c \cdot {\sqrt 2}^n\) gilt. Es gilt aber \({\sqrt 2}^n \cdot {\sqrt 2}^n = \left({\sqrt 2 \cdot \sqrt 2}\right)^n = 2^n\). Das heißt, dass das \(c\) von Professor Klein größer gleich \(\sqrt 2^n\) für alle \(n \in \mathbb{N}\) mit \(n \ge n_0\) sein müsste. Das kann aber gar nicht sein. Wir wollen diese Tatsache noch einmal formal beweisen. Um den Beweis etwas verständlicher zu halten, betrachten wir im folgenden Beweis zwei exponentiellen Funktionen mit ganzzahligen Basen.
Behauptung: Seien \(f : \mathbb{N} \rightarrow \mathbb{R}_{\ge 0}, f(x) = 6^x\) und \(g : \mathbb{N} \rightarrow \mathbb{R}_{\ge 0}, g(x) = 2^x\). Die Aussage \(f \le_{\text{as}} g\) gilt nicht.
Beweis: Um diese Aussage zu beweisen, beweisen wir, dass \(\neg (f \le_{\text{as}} g)\) wahr ist.
Sei \(c \in \mathbb{R}_{>0}\). Sei \(n_0 \in \mathbb{N}\). Setze \(n = \max \{\lceil \log_3 c \rceil + 1, n_0\}\). Dann gilt \(n \ge n_0\). Außerdem gilt das folgende.
\[\begin{align*} f(n) & = 6^n\\ & = \left({3 \cdot 2}\right)^n\\ & = 3^n \cdot 2^n\\ & = 3^{\max \{\lceil \log_3 c \rceil + 1, n_0\}} \cdot 2^n\\ & \ge 3^{\lceil \log_3 c \rceil + 1} \cdot 2^n\\ & > 3^{\lceil \log_3 c \rceil} \cdot 2^n\\ & \ge 3^{\log_3 c} \cdot 2^n\\ & = c \cdot 2^n\\ & = c \cdot g(n) \end{align*}\]Den Beweis zuvor können wir ganz analog auch für die Funktionen \(f(x) = 2^x\) und \(g(x) = \sqrt{2}^x\) beweisen. Größenordnungen wie \(\mathcal{O}(2^n)\) und \(\mathcal{O}({\sqrt{2}}^n)\) sind also nicht identisch sondern unterschiedlich.
Mit den Mitteln, die wir zur Verfügung haben, können wir die Laufzeit der Methode fib nur durch unterschiedliche Funktionen nach unten und oben abschätzen.
In einfacheren Fällen sind diese Funktionen für die untere und die obere Schranke aber identisch.
Für diesen Fall definieren wir eine scharfe Schranke.
Definition 3 (Asymptotisch scharfe Schranke)
Sei \(f \colon \mathbb{N} \rightarrow \mathbb{R}_{\ge 0}\). Dann definieren wir
\[\Theta(f) := \mathcal{O}(f) \cap \Omega(f).\]