Dynamische Programmierung

Hier lernst du, wie man dynamische Programmierung (DP) zum Entwurf effizienter Algorithmen einsetzen kann. Lies für die Grundlagen zuerst den Wikipedia-Artikel zur dynamischen Programmierung. Kern der dynamischen Programmierung ist das Wiederverwenden bekannter Teilergebnisse. Wir setzen uns mit dynamischer Programmierung in den folgenden vier Schritten auseinander.

1. Beispiel: Fibonacci-Zahlen;
2. Problem: Wegfindung;
3. Lösung: Wegfindung;
4. Übung: Längste gemeinsame Teilsequenz.

Am Beispiel der Fibonacci-Zahlen lernen wir das Grundprinzip kennen. Danach wird ein 2-dimensionales Beispiel zuerst als Problem geschildert und dann mittels dynamischer Programmierung gelöst. Schließlich gibt es eine Aufgabe, bei der du selbst einen Algorithmus entwickeln musst.

Unser erstes Beispiel ist die Berechnung von Fibonacci-Zahlen. Die Folge der Fibonacci-Zahlen \((f_i)_{i \in \mathbb{N}}\) ist definiert durch die Setzung der Anfangsglieder $$ f_0 = 0 \mbox{ und } f_1 = 1 $$ sowie der Rekursionsgleichung $$ \forall i: f_{i+2} = f_i + f_{i+1}. $$

Das Berechnen von Fibonacci-Zahlen kann man dann auch sehr einfach als rekursives Programm wie folgt gestalten.

function fibonacci(n) {
  if n = 0 return 0;
  if n = 1 return 1;
  return fibonacci(n-2) + fibonacci(n-1);
 }

Dieses Programm berechnet natürlich korrekt die Fibonacci-Zahlen. Es hat allerdings einen Nachteil: Die Laufzeit wächst exponentiell mit \(n\). Woran liegt das? Schauen wir uns die Berechnung von \(f_4\) einmal genauer an. Welche rekursiven Aufrufe gibt es? Wir kürzen den Funktionsnamen mit f ab. Ein Klick auf einen Funktionsaufruf expandiert diesen, wir sehen dann die resultierenden Folgeaufrufe.

Es reichen 4 Klicks (Expansionen), insgesamt gibt es 9 Funktionsaufrufe. Jetzt schauen wir uns auch nochmal \(f_5\) an.

Inzwischen brauchen wir 7 Klicks (Expansionen), insgesamt gibt es 15 Funktionsaufrufe; damit hat sich die Anzahl der Klicks fast verdoppelt! Dabei sehen wir jetzt schon, dass zum Beispiel \(f(2)\) insgesamt dreimal ausgewertet wurde, jeweils natürlich mit dem gleichen Ergebnis. Wenn wir den Algorithmus für größere \(n\) laufen lassen, so wird sich die Anzahl der Berechnungen von \(f(2)\) immer weiter erhöhen. Tatsächlich hat das obige Programm exponentielle Laufzeit.

Dieses Immer-wieder-neu-Berechnen ist unnötig vergeudete Rechenzeit, und hier kommt das dynamische Programmieren ins Spiel: Wir merken uns all diese Zwischenergebnisse in einem Array und greifen bei Bedarf darauf zurück. Ein solches dynamisches Programm könnte dann wie folgt aussehen.

function fibonacciDP(n) {
  a = new Array(n+1);
  a[0] = 0;
  a[1] = 1;
  for(i = 0 to n-2) {
    a[i+2] = a[i] + a[i+1];
  }
  return a[n];
 }

Dieses Programm hat nun nur noch lineare Laufzeit, dank der Benutzung des Arrays zum Zwischenspeichern.

Jetzt kommen wir zu einer anderen Anwendung, wo das Zwischenspeichern etwas versteckter ist. Außerdem benutzen wir nun keine lineare Tabelle (Array) mehr, sondern eine quadratische (Matrix).

