Dynamische Programmierung einfach erklärt

Dynamische Programmierung ist eine Methode für Optimierungsprobleme. Bei einem Optimierungsproblem suchst du die beste Lösung. Die Methode teilt das Problem in Teilprobleme auf und speichert Zwischenresultate systematisch.

Sie kann erfolgreich eingesetzt werden, wenn zwei Dinge zusammenkommen: Das Problem besteht aus vielen gleichartigen Teilproblemen. Und eine optimale Lösung des Problems setzt sich aus optimalen Lösungen der Teilprobleme zusammen. Das nennt man Optimalitätsprinzip von Bellman. Es gilt bei einigen Optimierungsproblemen, nicht bei allen.

Dann rechnest du zuerst die kleinsten Teilprobleme direkt aus und setzt daraus nächstgrößere zusammen, bis das ursprüngliche Problem gelöst ist. Einmal berechnete Teilergebnisse stehen in einer Tabelle. Kommt ein gleichartiges Teilproblem noch einmal vor, nutzt du die gespeicherte Lösung, statt sie neu zu berechnen. Das senkt die Laufzeit.

Die Fibonacci-Folge ist ein gutes Beispiel für Teilprobleme. Fₙ ist die n-te Fibonacci-Zahl. Die kleinsten Teilprobleme sind F₀ = 0 und F₁ = 1. Sie werden direkt festgelegt, ohne zu rechnen.

Alle weiteren Zahlen setzt du aus den beiden vorherigen zusammen: Fₙ = Fₙ₋₁ + Fₙ₋₂ für n ≥ 2. So entsteht aus kleineren Teilproblemen das nächstgrößere.

Was passiert, wenn man diese Regel direkt als rekursives Programm schreibt? Dann wird fib(4) zu fib(3) + fib(2), und fib(3) wird wieder zu fib(2) + fib(1). Die Berechnung von fib(2) kommt also doppelt vor. Bei größeren Zahlen nehmen solche Mehrfachberechnungen exponentiell zu, das heißt: Sie wachsen mit jedem größeren n immer schneller. Bei einer einfachen rekursiven Variante wären es für n = 43 über 1,4 Milliarden Aufrufe. Das wollen wir vermeiden: Jedes Teilergebnis soll nur einmal berechnet werden.

Es gibt zwei Wege, Mehrfachberechnungen zu vermeiden.

Weg 1: Memoisierung. Du speicherst die Rückgabewerte einer Funktion zwischen, statt sie neu zu berechnen. Anders als bei der dynamischen Programmierung bleibt dabei die grundlegende Vorgehensweise des Verfahrens erhalten: fib(n) ruft weiter fib(n − 1) und fib(n − 2) auf, schaut aber vorher im Speicher nach. In imperativen Programmiersprachen nutzt man dafür üblicherweise ein assoziatives Array, also einen Speicher, in dem zu jedem n der Wert abgelegt wird. Eine Funktion lässt sich nur memoisieren, wenn sie referenziell transparent ist: Bei gleichen Eingaben gibt sie immer dieselben Ausgaben zurück. Beim Fibonacci-Beispiel sinkt die Laufzeit auf O(n), falls sich Speicherreservierung und -initialisierung in O(n) vornehmen lassen. O(n) bedeutet: Die Laufzeit wächst etwa im gleichen Maß wie n.

Weg 2: Aufbauen ab den kleinsten Teilproblemen. Du berechnest zuerst die kleinen Fibonacci-Zahlen und baust daraus die größeren. Dafür reichen zwei Werte: der vorletzte und der letzte. In jedem Durchlauf bildest du daraus den neuen Wert (vorletzter + letzter) und schiebst beide weiter. Jede Berechnung geschieht nur einmal, deshalb ist die Laufzeit O(n). Kostspielige Rekursionen fallen weg.

Ein Greedy-Algorithmus (gieriger Algorithmus) wählt Schritt für Schritt den Folgezustand, der zum Zeitpunkt der Wahl das beste Ergebnis verspricht. Er ist oft schnell, löst viele Probleme aber nicht optimal.

Das hängt mit seinem Vorgehen zusammen: Er hat in jedem Schritt nur begrenzt Informationen, und einen ausgeführten Schritt nimmt er nicht mehr zurück. Was jetzt am besten aussieht, kann also später zu einer schlechteren Gesamtlösung führen. Die gefundene Lösung ist nicht notwendigerweise die global optimale, also die beste insgesamt. Oft ist sie nur ein lokales Optimum, also das Beste in der unmittelbaren Umgebung.

Bei der dynamischen Programmierung ist das Vorgehen anders: Sie berechnet optimale Lösungen der kleinsten Teilprobleme und setzt sie zu einer Lösung des nächstgrößeren Teilproblems zusammen. Ein Greedy-Algorithmus trifft dagegen nur die jeweils beste nächste Wahl.