Was ist dynamische Programmierung?

Wenn es um die Computerprogrammierung geht, ist die dynamische Programmierung so vielseitig wie mathematisch. Richard Bellman entwickelte die Technik in den 50er Jahren und hat seitdem in allen Bereichen, von der Luftfahrttechnik bis hin zur Wirtschaft, Anwendung gefunden.

In beiden Kontexten bezieht sich das Wort auf das Zerlegen eines komplizierten Themas in überschaubare Teile. Mehrjährige Entscheidungen brechen typischerweise rekursiv auseinander. In der Informatik hat ein Problem eine optimale Unterstruktur, wenn es optimal angegangen werden kann, indem es in Teilprobleme zerlegt und rekursiv die besten Lösungen gefunden werden.

Es besteht eine Beziehung zwischen dem Wert des Hauptproblems und den Werten der Teilprobleme, wenn die Teilprobleme rekursiv innerhalb des Hauptproblems verschachtelt werden können und dynamische Programmiertechniken verwendet werden können, um das Hauptproblem zu lösen. Im Bereich der Optimierung ist die Bellman-Gleichung eine bekannte Methode, um über diese spezielle Verbindung für eine bessere Strategie zu sprechen.

Sie können Software Engineering mit Hilfe von Online-Kursen lernen.

Mathematische Optimierung

Indem eine komplexe Auswahl in eine Reihe von inkrementellen Auswahlen zerlegt wird, wie dies bei der dynamischen Programmierung der Fall ist, kann ein mathematisches Optimierungsproblem für Operationen viel besser handhabbar gemacht werden. Um dies zu erreichen, definieren wir eine Reihe von Wertfunktionen V1, V2,…, Vn, die jeweils y als Argument nehmen, um den Zustand des Systems zu einem bestimmten Zeitpunkt I von 0 bis n zu beschreiben. Vn(y) ist der Wert zum Zeitpunkt n, der vom Zustand y erfasst wurde. Durch Verwendung einer rekursiven Verbindung, die als Bellman-Gleichung bekannt ist, können wir die Werte von Vi in früheren Perioden I = n1, n2,…, 2, 1 bestimmen Zeit I 1 und der Funktion Vi im neuen Zustand des Systems können wir Vi1 in jedem beliebigen Zustand y aus Vi ableiten, wobei I = 2,…, n. Diese Prozedur gibt Vi1 für die erforderlichen Zustände zurück, da Vi bereits für sie berechnet wurde. Und schließlich wird der optimale Lösungswert V1 in der Startbedingung des Systems gefunden. Durch Zurückverfolgen von Schritten aus früheren Berechnungen können die optimalen Werte der Auswahlvariablen einzeln abgerufen werden.

Damit die dynamische Programmierung sinnvoll ist, muss ein Problem zwei Eigenschaften aufweisen: eine optimale Unterstruktur und überlappende Unterprobleme. Der Begriff „teile und herrsche“ wird verwendet, um sich auf eine Technik zu beziehen, bei der eine Schwierigkeit in kleinere, unabhängige Probleme zerlegt und dann gelöst wird, indem die jeweils besten Antworten kombiniert werden. Aus diesem Grund betrachten wir Merge-Sort und Rapid-Sort nicht als dynamische Programmierschwierigkeiten.

Ein Software-Engineering-Zertifikatsprogramm kann Ihre Fähigkeiten verbessern.

Ein Optimierungsproblem mit optimaler Unterstruktur kann gelöst werden, indem die Lösungen seiner Unterprobleme kombiniert werden. Ideale Unterstrukturen werden üblicherweise durch Rekursion definiert. Jeder Zwischenknoten gewann den kürzesten Weg p von einem Knoten u zu einem Knoten v im Graphen G=(V,E) ist ein Beispiel für eine optimale Unterstruktur. Wenn der Pfad p der kürzeste ist, kann er in zwei Pfade unterteilt werden, p1 von u nach w und p2 von w nach v, die auch die kürzesten zwischen ihren jeweiligen Scheitelpunktpaaren sind. Daher verwenden die Bellman-Ford- und Floyd-Warshall-Algorithmen Rekursion, um die kürzesten Pfade zu finden.

Was ist die Logik hinter der Verwendung einer dynamischen Programmiermethode?

Der Ablauf der dynamischen Programmierung ist wie folgt:

1. Dabei reduziert es die Komplexität aller Aspekte des ursprünglichen Themas.
2. Um diese kleineren Probleme zu lösen, ermittelt es die bestmögliche Antwort.
3. Es verfolgt Lösungen für kleinere Herausforderungen (Memoisierung). Auswendiglernen ist der Akt des Erinnerns an die Lösungen kleinerer Probleme.
4. Es recycelt sie so, dass derselbe Teil des Problems mehrmals gelöst werden kann.
5. Nach all dem müssen Sie die Antwort auf das schwierige Problem finden.

1. Optimale Teilstrukturen und Probleme mit überlappenden Teilproblemen. In diesem Zusammenhang bezieht sich der Begriff „optimale Unterstruktur” auf ein Verfahren, durch das Optimierungsprobleme gelöst werden können, indem die besten Lösungen in ihre konstituierenden Unterprobleme integriert werden.
2. Da Zwischenergebnisse gespeichert werden müssen, steigt die räumliche Komplexität der dynamischen Programmierung sogar mit sinkender zeitlicher Komplexität.