Dynamische Programmierung, Grundprinzipien

Zur Auswahl der optimalen Lösung bei der DurchführungProgrammieraufgaben müssen manchmal eine große Anzahl von Datenkombinationen durchlaufen, die den Speicher des Personalcomputers laden. Zu solchen Methoden gehört beispielsweise die Programmiermethode "Teile und herrsche". In diesem Fall sieht der Algorithmus die Trennung der Aufgabe in einzelne kleine Teilaufgaben vor. Diese Methode wird nur in Fällen verwendet, in denen die kleinen Teilaufgaben unabhängig voneinander sind. Um unnötige Arbeit für den Fall zu vermeiden, dass die Teilaufgaben voneinander abhängig sind, wird das von American R. Bellman in den 1950er Jahren vorgeschlagene dynamische Programmierverfahren verwendet.

Das Wesen der Methode

Die dynamische Programmierung besteht darin, die optimale Lösung eines n-dimensionalen Problems zu bestimmen und sie in n getrennte Schritte aufzuteilen. Jeder von ihnen ist eine Teilaufgabe in Bezug auf eine Variable.

Der Hauptvorteil dieses Ansatzes istzu bedenken, dass Entwickler an eindimensionalen Optimierungsaufgaben von Teilaufgaben anstelle des n-dimensionalen Problems beteiligt sind und die Lösung der Hauptaufgabe "von unten nach oben" gesammelt wird.

Es ist zweckmäßig, dynamisch zu verwendenProgrammierung in den Fällen, in denen die Teilaufgaben miteinander in Beziehung stehen, d.h. haben gemeinsame Module. Der Algorithmus liefert einmal eine Lösung für jeden der Teilaufgaben, und die Antworten werden in einer speziellen Tabelle gespeichert. Dies ermöglicht es, die Antwort nicht erneut zu berechnen, wenn eine ähnliche Teilaufgabe auftritt.

Die Aufgabe der dynamischen Programmierung löst sichdie Frage der Optimierung. Der Autor dieser Methode R. Bellman formulierte das Prinzip der Optimalität: Unabhängig vom Anfangszustand bei jedem Schritt und der Lösung, die bei diesem Schritt bestimmt wird, werden alle folgenden Punkte optimal in Bezug auf den Zustand gewählt, den das System am Ende des Schrittes einnimmt.

Die Methode verbessert die Leistung von Aufgaben, die durch die Suche nach Varianten oder Rekursionen gelöst werden.

Konstruktion des Algorithmus des Problems

Dynamische Programmierung setzt vorausdie Konstruktion eines Algorithmus für Probleme, bei denen die Aufgabe in zwei oder mehr Teilaufgaben aufgeteilt ist, so dass ihre Lösung aus der optimalen Lösung aller darin enthaltenen Teilaufgaben gebildet werden kann. Ferner wird es notwendig, eine Wiederholungsbeziehung zu schreiben und den optimalen Wert des Parameters für das Problem als Ganzes zu berechnen.

Manchmal müssen Sie sich im dritten Schritt zusätzliche Hilfsinformationen über den Fortschritt jeder Teilaufgabe merken. Dies wird umgekehrt genannt.

Anwendung der Methode

Die dynamische Programmierung wird verwendet, wenn zwei charakteristische Merkmale vorhanden sind:

• Optimalität für Teilaufgaben;
• Vorhandensein von überlappenden Teilaufgaben im Problem.

Lösung des Optimierungsproblems durch die MethodeBei der dynamischen Programmierung müssen Sie zuerst die Struktur der Lösung beschreiben. Das Problem ist optimal, wenn die Lösung des Problems aus den optimalen Lösungen seiner Teilaufgaben besteht. In diesem Fall ist es ratsam, dynamische Programmierung zu verwenden.

Die zweite Eigenschaft des Problems, essentiell für ein gegebenesMethode, eine kleine Anzahl von Teilaufgaben. Die rekursive Lösung des Problems verwendet dieselben überlappenden Teilaufgaben, deren Anzahl von der Größe der ursprünglichen Information abhängt. Die Antwort wird in einer speziellen Tabelle gespeichert, das Programm spart Zeit und verwendet diese Daten.

Die Verwendung von dynamischenProgrammierung, wenn in der Hauptsache Entscheidungen in Etappen getroffen werden müssen. Betrachten Sie zum Beispiel ein einfaches Beispiel für die Aufgabe, Geräte zu ersetzen und zu reparieren. Angenommen, in der Gießerei einer Reifenfabrik werden Reifen gleichzeitig in zwei verschiedenen Formen hergestellt. Für den Fall, dass eines der Formulare fehlschlägt, müssen Sie das Gerät zerlegen. Es ist klar, dass es manchmal vorteilhafter ist, die zweite Form zu ersetzen, um die Maschine im Fall nicht zu demontieren, und diese Form wird in der nächsten Stufe ineffizient sein. Darüber hinaus ist es einfacher, beide Arbeitsformen zu ersetzen, bevor sie zu versagen beginnen. Die Methode der dynamischen Programmierung bestimmt die beste Strategie in der Frage des Ersetzens solcher Formen unter Berücksichtigung aller Faktoren: der Vorteil der Fortsetzung der Operation von Formen, der Verlust von ungenutzten Maschinen, die Kosten von zurückgewiesenen Reifen und mehr.