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 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 gibt. 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 & Kruskal 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:
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ß.
So würde die DP ihre Anwendung bei der Matrizenmultiplikation finden. Betrachten wir z.B. n Matrizen der Größe x (1 i n). Gesucht wird M= ... 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.