# 10 Dynamische Programmierung 1

[TOC]

[comment]: # (Zuerst ein paar LaTeX-Makros:)

$\newcommand{\N}{\mathbb{N}}
\newcommand{\lc}{\left\lceil}
\newcommand{\rc}{\right\rceil}
\newcommand{\lf}{\left\lfloor}
\newcommand{\rf}{\right\rfloor}
\newcommand{\ra}{\rightarrow}
\newcommand{\Ra}{\Rightarrow}
\newcommand{\O}{\mathcal{O}}$

*Disclaimer:* Diese Mitschrift ist als Ergänzung zur Vorlesung gedacht. Wir erheben keinen Anspruch auf Vollständigkeit und Korrektheit. Wir sind jederzeit froh um Hinweise zu Fehlern oder Unklarheiten an [e-mail].

Wenn Sie an dieser Mitschrift mitarbeiten möchten, melden Sie sich [hier](http://doodle.com/poll/hkiky233kxp7rr8n).

## Einführung

Heute wollen wir, nach den vielen spezifischen Algorithmen und Datenstrukturen der letzten Wochen, zu den allgemeinen Entwurfstechniken zurückkehren.

Wir kehren zurück zum allerersten Entwurfsprinzip: die Induktion. Wie können wir es auch für schwierigere Beispiele anwenden?

## Beispiel: Fibonacci-Zahlen
Diese rekursiv definierte Zahlenfolge ist uns allen bekannt:

$F_0=0, F_1=1, F_{i+2} = F_{i+1} = F_i$ fur $i\geq 0$

Wie implementieren wir eine solche Folge, also eine Funktion, die uns das $n$-te Element bestimmt?

Implementieren wir es mit Rekursion, geht das ganz leicht:

fib(n) {
	if(n<2) return n;
	return fib(n-1) + fib(n-2);
}

Führen wir dieses Programm für $n=100$ aus, dann entsteht ein riesiger Aufrufsbaum:


In der Implementierung oben berechnen wir die selbe Fibonacci-Zahl mehrmals. Im oben dargestellten Baum wird beispielsweise fib(98) und fib(97) mehrfach ausgerufen. Je größer dieser Baum wird, desto öfter berechnen wir ein und denselben Wert. Es ist leicht zu sehen, dass dieser Aufrufbaum exponentielle Grösse hat (think about it!).

Eleganter können wir eine Fibonacci-Zahl iterativ berechnen:

	Fib(0) = 0;
	Fib(1) = 1;
	for(int i=0; i>n-2; i++) {
		Fib(i+2) = Fib(i+1) + Fib(i);
	}

Dieser Trick, der vermeidet, dass wir das selbe $F_i$ immer und immer wieder berechnen, indem wir die $F_i$s von unten nach oben statt von oben nach unten berechnen, ist der Kern der induktiven Entwurfstechnik. Wir merken uns die schon berechneten Fibonacci-Zahlen und verwenden sie erneut.^[Es genügt sogar sich nur die letzten drei berechneten Fibonacci-Zahlen zu merken. Alle früheren benötigen wir nicht mehr.]

Nun zu einem interessanteren Beispiel solcher Induktionen.

## Beispiel: Chipverbindungen (Längste aufsteigende Teilfolge)

Wir haben eine Leiterplatte mit zwei Reihen von $n$ Punkten, die auf vorgegebene Art paarweise miteinander verbunden werden sollen. Die Verbindungen sollen so auf Metallschichten aufgeteilt werden, dass sich in jeder Schicht keine zwei Verbindungen überkreuzen. Wieviele der $n$ Verbindungen können wir maximal auf eine einzige Schicht legen? Anders gesagt: Wieviele Verbindungen können wir auswählen, ohne dass es Überkreuzungen gibt?


Nummerieren wir oben von $1$ bis $n$ und unten gemäss den Verbindungen (wie in der Skizze), so können wir leicht testen, ob sich zwei Verbindungen überkreuzen: Zwei Verbindungen $i$ und $j$ mit $i < j$ überkreuzen sich genau dann, wenn unten $j$ links von $i$ steht. Wir wollen also aus der unteren Folge eine aufsteigende Teilfolge auswählen.

Wie finden wir in einer Permutation der Zahlen $1$ bis $n$ die *längste aufsteigende Teilfolge*?

Wenn wir sämtliche $2^n$ mögliche Teilfolgen ausprobieren, dauert das zu lange. Also probieren wir Induktion und fangen ganz naiv an.

Wir betrachten die ersten $i$ Zahlen der Eingabe. Angenommen, wir kennen bereits eine aufsteigende Teilfolge für diese Eingabe. Um diese Teilfolge zu erweitern, müssen wir wissen, mit welcher Zahl diese Teilfolge endet (also die grösste Zahl in dieser aufsteigenden Teilfolge, die End-Zahl). Naiv würden wir also versuchen an alle Teilfolgen der ersten $i$ Elemente das $(i+1)$-te Element anzuhängen.

Wir müssen uns allerdings nicht alle Teilfolgen gleicher Länge merken. Es reicht, wenn wir uns diejenige Lösung merken, deren End-Zahl am kleinsten ist. Können wir irgendeine andere Teilfolge derselben Länge erweitern, so können wir auch die Teilfolge mit kleinster End-Zahl erweitern.

Es ist aber nicht notwendigerweise so, dass wir immer die längste gefundene aufsteigende Teilfolge erweitern können. Deshalb müssen wir uns für *jede* Folgenlänge die kleinste End-Zahl einer aufsteigenden Folge dieser Länge merken.

*Invariante*: Für jede schon gesehene Folgenlänge $l$ merken wir uns die bisher kleinste End-Zahl einer aufsteigenden Folge der Länge $l$.

Beispiel

3 2 5 1 6 4

Initilisiere alles mit unendlich (hier '-')
Teillänge: 1 2 3 4 5
Endzahl: - - - - -

Betrachte die '3': Erste Sequenz der Länge 1
Teillänge: 1 2 3 4 5
Endzahl: 3 - - - -

Betrachte die '2': Bessere Sequenz der Länge 1
Teillänge: 1 2 3 4 5
Endzahl: 2 - - - -

Betrachte die '5': Erste Sequenz der Länge 2
Teillänge: 1 2 3 4 5
Endzahl: 2 5 - - -

Betrachte die '1': Bessere Sequenz der Länge 1
Teillänge: 1 2 3 4 5
Endzahl: 1 5 - - -

Betrachte die '6': Erste Sequenz der Länge 3
Teillänge: 1 2 3 4 5
Endzahl: 1 5 6 - -

Betrachte die '4': Bessere Sequenz der Länge 2
Teillänge: 1 2 3 4 5
Endzahl: 1 4 6 - -

Aus dieser Tabelle können wir nun direkt ablesen, dass $3$ die Länge der längsten aufsteigenden Teilfolge ist und dass diese mit einer $6$ endet. Es ist aber nicht so, dass in der Tabelle direkt die beste Folge steht. Die $4$ als Endzahl der Länge $2$ steht beispielsweise rechts der $6$ können wir also nicht in der längsten Teilfolge verwenden. Um nicht nur die Länge sondern auch die Teilfolge zu finden, können wir uns beispielsweise bei jedem Element merken, was das beste vorangehende Element war. So können wir am Ende die Teilfolge $2,5,6$ rekonstruieren.

Elemente: 3 2 5 1 6 4
Vorgänger: - - 2 - 5 1

Beim Ausfüllen der Tabelle suchen wir in jedem Schritt nach dem kleinsten Eintrag, der grösser ist als unser neues Element, und schreiben dort unser neues Element hin. Die Position dieses Eintrages können wir mittels binärer Suche finden, weil die Tabelle zu jedem Zeitpunkt aufsteigend sortiert ist (think about it!). Somit dauert ein Eintrag nur $\O(\log n)$ und das Ausfüllen der gesamten Tabelle kostet $\O(n \log n)$.

Wenn wir etwas Zusätzliches über die Lösungslänge wissen, dann geht es oft gar noch schneller. Wissen wir beispielsweise, dass die längste Teilfolge fast Länge $n$ hat, dann ist es besser die binäre Suche durch eine exponentielle Suche (die vom rechten Rand der schon ausgefüllten Tabelle nach links hin startet) zu ersetzen. Da diese Suche dann oft sehr rasch abbricht, erreichen wir damit gar lineare Laufzeit.

## Beispiel: Editierdistanz

Wieviele Veränderungen braucht es um von einem Wort auf ein anderes zu kommen?

LIEBE (Zeichen entfernen)
LEBE (Zeichen hinzufügen)
LEBER (Zeichen ändern)
LEDER

Wir dürfen die drei Operationen *hinzufügen*, *entfernen*, *ändern* in beliebiger Folge ausführen. Was ist die kürzeste Folge von Editieroperationen, die von ``LIEBE`` nach ``LEDER`` führt? Die Länge einer solchen kürzesten Folge heisst *Editierdistanz*.

Die folgende kompakte Darstellung dieser Operationen nennt man *Alignment*:

LIEBE_
L_EDER

Hier wird in der zweiten Position im unteren Wort eine Lücke eingefügt und in der vierten Position ein Zeichen ersetzt. Aus so einem Alignment, lässt sich die Anzahl Operationen direkt ablesen.

An jeder Position können vier mögliche Fälle auftreten:

_ X X X
X _ X Y

Es kann entweder oben oder unten eine Lücke eingefügt werden, oder es steht sowohl oben als auch unten ein Zeichen. Es kann dasselbe Zeichen oder unterschiedliche Zeichen oben und unten stehen. Der Fall, bei den oben und unten eine Lücke steht, muss nicht berücksichtigt werden, da dies unsinnig ist. Man könnte diese Position aus dem Alignment entfernen.

Uns interessiert das Alignment, das die kleinste Anzahl von Editieroperationen repräsentiert.

Das *Optimalitätsprinzip der dynamischen Programmierung* besagt nun Folgendes: Wenn ich eine optimale Lösung habe, dann ist eine Teillösung dieser Lösung selbst auch eine *optimale* Teillösung. Wäre das nicht so, so könnten wir diese Teillösung durch eine bessere ersetzen, wodurch auch eine bessere Gesamtlösung entstehen würde. Das ist aber ein Widerspruch, da wir von einer optimalen Lösung ausgegangen sind. Dieses Prinzip lässt sich auf das Sequence Alignment Problem anwenden.

Ein möglichst kurzes Alignment entspricht einer kleinen Editierdistanz. Von ``abc`` nach ``edf`` kann man z.B mit sechs Operationen kommen, oder auch nur mit drei:

a b c _ _ _
_ _ _ d e f

a b c
d e f

Verallgemeinert betrachten wir die Eingabe $a_1a_2a_3\dots a_n$ und $b_1b_2b_3\dots b_m$.

Wir bezeichnen nun die Kosten des optimalen Alignments für die beiden Anfangsstücke bis $n$ und $m$ als $ED(n,m)$. Dies können wir nun induktiv/rekursiv ausdrücken als:

$$ED(n,m) = \min\begin{cases}
ED(n-1,m)+1 && \text{Platzhalter einfügen in $b$}\\
ED(n,m-1)+1 && \text{Platzhalter einfügen in $a$}\\
ED(n-1,m-1)+d && \text{d=1, falls $a_n \neq b_m$; $d=0$ sonst}\\
\end{cases}$$

Wobei $ED(n,m)$ nur definiert ist, für $n,m \geq 0$. Als Basisfall der Induktion definieren wir $ED(0,0)=0$.

Zum Einsetzen eines Eintrages betrachten wir also nur die drei Einträge oben, links und links oben (sofern überhaupt vorhanden). Machen wir es am Beispiel ``FISCH`` vs. ``FROSCH`` und schreiben das Tableau hin: (die ``->`` und ``\_`` deuten dabei an, woher in einigen Zellen das Minimum herkam)

ED
0 1 2 3 4 5
F I S C H

0 0-> 1-> 2-> 3-> 4-> 5
|\_
1 F 1 0-> 1-> 2-> 3-> 4
\_ \_ \_
2 R 2 1 1-> 2-> 3-> 4
\_ \_ \_ \_
3 O 3 2 2 2-> 3-> 4
\_
4 S 4 3 3 2 3 4
\_
5 C 5 4 4 3 2-> 3
\_
6 H 6 5 5 4 3 2

Die Distanz zwischen ``FISCH`` und ``FROSCH`` ist also $2$ und dank den Pfeilen in der Tabelle können wir das optimale Alignment rekonstruieren:^[Zwingend nötig sind die Pfeile nicht. Wir können auch vom Ende her zurückrechnen und uns in jedem Eintrag fragen: Wie können wir hierhin gekommen sein?]

FI_SCH
FROSCH

Wieviel Zeit benötigen wir nun, um diese Tabelle auszuführen? Die Tabelle hat $n\cdot m$ Einträge und jeder Eintrag kann in konstanter Laufzeit berechnet werden, da wir nur drei weitere Einträge, die bereits berechnet wurden, betrachten müssen. Daher kann die ganze Tabelle in $\O(n\cdot m)$ Laufzeit berechnet werden.

Das eben vorgestellte Verfahren nennt man *Dynamisches Programm*. Die Lösungsmethode basiert auf dem oben beschriebenen Optimalitätsprinzip und wird *Dynamische Programmierung*^[Dieser Name ist alles andere als selbsterklärend.] genannt.

## Beispiel: Matrixkettenmultiplikation
Wir wollen $n$ Matrizen miteinander multiplizieren:
$$A_1 \times A_2 \times \dots A_n$$

Weil das Assoziativitätsgesetz bei der Matrixmultiplikation gilt, können wir die Reihenfolge der Multiplikationen unterschiedlich wählen.

$$((A_1 \times ((A_2 \times A_3) \times A_4)) \times A_5) = ((A_1 \times A_2) \times A_3) \times (A_4 \times A_5)$$

Das Resultat ist zwar immer das gleiche, aber der Rechenaufwand kann sich je nach Klammerung ändern.

Für eine Multiplikation der Matrix $A_1$ der Grösse $r \times s$ mit der Matrix $A_2$ der Grösse $s \times u$, haben wir Kosten $r\cdot s \cdot u$ und erhalten als Resultat eine Matrix der Grösse $r \times u$.

Wenn wir nun drei Matrizen multiplizieren sollen mit Grössen $r \times s$, $s \times u$ und $u \times v$, so können wir zuerst die ersten beiden Matrizen multiplizieren und dann die resultierende Matrix mit der dritten Matrix. Die Kosten wären dann $r\cdot s\cdot u + r \cdot u \cdot v$. Multiplizieren wir andererseits zuerst die letzten beiden Matrizen und erst dann die erste Matrix, dann brauchen wir dafür $s\cdot u \cdot v + r \cdot s \cdot v$ elementare Multiplikationen.

Das Bestimmen der optimalen Reihenfolge geht hoffentlich viel schneller das anschliessende Ausführen der Multiplikationen. Für eine Bibliothek mathematischer Software kann es also durchaus Sinn machen sich vorher zu überlegen was die beste Multiplikationsreihenfolge ist.

Induktiv überlegen wir uns: Was ist die letzte Matrixmultiplikation, die wir ausführen? Die beiden Operanden dieser finalen Multiplikation hängen davon ab, welche zusammenhängenden Teilstücke der Matrixfolge wir schon miteinander multipliziert haben. Wenn wir für einen Index $k$ bereits die Matrizen $A_1$ bis $A_k$ miteinander multipliziert haben und auch schon $A_{k+1}$ bis $A_n$ verrechnet haben, dann bleibt als letzte Multiplikation $(A_1 \times A_2 \times \dots \times A_k) \times (A_{k+1} \times A_{k+2} \times A_n)$ zu berechnen.

Wir suchen nun das beste $k$, also die beste Aufteilung in zwei Teilstücke um den Gesamtaufwand zu minimieren.

$M(i,j) = \min_k \left\{ \underbrace{M(i,k)+ M(k+1,j)}_{\text{optimale Teilstücke}}+ \underbrace{u \cdot v \cdot w}_{\text{letzte Multiplikation}} \right\}$

M | j n
-------------------------
| |
i |_____M(i,j)
|
n |

Laufzeitanalyse: Die Tabelle hat $n^2$ Einträge. Um einen Eintrag zu berechnen, müssen wir das minimale $k$ finden. Dafür gibt es $\O(n)$ Möglichkeiten, die wir alle betrachten müssen. Die Tabelle kann also $O(n^3)$ Laufzeit berechnet werden.

*Als Übungsaufgabe:* Wie müssen wir das Tableau erweitern, sodass wir die Lösung (die optimale Klammerung) rasch auslesen können.