Kurs:Algorithmen und Datenstrukturen/Vorlesung/Dynamische Programmierung

Dynamische Programmierung

Auf dieser Seite wird die dynamische Programmierung behandelt.

Die dynamische Programmierung vereint die Ideen verschiedener Muster. Zum einen die Wahl der optimalen Teillösung des Greedy Musters und zum anderen die Rekursion und den Konfigurationsbaum aus Divide and Conquer und Backtracking. Die Unterschiede sind, dass Divide and Conquer unabhängige Teilprobleme löst und in der dynamischen Programmierung eine Optimierung von abhängigen Teilproblemen durchgeführt wird. Die dynamische Programmierung ist eine „bottom-up“-Realisierung der Backtracking-Strategie. Die Anwendungsbereiche sind die selben wie bei Greedy, jedoch wird dynamische Programmierung insbesondere dort angewandt, wo Greedy nur suboptimale Lösungen liefert.

Idee

Bei der dynamischen Programmierung werden kleinere Teilprobleme zuerst gelöst, um aus diesen größere Teillösungen zusammenzusetzen. Das Problemlösen geschieht quasi auf Vorrat. Es werden möglichst nur die Teilprobleme gelöst, die bei der Lösung der großen Probleme auch tatsächlich benötigt werden. Wir erzielen einen Gewinn, wenn identische Teilprobleme in mehreren Lösungszweigen betrachtet werden. Rekursives Problemlösen wird ersetzt durch Iteration und abgespeicherte Teilergebnisse.

Nicht immer ist es überhaupt möglich, die Lösungen kleinerer Probleme so zu kombinieren, dass sich die Lösung eines größeren Problems ergibt. Die Anzahl der zu lösenden Probleme kann unvertretbar groß werden. Es können zu viele Teillösungen entstehen, die dann doch nicht benötigt werden oder der Gewinn der Wiederverwendung ist zu gering, da die Lösungszweige disjunkt sind.

Beispiel Editierdistanz

Gegeben sind zwei Zeichenketten s und t, was ist die minimale Anzahl an Einfüge-, Lösch- und Ersetzoperationen um s in t zu transformieren?

Als Beispiel entspricht s "Haus" und t "Maus". Die Lösung ist hier, dass "H" durch "M" ersetzt wird. Bei s= "Katze" und t="Glatze" wird "K" durch "G" ersetzt und "I" hinzugefügt. Die Editierdistanz kommt in der Rechtschreibprüfung und Plagiatserkennung zur Anwendung.

Formalisierung

Definition ( Ein-Schritt Modifikation)

Beachte $s=s_1...s_m$

1. Jedes $s^{\prime }=s_1...s_{i-1}{s}_{i+1}....s_m$ (für $i=1,...,m$)
2. Jedes $s^{\prime }=s_1...s_{i-1}x{s}_{i+1}....s_m$ (für $i=1,...,mundx!=s_i$)
3. Jedes $s^{\prime }=s_1...s_{i}x{s}_{i+1}....s_m$ (für $i=0,1,...,mundbel.x$)

heißt Ein-Schritt Modifikation von s.

Definition (k-Schritt Modifikation) Eine Zeichenkette t heißt k-Schritt Modifikation $(k>1)$ von s, wenn es Zeichenketten u gibt mit:

1. u ist eine Ein-Schritt Modifikation von s
2. t ist eine k-1-Schritt Modifikation von u

Definition (Editierdistanz, auch Levenshtein-Distanz) $D(s,t)=min\{d|sisteined-SchrittModifikationvont\}$

Ist s eine d-Schritt Modifikation von t, so ist auch s eine d+2j Modifikation von t für jedes j>0.Eine minimale Modifikation muss nicht eindeutig sein. Wir sind aber hier nur an dem Wert einer minimalen Modifikation interessiert.

Charakterisierung und Algorithmus

Die Idee ist, dass die Berechnung von D(s,t) auf die Berechnung von D auf die Präfixe von s und t zurückgeführt wird.

Definition $D_{ij}(s,t)$

Sei $s=s_1...s_{m}undt=t_1...t_n$

Definiere $D_{ij}(s,t)=D(s_1...s_i,t_1...t_j)(fueri=0,...,m,j=0,...,n)$

Beachte für z.B i=0 haben wir $s_1...s_i=ϵ$ (leerer String).

Wir beobachten, dass gilt $D_{mn}(s,t)=D(s,t)$. Dies ist nun zu berechnen. Zudem ist $D_{00}(s,t)=D(ϵ,ϵ)=0$, also sind zwei leere Strings identisch.

$D_{0j}(s,t)=D(ϵ,t)=j$ für j=1,..,n. Also alle Zeichen $t_1...t_j$ müssen eingefügt werden.

$D_{i0}(s,t)=D(s,ϵ)=i$ für i=1,...,m. Also alle Zeichen $s_1...s_i$ müssen eingefügt werden.

Theorem der zentralen Charakterisierung der Editierdistanz

Falls $s_i=t_j:D_{ij}(s,t)=D_{i-1,j-1}(s,t)$.

Ansonsten: $D_{ij}(s,t)=min:=\{\begin{array}{cc}{D}_{i-1,j-1}(s,t)+1& Ersetzung\\ D_{i,j-1}(s,t)+1& Einfuegung\\ D_{i-1,j}(s,t)+1& Loeschung\end{array}$

Algorithmus

For j=0,...,n set $D_{0j}$(s,t)=j
For i=0,...,m set $D_{i0}$(s,t)=i
For i=1,..,m
   For j=1,...,n
      If $s_i=t_j$ set $D_{ij}(s,t)=D_{i-1,j-1}(s,t)$
      else $D_{ij}(s,t)=$
         min {$D_{i-1,j-1}(s,t)+1,D_{i,j-1}(s,t)+1,D_{i-1,j}(s,t)+1$}
Return $D_{mn}(s,t)$

Analyse

Theorem

Für endliche Zeichenketten s und t terminiert der Algorithmus editdistance nach endlich vielen Schritten.

Beweis

Der Beweis folgt auf dem nächsten Theorem.

Theorem

Für die Eingaben $s=s_1...s_m$ und $t=t_1...t_n$ hat der Algorithmus eine Laufzeit von $\mathrm{\Theta }(mn)$.

Beweis

Der Beweis besteht aus einer einfachen Schleifenanalyse.

Theorem

Der Algorithmus editdistance berechnet die Editierdistanz zweier Zeichenketten s und t.

Beweis

Der Beweis folgt direkt aus der zentralen Charakterisierung der Editierdistanz.