Kurs:Algorithmen und Datenstrukturen/Vorlesung/Dynamische Programmierung




Dynamische Programmierung

Bearbeiten

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.

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

Bearbeiten

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

Bearbeiten

Definition ( Ein-Schritt Modifikation)

Beachte  

  1. Jedes   (für  )
  2. Jedes   (für  )
  3. Jedes   (für  )

heißt Ein-Schritt Modifikation von s.

Definition (k-Schritt Modifikation) Eine Zeichenkette t heißt k-Schritt Modifikation   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)  

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

Bearbeiten

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  

Sei  

Definiere  

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

Wir beobachten, dass gilt  . Dies ist nun zu berechnen. Zudem ist  , also sind zwei leere Strings identisch.

  für j=1,..,n. Also alle Zeichen   müssen eingefügt werden.

  für i=1,...,m. Also alle Zeichen   müssen eingefügt werden.

Theorem der zentralen Charakterisierung der Editierdistanz

Bearbeiten

Falls  .

Ansonsten:  

Algorithmus

Bearbeiten
For j=0,...,n set  (s,t)=j
For i=0,...,m set  (s,t)=i
For i=1,..,m
   For j=1,...,n
      If   set  
      else  
         min { }
Return  

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   und   hat der Algorithmus eine Laufzeit von  .

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.