Was ist dynamische Programmierung?

Dynamisches Programmieren beschreibt unter Bezugnahme auf das Gebiet der Informatik eine Gruppe ähnlicher Computeralgorithmen, die komplexe Probleme lösen sollen, indem das Problem in Mengen kleinerer Probleme zerlegt wird. Die dynamische Programmierung wurde erstmals von Richard Bellman in den 1950er Jahren entwickelt und beschäftigt sich mit Problemen, die sich entweder mit Teilproblemen oder mit optimalen Teilstrukturen überschneiden. Um zu verstehen, wie dynamische Programmierung funktioniert, ist es am besten, das Konzept hinter diesen beiden Begriffen zu verstehen.

Überlappende Teilprobleme beschreiben komplizierte Gleichungen, die, wenn sie in kleinere Mengen von Gleichungen zerlegt werden, Teile der kleineren Gleichungen mehrmals wiederverwenden, um eine Antwort zu erhalten. Beispielsweise kann eine mathematische Gleichung, die zur Berechnung aller möglichen Ergebnisse unter Verwendung eines Satzes von Zahlen aufgefordert wird, dasselbe Ergebnis mehrere Male berechnen, während andere Ergebnisse nur einmal berechnet werden. Dynamische Programmierung würde dieses Problem erkennen lassen, dass nach der ersten Berechnung des Ergebnisses dieses Ergebnis gespeichert und die Antwort später in die Gleichung eingefügt werden sollte, anstatt sie erneut zu berechnen. Bei langen komplexen Prozessen und Gleichungen spart dies Zeit und schafft eine schnellere Lösung mit weitaus weniger Schritten.

Optimale Unterstrukturen schaffen eine Lösung, indem sie die beste Antwort auf alle Unterprobleme finden und dann die beste Gesamtantwort erstellen. Nachdem ein komplexes Problem in kleinere Probleme zerlegt wurde, verwendet der Computer ein mathematisches System, um die beste Antwort für jedes Problem zu ermitteln. Es berechnet die Antwort auf das ursprüngliche Problem aus den kleineren Antworten. Bei diesem Prozess gibt es Mängel. Es gibt zwar die Lösung, die mathematisch am besten funktioniert, aber es kann sein, dass es je nach Art des Problems und in Bezug auf die reale Welt die beste Lösung im wirklichen Leben ist oder nicht.

Während einer dieser Operationen versucht der dynamische Programmieralgorithmus, den kürzesten Weg zur Lösung zu finden. Dies kann auf zwei Arten geschehen. Der Top-Down-Ansatz zerlegt die Gleichung in kleinere Gleichungen und verwendet die Antworten für diese Gleichungen bei Bedarf erneut. Der Bottom-Up-Ansatz versucht, den kleinsten mathematischen Wert nach der Aufschlüsselung der Gleichung zu lösen und arbeitet sich dann von dort zum größten hoch. Beide Ansätze sparen Zeit, aber die dynamische Programmierung funktioniert nur, wenn das ursprüngliche Problem in kleinere Gleichungen zerlegt werden kann, die zu einem bestimmten Zeitpunkt zur Lösung der Gleichung wiederverwendet werden.