next up previous contents
Next: DTW oder dynamic time Up: No Title Previous: Wechsel der Forschungsparadigmen

Dynamische Programmierung

Es existiert viel Literatur über dynamische Programmierung (weiter DP), zahlreiche Bücher, Veröffentlichungen und andere Diskurse, so daß ich mich an die Arbeit von Rabiner gif und Cormen beschränken werde.

Viele statistische Probleme können dadurch gelöst werden, daß man sie in Teilprobleme zerlegt und deren Lösungen in geeigneter Weise zusammenfügt. So eignet sich dynamische Programmierung zur Lösung solcher Probleme, bei denen es sehr viel weniger Teilprobleme als mögliche Zerlegungen gibtgif. In diesen Fällen ist es günstig, die gefundenen Teillösungen in einer Tabelle zu speichern und so sicherzustellen, daß jedes Teilproblem nur einmal gelöst wird. Nach Sankoff & Kruskalgif ist die dynamische Programmierung für Zuordnungsprobleme verschiedenster Art geeignet. Dazu gehören etwa der Vergleich des genetische Codes unterschiedlicher Arten von Lebewesen oder die Zuordnung eines elektroakustischen Sprachsignals zu einem geschriebenen Text (dynamic time warping).

Das Vorgehen bei der dynamische Programmierung kann man so beschreiben:

  1. Bestimme die zu einer optimalen Gesamtlösung führenden Zerlegungen der Eingabe.
  2. Definiere rekursiv den Wert der Zielfunktion für

  3. Berechne diese Werte für alle in Betracht kommenden Teilaufgaben und speichere sie ab.
  4. Bestimme eine optimale Gesamtlösung unter Rückgriff auf die vorher berechneten Werte für benutzte Teilaufgaben.

Bei der Verwendung müssen wir das häufig angesprochene Optimalitätsprinzip im Auge behalten, das besagt, daß in einer optimalen Folge von Entscheidungen bzw. Auswahlen auch jede Teilfolge optimal sein muß.gif

So würde die DP ihre Anwendung bei der Matrizenmultiplikation finden. Betrachten wir z.B. n Matrizen der Größe di-1 x di (1 i n). Gesucht wird M=M1 * ... * Mn mit minimaler Anzahl von Multiplikationen. Die Matrizenmultiplikation ist assoziativ, also das Produkt kann auf verschiedene Arten berechnet werden, und, was für dieses Beispiel wesentlich ist, man kann durch geschickte Klammerung die Anzahl der skalaren Multiplikationen senken.

Wir haben beispielsweise 4 Matrizen A:[13,5], B:[5,89], C:[89,3] und D:[3,34]:

M #M
A(B(CD)) 9078+15130+2210 = 26418
A((BC)D) 1335+510+2210 = 4055
(AB)(CD) 5785+9078+39338 = 54201
(A(BC))D 1335+195+1326 = 2856
((AB)C)D 5785+3471+1326 = 10582


Gemeinsame Sequenz der zweiten und vierten Zeile ist die Multiplikation von B & C, der dritten und fünften die Multiplikation von A & B.

Wie man sehen kann, ist die beste Klammerung ca. 19mal schneller zu berechnen als die schlechteste. Zu beachten sind Teilsequenzen, gemeinsame Teile des Problems, die bei jeder Zeile immer wieder auftauchen und die mit Hilfe einer Tabelle mit Zwischenergebnissen ersparen würden, bzw. den Rechenaufwand verringern können.


next up previous contents
Next: DTW oder dynamic time Up: No Title Previous: Wechsel der Forschungsparadigmen

Damir Culjat
Tue Feb 23 14:43:47 CET 1999