Glossar · approach
Dynamic Programming
Die OR / Informatik-Technik zur Lösung mehrstufiger Entscheidungsprobleme durch rekursive Zerlegung in überlappende Teilprobleme mit gespeicherten Zwischenresultaten; eingeführt von Bellman (1957).
Dynamische ProgrammierungDynamic ProgrammingDPBellman DP
Dynamische Programmierung (DP) ist die von Richard Bellman in seinem Buch von 1957 (*Dynamic Programming*, Princeton University Press) eingeführte Technik zur Lösung mehrstufiger Entscheidungsprobleme; sie zerlegt ein Problem in überlappende Teilprobleme, speichert Zwischenresultate in einer Tabelle (Memoisation oder Tabulation) und löst rekursiv über die Bellman-Gleichung V(s) = max_a {r(s, a) + γ V(s')}. Das Rucksackproblem ist das kanonische DP-Beispiel — Bellman stellt den DP-Rahmen im Buch von 1957 anhand des Knapsack vor; die Zeitkomplexität O(N×W) ist **pseudo-polynomiell** (polynomiell im Wert von W, exponentiell in seiner Bit-Länge). Weitere kanonische Anwendungen: kürzeste Pfade (Bellman-Ford), Bestandsführung (Wagner-Whitin Lotgrößenbestimmung), Ausrüstungs-Ersatz (Bellman 1955), stochastische Entscheidungsprozesse (Markov Decision Process), Sequenz-Alignment (Needleman-Wunsch), Parsing (CYK), Matrixketten-Multiplikationsreihenfolge. DP gibt es in zwei Hauptklassen: **deterministische DP** (jede Stufe mit bekanntem Ausgang) und **stochastische DP** (jede Stufe mit probabilistischem Ausgang — Markov-Entscheidungsprozesse). Anwendbarkeit erfordert optimale Substruktur (Teiloptima setzen sich zum Gesamtoptimum zusammen) und überlappende Teilprobleme. Approximate Dynamic Programming (ADP) und Stochastic Dual Dynamic Programming (SDDP) erweitern DP auf große stochastische Probleme. Bellman 1957 + Bellman und Dreyfus 1962 + Bertsekas 1995 sind die kanonischen Referenzen.
Örnek
Das Investitionskomitee einer mittelständischen Holding löst per DP die optimale NPV-Teilmenge aus 80 Kandidatenprojekten unter 100M TRY Jahresbudget: N = 80, W = 100.000 (in Tausend-TRY-Einheiten), DP-Tabelle 80 × 100.000 = 8M Zellen, Sekunden auf moderner Hardware; der Gesamt-NPV ist 7% höher als die intuitive Reihung.