Das dynamische Programmierung ist ein Algorithmusmodell, das ein komplexes Problem löst, indem es in Teilprobleme unterteilt und deren Ergebnisse gespeichert werden, um zu vermeiden, dass diese Ergebnisse neu berechnet werden müssen.
Dieser Zeitplan wird verwendet, wenn Sie Probleme haben, die in ähnliche Teilprobleme unterteilt werden können, damit deren Ergebnisse wiederverwendet werden können. Diese Programmierung wird größtenteils zur Optimierung verwendet.
Vor dem Lösen des verfügbaren Teilproblems versucht der dynamische Algorithmus, die Ergebnisse der zuvor gelösten Teilprobleme zu untersuchen. Teilproblemlösungen werden kombiniert, um die beste Lösung zu erzielen.
Anstatt immer wieder dasselbe Teilproblem zu berechnen, können Sie Ihre Lösung in einem Speicher speichern, wenn Sie zum ersten Mal auf dieses Teilproblem stoßen. Wenn es während der Lösung eines anderen Teilproblems erneut angezeigt wird, wird die bereits im Speicher gespeicherte Lösung übernommen.
Dies ist eine wunderbare Idee, um die Speicherzeit zu korrigieren. Durch die Verwendung von zusätzlichem Speicherplatz können Sie die Zeit verbessern, die für die Suche nach einer Lösung erforderlich ist..
Artikelverzeichnis
Mit den folgenden wesentlichen Merkmalen müssen Sie ein Problem haben, bevor die dynamische Programmierung angewendet werden kann:
Diese Eigenschaft drückt aus, dass ein Optimierungsproblem gelöst werden kann, indem die optimalen Lösungen der sekundären Probleme, aus denen es besteht, kombiniert werden. Diese optimalen Unterstrukturen werden durch Rekursion beschrieben.
In einem Diagramm wird beispielsweise eine optimale Unterstruktur auf dem kürzesten Weg r dargestellt, der von einem Scheitelpunkt s zu einem Scheitelpunkt t führt:
Das heißt, auf diesem kürzesten Weg kann jeder Zwischenscheitelpunkt i genommen werden. Wenn r wirklich die kürzeste Route ist, kann sie in die Unterrouten r1 (von s nach i) und r2 (von i nach t) unterteilt werden, so dass dies wiederum die kürzesten Routen zwischen den entsprechenden Eckpunkten sind.
Um die kürzesten Wege zu finden, kann die Lösung daher leicht rekursiv formuliert werden, wie es der Floyd-Warshall-Algorithmus tut..
Der Teilproblemraum muss klein sein. Das heißt, jeder rekursive Algorithmus, der ein Problem löst, muss immer wieder dieselben Teilprobleme lösen, anstatt neue Teilprobleme zu generieren..
Um beispielsweise die Fibonacci-Reihe zu erzeugen, kann diese rekursive Formulierung betrachtet werden: Fn = F (n-1) + F (n-2), wobei F1 = F2 = 1 zugrunde gelegt wird. Dann haben wir: F33 = F32 + F31 und F32 = F31 + F30.
Wie Sie sehen können, wird F31 in die rekursiven Teilbäume von F33 und F32 aufgelöst. Obwohl die Gesamtzahl der Teilprobleme sehr gering ist, werden Sie bei einer solchen rekursiven Lösung immer wieder dieselben Probleme lösen..
Dies wird bei der dynamischen Programmierung berücksichtigt, sodass jedes Teilproblem nur einmal gelöst wird. Dies kann auf zwei Arten erreicht werden:
Wenn die Lösung eines Problems unter Verwendung der Lösung seiner Teilprobleme rekursiv formuliert werden kann und sich diese Teilprobleme überschneiden, können die Lösungen für die Teilprobleme leicht gespeichert oder in einer Tabelle gespeichert werden.
Jedes Mal, wenn nach einer neuen Teilproblemlösung gesucht wird, wird die Tabelle überprüft, um festzustellen, ob sie zuvor gelöst wurde. Wenn eine Lösung gespeichert ist, wird sie verwendet, anstatt sie erneut zu berechnen. Andernfalls wird das Teilproblem gelöst und die Lösung in der Tabelle gespeichert.
Nachdem die Lösung eines Problems rekursiv in Bezug auf seine Teilprobleme formuliert wurde, wird es möglich sein, das Problem in aufsteigender Weise neu zu formulieren: Zuerst werden wir versuchen, die Teilprobleme zu lösen und ihre Lösungen zu verwenden, um Lösungen für die größeren Teilprobleme zu finden.
Dies erfolgt im Allgemeinen auch in Tabellenform, wobei iterativ Lösungen für immer größere Teilprobleme generiert werden, indem Lösungen für kleinere Teilprobleme verwendet werden. Wenn beispielsweise die Werte von F31 und F30 bereits bekannt sind, kann der Wert von F32 direkt berechnet werden.
Ein wesentliches Merkmal eines Problems, das dynamisch gelöst werden kann, ist, dass sich Teilprobleme überlappen sollten. Dies unterscheidet die dynamische Programmierung von der Divide- und Conquer-Technik, bei der es nicht erforderlich ist, die einfachsten Werte zu speichern.
Es ist ähnlich wie bei der Rekursion, da bei der Berechnung der Basisfälle der Endwert induktiv bestimmt werden kann. Dieser Bottom-up-Ansatz funktioniert gut, wenn ein neuer Wert nur von zuvor berechneten Werten abhängt.
Für jede positive ganze Zahl "e" kann einer der folgenden drei Schritte ausgeführt werden.
- Subtrahieren Sie 1 von der Zahl. (e = e-1).
- Wenn es durch 2 teilbar ist, dividiere durch 2 (wenn e% 2 == 0, dann ist e = e / 2).
- Wenn es durch 3 teilbar ist, dividiere durch 3 (wenn e% 3 == 0, dann ist e = e / 3).
Basierend auf den obigen Schritten muss die Mindestanzahl dieser Schritte gefunden werden, um e auf 1 zu bringen. Zum Beispiel:
- Wenn e = 1, Ergebnis: 0.
- Wenn e = 4, Ergebnis: 2 (4/2 = 2/2 = 1).
- Wenn e = 7, Ergebnis: 3 (7-1 = 6/3 = 2/2 = 1).
Man könnte daran denken, immer den Schritt zu wählen, der n so niedrig wie möglich macht, und so fortzufahren, bis er 1 erreicht. Es ist jedoch ersichtlich, dass diese Strategie hier nicht funktioniert..
Wenn zum Beispiel e = 10 ist, wären die Schritte: 10/2 = 5-1 = 4/2 = 2/2 = 1 (4 Schritte). Die optimale Form ist jedoch: 10-1 = 9/3 = 3/3 = 1 (3 Schritte). Daher sollten alle möglichen Schritte, die für jeden gefundenen Wert von n ausgeführt werden können, ausprobiert werden, wobei die Mindestanzahl dieser Möglichkeiten ausgewählt wird.
Alles beginnt mit einer Rekursion: F (e) = 1 + min F (e-1), F (e / 2), F (e / 3), wenn e> 1, wobei als Basisfall gilt: F (1) = 0. Mit der Wiederholungsgleichung können wir mit der Codierung der Rekursion beginnen.
Es ist jedoch ersichtlich, dass es überlappende Teilprobleme gibt. Darüber hinaus hängt die optimale Lösung für eine bestimmte Eingabe von der optimalen Lösung ihrer Teilprobleme ab.
Wie beim Auswendiglernen, wo die Lösungen der gelösten Teilprobleme zur späteren Verwendung gespeichert werden. Oder wie bei der dynamischen Programmierung beginnen Sie ganz unten und arbeiten sich bis zum angegebenen e vor. Dann beide Codes:
Einer der Hauptvorteile der dynamischen Programmierung besteht darin, dass die Verarbeitung beschleunigt wird, da zuvor berechnete Referenzen verwendet werden. Da es sich um eine rekursive Programmiertechnik handelt, werden die Codezeilen des Programms reduziert.
Gierige Algorithmen ähneln der dynamischen Programmierung, da sie beide Werkzeuge zur Optimierung sind. Der Greedy-Algorithmus sucht jedoch bei jedem lokalen Schritt nach einer optimalen Lösung. Das heißt, es sucht eine gierige Wahl in der Hoffnung, ein globales Optimum zu finden..
Gierige Algorithmen können daher eine Annahme treffen, die zu diesem Zeitpunkt optimal aussieht, aber in Zukunft teuer wird und kein globales Optimum garantiert..
Andererseits findet die dynamische Programmierung die optimale Lösung für die Teilprobleme und trifft dann eine fundierte Wahl, indem sie die Ergebnisse dieser Teilprobleme kombiniert, um tatsächlich die optimalste Lösung zu finden..
- Es wird viel Speicher benötigt, um das berechnete Ergebnis jedes Teilproblems zu speichern, und es kann nicht garantiert werden, dass der gespeicherte Wert verwendet wird oder nicht.
- Oft wird der Ausgabewert gespeichert, ohne jemals in den folgenden Unterproblemen während der Ausführung verwendet zu werden. Dies führt zu einer unnötigen Speichernutzung.
- In der dynamischen Programmierung werden Funktionen rekursiv aufgerufen. Dadurch steigt der Stapelspeicher ständig an.
Wenn Sie nur über begrenzten Speicher verfügen, um Ihren Code auszuführen, und die Verarbeitungsgeschwindigkeit keine Rolle spielt, können Sie die Rekursion verwenden. Wenn Sie beispielsweise eine mobile Anwendung entwickeln, ist der Speicher für die Ausführung der Anwendung sehr begrenzt.
Wenn Sie möchten, dass das Programm schneller ausgeführt wird und Sie keine Speicherbeschränkungen haben, ist die dynamische Programmierung vorzuziehen.
Dynamische Programmierung ist eine effektive Methode zur Lösung von Problemen, die ansonsten in angemessener Zeit äußerst schwierig zu lösen wären..
Algorithmen, die auf dem dynamischen Programmierparadigma basieren, werden in vielen Bereichen der Wissenschaft verwendet, einschließlich vieler Beispiele in der künstlichen Intelligenz, von der Planung der Problemlösung bis zur Spracherkennung..
Dynamische Programmierung ist sehr effektiv und funktioniert sehr gut für eine Vielzahl von Problemen. Viele Algorithmen können als gierige Algorithmusanwendungen angesehen werden, wie zum Beispiel:
- Fibonacci-Zahlenreihen.
- Hanoi Türme.
- Alle kürzesten Routenpaare von Floyd-Warshall.
- Rucksackproblem.
- Projektplanung.
- Der kürzeste Weg durch Dijkstra.
- Flugsteuerung und Robotiksteuerung.
- Mathematische Optimierungsprobleme.
- Timesharing - Planen Sie den Job, um die CPU-Auslastung zu maximieren.
Fibonacci-Zahlen sind die Zahlen, die in der folgenden Reihenfolge gefunden werden: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 usw..
In der mathematischen Terminologie wird die Folge Fn von Fibonacci-Zahlen durch die Wiederholungsformel definiert: F (n) = F (n - 1) + F (n - 2), wobei F (0) = 0 und F (1) = 1.
In diesem Beispiel wird ein Sucharray mit allen Anfangswerten mit -1 initialisiert. Wann immer die Lösung eines Teilproblems benötigt wird, wird diese Suchmatrix zuerst durchsucht.
Wenn der berechnete Wert vorhanden ist, wird dieser Wert zurückgegeben. Andernfalls wird das Ergebnis so berechnet, dass es im Sucharray gespeichert wird, damit es später wiederverwendet werden kann.
In diesem Fall wird für dieselbe Fibonacci-Reihe zuerst f (0) berechnet, dann f (1), f (2), f (3) und so weiter. Somit werden die Lösungen der Teilprobleme von unten nach oben konstruiert.
Bisher hat noch niemand einen Kommentar zu diesem Artikel abgegeben.