Dynamic Programming

Dynamic Programming (dynamische Programmierung) ist eine algorithmische Technik, die komplexe Probleme löst, indem sie sie in überlappende Teilprobleme zerlegt und deren Lösungen speichert, um Redundanz zu vermeiden.

Richard Bellman prägte den Begriff in den 1950ern — der Name „Dynamic Programming" war bewusst gewählt, um mathematische Forschung vor seinem Pentagon-Arbeitgeber zu tarnen. Die Bellman-Gleichung, das Herzstück der Methode, ist heute fundamental für Reinforcement Learning.

Das Prinzip: Wenn ein Problem optimale Substruktur hat (die optimale Lösung enthält optimale Lösungen der Teilprobleme) und überlappende Teilprobleme (dieselben Teilprobleme werden mehrfach gelöst), kann Dynamic Programming die Lösung exponentiell beschleunigen.

In der KI: Die Bellman-Gleichung V(s) = max_a [R(s,a) + γ × V(s')] definiert den optimalen Wert eines Zustands im Reinforcement Learning. Q-Learning, Value Iteration und Policy Iteration sind Dynamic-Programming-Algorithmen. DQN (Deep Q-Network) approximiert die Bellman-Gleichung mit einem neuronalen Netz.

Weitere KI-Anwendungen: Viterbi-Algorithmus (der effizienteste Algorithmus für Hidden Markov Models, genutzt in Spracherkennung und NER). Sequenz-Alignment (Needleman-Wunsch, Smith-Waterman — fundamental in der Bioinformatik). CTC-Decoding (Connectionist Temporal Classification, genutzt in Spracherkennung).

Dynamic Programming ist einer der wenigen algorithmischen Ansätze, die sowohl in der klassischen Informatik als auch in der modernen KI zentrale Bedeutung haben.