Dynamisches Programmieren WS13-14
Inhaltsverzeichnis |
Autoren
Einführung
Das Prinzip "Teile und Herrsche" dient als Grundlage für viele Algorithmen: Um ein umfangreiches Problem zu lösen, zerlegt man es in kleinere Teilprobleme, die unabhängig voneinander gelöst werden können. In der dynamischen Programmierung wird dieses Prinzip aufgegriffen und weiterentwickelt. Wissen wir nicht genau welche kleineren Probleme zu lösen sind, berechnen wir all diese Teilprobleme und speichern die Ergebnisse zur Verwendung bei der Lösung größerer Probleme, in einer Tabelle. Der Begriff "Programmieren" bezieht sich hierbei eher auf das Formulieren von Problemstellungen und das erstellen einer Tabelle. Deshalb wird oftmals auch von "Dynamischer Optimierung" gesprochen.
Bei der Anwendung der dynamischen Programmierung können immer folgende Probleme auftreten:
- Es ist nicht immer möglich, die Lösungen kleinerer Probleme so zu kombinieren, dass sich die optimale Lösung eines größeren Problems ergibt.
- Die Anzahl der zu lösenden Teilprobleme kann unvertretbar groß werden.
Vorgehensweise
Die Entwicklung eines dynamischen Programms kann in vier Schritte unterteilt werden:
- Charakterisierung der Struktur eines Programms.
- Definieren des Wertes einer optimalen Lösung rekursiv.
- Berechnung des Wertes einer optimalen Lösung durch den bottom-up-Ansatz.
- Konstruktion einer zugehörigen optimalen Lösung aus den schon berechneten Daten.