Was ist Dynamische Programmierung?
Methode des Algorithmenentwurfs, die ein Problem in kleinere Teilprobleme zerlegt und deren Lösungen zur Wiederverwendung in einer Tabelle festhält, um dieselbe Berechnung nicht mehrfach auszuführen. Sie wird unter anderem für das Rucksackproblem, das Wechselgeldproblem mit möglichst wenigen Münzen, die längste gemeinsame Teilfolge und kürzeste Wege eingesetzt.
Japanische Bezeichnung: 動的計画法
„Dynamische Programmierung“ kommt in 2 Übungsfragen aus 1 Themen vor, z. B. Datenstrukturen und Algorithmen.
Fachgebiet: Datenstrukturen und Algorithmen
Die Idee: jedes überlappende Teilproblem nur einmal lösen
Werden Fibonacci-Zahlen direkt nach fib(n) = fib(n−1) + fib(n−2) rekursiv berechnet, werden dieselben Werte immer wieder neu berechnet, und die Zahl der Aufrufe wächst exponentiell (etwa 2,69 Millionen für fib(30)). Die dynamische Programmierung hält die Lösung jedes Teilproblems fest, sobald sie gefunden ist, und schlägt sie danach nur noch nach, sodass fib(n) einen Aufwand proportional zu n erfordert. Sie ist anwendbar, wenn sich die optimale Lösung eines großen Problems aus optimalen Lösungen kleinerer Teilprobleme zusammensetzen lässt (optimale Teilstruktur) und dieselben Teilprobleme mehrfach auftreten (überlappende Teilprobleme).
Memoisation und das Füllen von Tabellen
Es gibt zwei Umsetzungsweisen: die Memoisation (Top-down), die die rekursive Form beibehält, sich aber berechnete Ergebnisse merkt, und den Bottom-up-Ansatz, der eine Tabelle beginnend bei den kleinsten Teilproblemen füllt. Beim 0/1-Rucksackproblem zum Beispiel enthält die Tabelle „den höchsten Wert, der mit den Gegenständen bis i innerhalb der Kapazität c erreichbar ist“, und sie wird gefüllt, indem jeweils das Größere aus Mitnehmen und Weglassen eines Gegenstands gewählt wird. Bei n Gegenständen und der Kapazität W kostet das O(nW). Das Problem der kleinsten Münzzahl lässt sich ebenso lösen, indem man für jeden Betrag von 0 bis zum Zielbetrag die kleinste Münzzahl tabelliert.
Unterschied zu Greedy-Algorithmen und Anwendungen
Ein Greedy-Algorithmus wählt einfach in jedem Moment die am besten erscheinende Möglichkeit und geht weiter; er ist daher schnell, bei manchen Problemen aber nicht optimal. Sollen 8 Yen mit Münzen zu 1, 4 und 6 Yen bezahlt werden, verwendet der Greedy-Algorithmus drei Münzen, 6 + 1 + 1, während die dynamische Programmierung zwei findet, 4 + 4. Die dynamische Programmierung ist weit verbreitet, etwa für die Editierdistanz und die längste gemeinsame Teilfolge von Zeichenketten (wie im Befehl diff), das Alignment von DNA-Sequenzen, den Viterbi-Algorithmus in der Spracherkennung und den Floyd-Warshall-Algorithmus für kürzeste Wege zwischen allen Knotenpaaren.
Häufige Fragen
Wie unterscheidet sich die dynamische Programmierung von Teile und herrsche?
Beide zerlegen ein Problem in Teilprobleme, doch bei Teile-und-herrsche-Algorithmen wie Mergesort überlappen sich die Teilprobleme nicht, daher müssen keine Lösungen festgehalten werden. Die dynamische Programmierung unterscheidet sich darin, dass sie Lösungen festhält und wiederverwendet, wenn dieselben Teilprobleme mehrfach auftreten.
Was sind die Schwächen der dynamischen Programmierung?
Sie braucht Speicher und Aufwand proportional zur Größe der Tabelle. Das O(nW) des Rucksackproblems ist proportional zum Wert der Kapazität W und wird daher unpraktikabel, wenn W sehr groß ist. Der Speicherbedarf lässt sich verringern, indem nur das Nötige festgehalten oder nur die vorherige Zeile der Tabelle aufbewahrt wird.