Dynamische Programmierung
Dynamische Programmierung (DP; englisch dynamic programming, DP) ist eine Methode zur Lösung komplexer Optimierungsprobleme, die auf der Zerlegung des ursprünglichen Problems in eine Folge einfacherer Teilprobleme basiert[1][2]. Die Methode wird auf mehrstufige Entscheidungsprozesse angewendet, bei denen die optimale Lösung des Gesamtproblems aus den optimalen Lösungen seiner Teilprobleme konstruiert werden kann.
Der Begriff wurde in den 1950er Jahren von dem amerikanischen Mathematiker Richard Bellman eingeführt[3]. In diesem Kontext wird das Wort „Programmierung“ im Sinne von „Planung“ oder „Erstellung eines optimalen Handlungsplans“ verwendet, nicht im Sinne des Schreibens von Computercode[4].
Schlüsseleigenschaften und Theoreme
Die Anwendbarkeit der dynamischen Programmierung auf ein Problem wird durch das Vorhandensein von zwei fundamentalen Eigenschaften bestimmt.
Bellmansches Optimalitätsprinzip
Das zentrale Konzept der Methode ist das Bellmansche Optimalitätsprinzip (englisch Bellman's principle of optimality). Es besagt: Unabhängig vom Ausgangszustand und der ersten Entscheidung müssen die nachfolgenden Entscheidungen eine optimale Strategie in Bezug auf den Zustand bilden, der sich aus der ersten Entscheidung ergibt[3].
Mit anderen Worten, jeder Teil einer optimalen Trajektorie ist für sich genommen optimal. Diese Eigenschaft ermöglicht es, das Gesamtproblem in eine Folge einfacherer Teilprobleme zu zerlegen und diese rekursiv zu lösen.
Überlappende Teilprobleme
Ein Problem besitzt die Eigenschaft überlappender Teilprobleme (englisch overlapping subproblems), wenn bei seiner rekursiven Lösung dieselben Teilprobleme mehrfach auftreten. DP vermeidet wiederholte Berechnungen, indem es die Lösungen bereits gelöster Teilprobleme speichert (diese Technik wird Memoisation oder Tabulierung genannt), was die Effizienz im Vergleich zu einer naiven rekursiven Suche erheblich steigert.
Bellman-Gleichung
Aus dem Optimalitätsprinzip leitet sich die grundlegende Rekurrenzrelation der Methode ab – die Bellman-Gleichung[1]. Sie verknüpft den „Wert“ (optimaler Gewinn oder optimale Kosten) des aktuellen Zustands mit den Werten der nachfolgenden Zustände. Für einen deterministischen, mehrstufigen Prozess mit einer additiven Zielfunktion lautet sie in allgemeiner Form:
wobei:
- – die Schrittnummer (von bis 1);
- – der Zustand des Systems im Schritt ;
- – die steuerbare Entscheidung, die im Schritt getroffen wird;
- – der Gewinn (oder die Kosten) im k-ten Schritt;
- – die Funktion, die den neuen Zustand des Systems definiert;
- – der optimale Wert der Zielfunktion für das Teilproblem, das im Schritt im Zustand beginnt.
Die Gleichung wird in der Regel sequenziell „rückwärts“ gelöst, indem man vom letzten zum ersten Schritt fortschreitet.
Anwendungsbeispiele
- Problem des kürzesten Weges in einem Graphen: Dieses Problem besitzt die Eigenschaft der optimalen Unterstruktur, da jeder Teilabschnitt eines kürzesten Weges selbst ein kürzester Weg ist. Die Algorithmen von Bellman-Ford und Floyd-Warshall sind klassische Beispiele für die Anwendung von DP zur Lösung dieses Problems[5].
- Rucksackproblem: Das Problem der optimalen Befüllung eines Rucksacks mit begrenzter Kapazität mit Gegenständen, die unterschiedlichen Wert und Gewicht haben. DP löst dieses Problem, indem es die Gegenstände nacheinander betrachtet und bei jedem Schritt den maximalen Wert für alle möglichen verbleibenden Kapazitäten berechnet.
- Ressourcenallokationsproblem: Die Verteilung einer begrenzten Ressource (z. B. Investitionen) auf mehrere Projekte, um den Gesamtertrag zu maximieren.
Einschränkungen
Die Haupteinschränkung der Methode ist der Fluch der Dimensionalität (englisch curse of dimensionality) – ein von Bellman eingeführter Begriff, der das exponentielle Wachstum der Anzahl von Zuständen und folglich der Rechenkomplexität bei Zunahme der Anzahl von Variablen, die den Systemzustand beschreiben, bezeichnet[6][7]. Dies schränkt die praktische Anwendung der exakten DP auf Probleme mit sehr hoher Dimensionalität ein.
Verwandte Konzepte
- Operations Research
- Theorie der optimalen Steuerung
- Markow-Entscheidungsprozess (stochastische Verallgemeinerung)
- Hamilton-Jacobi-Bellman-Gleichung (Analogon für kontinuierliche Zeit)
Einzelnachweise
- ↑ 1.0 1.1 "Dynamische Programmierung". Große Russische Enzyklopädie. [1]
- ↑ "Dynamische Programmierung". Wikipedia. [2]
- ↑ 3.0 3.1 Reschetnikow A. N., Kotschenkow A. W., Pirow D. M., Rjabokon D. A. (2011). Dynamische Programmierung. Anwendungsbeispiele. Lehrbuch, Lobatschewski-Universität Nischni Nowgorod (WMiK). [3]
- ↑ "Dynamic programming". Wikipedia. [4]
- ↑ Bradley S. P., Hax A. C., Magnanti T. L. (1977). Applied Mathematical Programming. Addison-Wesley. [5]
- ↑ "Fluch der Dimensionalität". Wikipedia. [6]
- ↑ Jensen P. A. (2004). Dynamic Programming – Models. Operations Research Models and Methods, Univ. of Texas. [7]