Dynamisches Programmieren WS13-14

Aus ProgrammingWiki
< AuK
Archivierte Version vom 2013-11-09T08:14:47+00:00. Aktuelle Version

Inhaltsverzeichnis

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.

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.

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

  • 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.
  • Die Anzahl der zu lösenden Teilprobleme kann unvertretbar groß werden.
  • 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.

Doch zunächst soll auf grundlegende Schwierigkeiten bei der dynamischen Programmierung hingewiesen werden.

Rekursiver Lösungsansatz = rekursiver Algorithmus?


In diesem Beispiel soll anhand der Berechnung der Fibonacci-Folge gezeigt werden, warum in der dynamischen Programmierung zumeist iterative Lösungsmethoden mit Bottom-up-Ansatz verwendet werden.

Zur Erinnerung, die Fibonacci-Folge ist eine unendliche Folge von Zahlen, bei der die Summe der beiden Vorgänger die unmittelbar folgende Zahl ergibt.

Rekursive Definition


f(0) = 1 f(1) = 1 f(n) = f(n-1)+f(n-2), \text{mit n} \geq 2

Rekursive Lösung



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) = \text{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
Details
Fib(5).jpg



Lösungsansatz
Aufgrund dieser Schwierigkeiten wird in der dynamischen Programmierung traditionell der iterative Lösungsansatz bevorzugt. Doch auch dieser hat Nachteile. Wie bereits erwähnt, müssen alle Teillösungen berechnet werden, auch diese, die nicht zur optimalen Lösung des Problems beitragen. Der größte Nachteil besteht jedoch darin, dass der rekursiv gebildete Top-down-Ansatz in einen iterativen Bottom-up-Algorithmus umgewandelt werden muss. Das ist sehr aufwändig, da der Algorithmus erst umgewandelt werden muss und sich bei dieser Umwandlung schnell Fehler einschleichen.
Doch auch aus dieses Problem lässt sich lösen. Eine Variante der Dynamischen Programmierung, die oft so effizient wie die traditionelle Methode ist, heißt Memisation (eng. memoizing). Im nächsten Abschnitt wird am 0/1 Rucksackproblem gezeigt, wie iterative und rekursive Lösungsansätze aussehen können.
Lösung des 0/1 Rucksackproblems
Beim 0/1 Rucksackproblem gilt die Optimalitätsbeidingung, denn die optimale Gesamtlösung lässt sich aus optimalen Teilproblemen zusammensetzen.
Bezogen auf das Rucksackproblem bedeutet das, Gegenstand i wird in den optimal gefüllten, auch leeren, Rucksack gelegt. D.h. alle zur Auswahl stehenden Gegenstände können solange in den Rucksack gelegt werden, solange sie noch Platz haben. 
Für den optimalen gefüllten Rucksack gilt die rekursive Definition mit:
i=\text{ Gegenstand }
g=\text{ Gewicht }
w=\text{ Wert des Gegenstands }
n = \text {Anzahl der Gegenstände }
K = \text{ Restkapazität des Rucksacks }
wert(i,g) = \text{ Optimaler Wert für die Gegenstände } 
wert(n,K)=\text{ Optimaler Gesamtwert }


$wert(i,g) = \begin{cases} 
		0, & wenn \ i =0 \\ 
		wert(i-1, g), & wenn \ i > 0 \ und \ g-g_{i} < 0\\ 
		max(wert(i-1,g), wert(i-1, g-g_{i})+w_{i}), & sonst \\
		\end{cases}$

Der Fall wert(i,g) = wert(i-1,g) bezieht sich auf einen Gegenstand, der die Restkapazität des Rucksacks überschreiten würde. D.h. wert(i-1,g) ist der Maximalwert aus 1,2,...,i-1 Gegenständen mit Bezug auf die Kapazität des Rucksacks. Der letzte Fall wert(i,g) = max(wert(i-1,g), wert(i-1, g-g_{i})+w_{i}) beschreibt die Maximierung des Werts in Berücksichtigung des Gewichts.
Iterativer Algorithmus



$i$
1
2
3
4
5




$g_i$
2
2
6
5
4




$w_i$
6
3
5
4
6







Der Aufruf von (gesamtwert-iterativ 5 10) erzeugt folgende Tabelle:



n/K
0
1
2
3
4
5
6
7
8
9
10




0
0
0
0
0
0
0
0
0
0
0
0




1
0
0
6
6
6
6
6
6
6
6
6




2
0
0
6
6
6
9
9
9
9
9
9




3
0
0
6
6
9
9
9
9
11
11
14




4
0
0
6
6
9
9
9
10
11
13
14




5
0
0
6
6
9
9
12
12
15
15
15





Needleman-Wunsch-Algorithmus
//TODO Einleitung DNA / Sequenzanalyse / String Matching
Problemstellung
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.

M A E H T E 
A E H R E N



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

M A E H T E _
  | | |   |
_ A E H R E N



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.

match = 3 
mismatch = 0 
gappenalty = -1 

Lösung
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:

$a_{0, 0} = 0 \\
{0, j} = a_{0, j-1}+gappenalty \\
{i, 0} = a_{i-1, 0}+gappenalty  \\
{i, j} = max(a_{i-1, j}+gappenalty, a_{i, j-1}+gappenalty, a_{i-1, j-1}+gappenalty)$



\text{für alle i in {1, ..., m-1}, j in {1, ..., n-1}}


Für das Beispiel ergibt sich folgende Matrix:




$
A
E
H
R
E
N




$
0
-1
-2
-3
-4
-5
-6




M
-1
0
-1
-2
-3
-4
-5




A
-2
2
1
0
-1
-2
-3




E
-3
1
5
4
3
2
1




H
-4
0
4
8
7
6
5




T
-5
-1
3
7
8
7
6




E
-6
-2
2
6
7
11
10





Die Zahl in der rechten unteren Ecke ist das Maß für die Ähnlichkeit der beiden Sequenzen. Das Alignment lässt sich konstruieren, indem man ausgehend vom rechten unteren Feld in die Richtung geht, aus der das Maximum kommt. Diese Felder sind in der Matrix fett gekennzeichnet. Wird nach links gegangen, entspricht das einer Einfügung in der Sequenz x. Wird nach oben gegangen, entspricht das einer Einfügung in die Sequenz y. Wird diagonal nach links oben gegangen, entspricht das einer Übereinstimmung, wenn der Wert des aktuellen Feldes und der Wert des linken oberen Nachbarfeldes sich um match unterscheidet und sonst einer Nichtübereinstimmung. So kommt das folgende Alignment zustande:
M A E H T E _
  | | |   |
_ A E H R E N


Aufwandsbetrachtung und Einsatzgebiete
Fazit