Dynamisches Programmieren WS13-14

Autoren

Jens Klinger

Daniel Franke

Einführung

Das Prinzip "Teile und Herrsche" dient als Grundlage für viele Algorithmen: Um ein umfangreiches Problem zu lösen, zerlegt man es in kleinere Teilprobleme, die unabhängig voneinander gelöst werden können. In der dynamischen Programmierung wird dieses Prinzip aufgegriffen und weiterentwickelt. Im Gegensatz zu "Teile und Herrsche" wird das bottom-up-Verfahren angewendet. D.h. dynamische Programmierung führt dann zu einer Lösung, wenn das Optimierungsproblem aus vielen gleichartigen Teilproblemen besteht, und sich eine optimale Gesamtlösung des Problems aus optimalen Teillösungen zusammensetzt. Zu diesem Zweck werden alle Teilproblem "von-unten-her" berechnet und in eine Tabelle eingetragen um eine erneute Berechnung zu vermeiden.

Bei der Anwendung der dynamischen Programmierung können immer folgende Schwierigkeiten auftreten:

1. Es ist nicht immer möglich, die Lösungen kleinerer Probleme so zu kombinieren, dass sich die optimale Lösung eines größeren Problems ergibt.
2. Die Anzahl der zu lösenden Teilprobleme kann unvertretbar groß werden.
3. Die Zerlegung in unabhängige und überlappungsfreie Teilprobleme ist häufig Illussion.

Es gibt daher viele Probleme, für die die dynamische Programmierung nicht anwendbar bzw. ineffizienter ist als Standardalgorithmen. In diesem Wiki werden daher einige Probleme vorgestellt für die die dynamische Programmierung sehr effizient ist.

Beispiel für auftretende Probleme

Die Entwicklung eines dynamischen Programms kann in vier Schritte unterteilt werden:

1. Charakterisierung der Struktur eines Programms.
2. Definieren des Wertes einer optimalen Lösung rekursiv.
3. Berechnung des Wertes einer optimalen Lösung durch den bottom-up-Ansatz.
4. Konstruktion einer zugehörigen optimalen Lösung aus den schon berechneten Daten.

Rekursive Definition

F(0) = 1

F(1) = 1

F(n) = F(n-1)+F(n-2), mit n \geq 2

Codebeispiel

Abschätzung der Laufzeit

Die Funktion zur Berechnung der Fibonacci-Zahlen wächst exponentiell:

F(n) = [\frac{1}{\sqrt{5}}(1,618...)]

Wir müssen beachten, das wir mit einer rekursiv definierten Funktion, auch für die Abschätzung der Laufzeit eine Rekursionsgleichung erhalten!

Das sehen wir hier:

T(n) = Anzahl der Schritte zur Berechnung von fib(n)

T(0) = 1

T(1) = 1

T(n) = T(n-1)+T(n-2)

Wir sehen das die Formel zur Abschätzung der Laufzeit, identisch ist, mit der Formel zur Berechnung der Fibonacci-Zahl. Daraus können wir wiederum Schlussfolgern, das es sich um einen exponentiellen Aufwand O(1,618n)handelt.

Baumdarstellung

Iterative versus rekursive Berechnung

Needleman-Wunsch-Algorithmus

//TODO Einleitung DNA / Sequenzanalyse / String Matching

Der Needleman-Wunsch-Algorithmus berechnet das optimale globale Alignment von zwei Sequenzen. Er erstellt dabei eine Score zur Bewertung der Ähnlichkeit. Je größer die Score, umso größer die Ähnlichkeit. Das Alignment ist eine Folge von Editieroperationen, um die erste Sequenz in die zweite Sequenz zu überführen. Das soll an einem Beispiel gezeigt werden:

Gegeben sind zwei Proteinsequenzen, z.B. die Sequenzen MAEHTE und AEHREN. Gesucht wird nach der Ähnlichkeit. Werden diese Sequenzen untereinander geschrieben, ist keine Übereinstimmung zu erkennen.

MAEHTE
AEHREN 

Durch Einfügen von Gaps werden nun Übereinstimmungen in Teilstücken erreicht:

MAEHTE_ 
_AEHREN 

Der Abschnitt AEH bildet dabei die längste gemeinsame Teilsequenz, das Alignment. Die Länge der längsten Teilsequenz ist ein Maß für die Ähnlichkeit der Sequenzen. Das heißt, je mehr senkrechte Striche, umso größer die Ähnlichkeit. Die Anzahl der Nichtübereinstimmungen des Vergleichs wird als Editier-Distanz bezeichnet. Dieses Maß gibt an, wie viele Buchstabenänderungen, Einfügungen und Löschungen mindestens erforderlich sind, um eine Sequenz in die andere zu überführen. Im obigen Beispiel etwa lässt sich MAETHE in AEHREN überführen, indem das M gelöscht wird, das T in ein R geändert wird und am Schluss ein N eingefügt wird. Die Editierdistanz beträgt somit 3.

Noch genauer lässt sich die Ähnlichkeit bewerten, wenn die Übereinstimmung gewisser Buchstaben höher bewertet wird als die anderer. Ebenso wenn Nichtübereinstimmungen bestimmter Kombinationen anders bewertet werden und wenn Einfügen und Löschen eine eigene Bewertung bekommen. Im Beispiel wird jede Übereinstimmung mit 3, jede Nichtübereinstimmung mit 0 und jede Einfügung bzw. Löschung mit -1 bewertet. Dazu werden die Variablen match, mismatch und gappenalty eingeführt.

Mit dem Needleman-Wunsch-Algorithmus wird erst das Maß der Ähnlichkeit und anschließend ein Alignment berechnet. Gegeben sind zwei Sequenzen x und y. Die Längen der Sequenzen werden mit m\timesn$ bezeichnet. Bei der Berechnung wird die Funktion $equal$ benutzt, die $i$ und $y$ miteinander vergleicht. Der Funktionswert $equal(i,j)$ ist gleich $match$, wenn das $i$-te Zeichen von $x$ mit dem $j$-ten Zeichen von $y$ übereinstimmt, und sonst gleich $mismatch$: \[equal(i,j)=\left\{ \begin{array}{ll} match,\text{falls $x_{i}=y_{j}$;}\\ mismatch,\text{sonst.} \end{array} \right.\] \[\text{für alle i in {0, ..., m-1 }, j in {0, ..., n-1}}\] Es wird nun eine $m\timesn-Matrix a nach folgender Vorschrift ausgefüllt:

Für das Beispiel ergibt sich folgende Matrix:

Aufwandsbetrachtung und Einsatzgebiete

Fazit