Stellen wir uns vor, wir hätten ein Raster gegeben. Wir starten in der oberen linken Ecke und wollen nach unten rechts. Dabei dürfen wir bei jedem Schritt entweder ein Feld nach rechts gehen oder einen Schritt nach unten. Jeder Schritt kostet uns so viel wie auf dem Feld angegeben. Wir starten also im blauen Feld und wollen zum roten.

Eine Möglichkeit, einen Pfad zu berechnen, wäre eine Greedy-Heuristik: Wir entscheiden uns jeweils für rechts oder unten je nachdem, welcher Schritt günstiger ist.

Die Gesamtkosten: $$ 3+7+9+4+2+1+2 = 28. $$ Geht das besser?

Die Gesamtkosten: $$ 3+10+3+1+3+1+2 = 23. $$ Wir nehmen früh ein teures Feld (10) in Kauf, damit wir dann viele günstige Felder bekommen.

Wir wenden uns jetzt der Frage zu, wie wir einen effizienten Algorithmus für dieses Problem entwickeln können, der immer den optimalen Weg findet. Das ist nicht so einfach, da es exponentiell viele verschiedene Wege gibt, die vom Start zum Ziel führen. Um die Methode der dynamischen Programmierung anzuwenden, brauchen wir Zwischenergebnisse, die wir uns merken können. Von der Problemstellung her sind jedoch keine solchen Zwischenergebnisse vorgesehen (im Gegensatz zu der Berechnung der Fibonacci-Zahlen). Deshalb definieren wir uns einfach unsere eigenen! Und darin steckt jetzt der Trick, denn man muss darauf kommen, welche Zwischenergebnisse nützlich wären.

Wir wählen bei uns das Folgende: Wir speichern uns für jede Zelle im Raster, wie teuer der günstigste Weg dorthin ist (man kann sich auch noch den genauen Weg merken, wenn man den später ausgeben möchte). Damit ist also unsere Merktabelle genauso groß wie das Raster selbst. Diese Tabelle kann man nun schrittweise füllen; die oberste Reihe und die linkeste Spalte sind einfach, weil es jeweils nur einen Weg (den direkten) gibt.

Wie man jetzt sehen kann, sind die beschrifteten Zellen nun mit der Länge des kürzesten Weges vom Ausgangspunkt zur Zelle beschriftet. Insbesondere ist der kürzeste Weg vom Ausgangspunkt zu sich selbst der leere Weg (Weg der Länge 0).

Jetzt können wir uns daran machen, auch die anderen Felder zu füllen. Fangen wir an mit dem Feld unter der 3. Der kürzeste Weg hierher nimmt entweder die 3 (von oben) oder die 15 (von links) und addiert dann die 7 für das neue Feld. Danach (aber erst danach!) können wir mit dem Feld unter der 13 genauso verfahren.

Genau auf diese Weise kann man nun auch den Rest der Matrix auffüllen. Und dafür ist die Matrix jetzt editierbar; fülle einfach alle Zellen auf.

Jetzt bist du an der Reihe, einen Algorithmus mittels dynamischer Programmierung zu erstellen. Wir betrachten das folgende Problem.

Dabei muss eine Teilfolge nicht zusammenhängend im Wort vorkommen. Zum Beispiel haben ananas und bananenmus als längste gemeinsame Teilfolge anans. Deine Aufgabe ist es nun, einen Algorithmus zu entwickeln, welcher dynamische Programmierung benutzt, um das Problem zu lösen. Tipp: Benutze eine 2-Dimensionale Tabelle wie im obigen Beispiel.

Wende den fertigen Algorithmus auf die folgenden beiden Wörter an (per Hand ausgeführt oder implementiert).

Falls du Hilfe beim Entwickeln des Algorithmus brauchst, kannst du dazu leicht eine Lösung per Google finden.

Was haben wir gelernt?

1. Dynamische Programmierung ist eine Technik, um effiziente Algorithmen zu erstellen.
2. Kern ist das Merken (Zwischenspeichern) von Teillösungen.
3. Zum Speichern benutzt man eine Tabelle, die je nach Bedarf 1- oder 2-dimensional sein kann oder sogar noch höhere Dimension hat.