DYNAMISCHE PROGRAMMIERUNG: EIGENSCHAFTEN, BEISPIEL, VOR- UND NACHTEILE - TECHNOLOGIE - 2025

Die dynamische Programmierung ist ein Modellalgorithmus, der ein komplexes Problem löst, indem er es in Teilprobleme unterteilt und die Ergebnisse speichert, um zu vermeiden, dass die 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. Dieser Zeitplan wird größtenteils zur Optimierung verwendet.

Dynamische Programmierung. Teilprobleme in der Fibonacci-Sequenz überlagert. Quelle: Wikimedia commons, de: Benutzer: Dcoatzee, verfolgt von Benutzer: Stannered / Public Domain

Vor dem Lösen des verfügbaren Teilproblems versucht der dynamische Algorithmus, die Ergebnisse der zuvor gelösten Teilprobleme zu untersuchen. Die Lösungen für die Teilprobleme 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 zum Fixieren der Speicherzeit, bei der durch die Verwendung von zusätzlichem Speicherplatz die für die Suche nach einer Lösung erforderliche Zeit verkürzt werden kann.

Merkmale der dynamischen Programmierung

Mit den folgenden wesentlichen Merkmalen müssen Sie ein Problem haben, bevor die dynamische Programmierung angewendet werden kann:

Optimale Unterkonstruktion

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.

Überlappende Teilprobleme

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, können wir diese rekursive Formulierung betrachten: Fn = F (n - 1) + F (n - 2), wobei als Basisfall F1 = F2 = 1 gilt. 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:

Top-Down-Ansatz

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.

Bottom-up-Ansatz

Nachdem die Lösung eines Problems rekursiv in Bezug auf seine Teilprobleme formuliert wurde, kann versucht werden, das Problem in aufsteigender Weise neu zu formulieren: Zunächst 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.

Vergleich mit anderen Techniken

Ein wesentliches Merkmal eines Problems, das durch dynamische Programmierung gelöst werden kann, ist, dass sich Teilprobleme überlappen sollten. Dies unterscheidet die dynamische Programmierung von der Divide- und Conquer-Technik, bei der nicht die einfachsten Werte gespeichert werden müssen.

Dies ähnelt 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.

Beispiel

Mindestschritte bis 1

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, wird es durch 2 geteilt (wenn e% 2 == 0, dann ist e = e / 2).

- Wenn es durch 3 teilbar ist, wird es durch 3 geteilt (wenn e% 3 == 0 ist, dann ist e = e / 3).

Basierend auf den obigen Schritten sollte 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).

Fokus

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 müssen 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 genommen wird: F (1) = 0. Mit der Wiederholungsgleichung können Sie beginnen, die Rekursion zu codieren.

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:

Auswendiglernen

Dynamische Bottom-Up-Programmierung

Vorteil

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 im Programm reduziert.

Unersättliche Algorithmen gegen dynamische Programmierung

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.

Nachteile

- Es wird viel Speicher benötigt, um das berechnete Ergebnis jedes Teilproblems zu speichern, ohne garantieren zu können, 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.

Rekursion vs dynamische Programmierung

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 keine Speicherbeschränkungen aufweist, ist die dynamische Programmierung vorzuziehen.

Anwendungen

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.

Algorithmen basierend auf dynamischer Programmierung

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.

- Türme von Hanoi.

- Alle Paare kürzerer Routen durch Floyd-Warshall.

- Rucksackproblem.

- Projektplanung.

- Der kürzeste Weg durch Dijkstra.

- Flugsteuerung und Robotiksteuerung.

- Mathematische Optimierungsprobleme.

- Timeshare: Planen Sie den Job, um die CPU-Auslastung zu maximieren.

Fibonacci-Zahlenreihe

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.

Top-Down-Ansatz

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.

Bottom-up-Ansatz

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.

Verweise

1. Vineet Choudhary (2020). Einführung in die dynamische Programmierung. Developer Insider. Entnommen aus: developerinsider.co.
2. Alex Allain (2020). Dynamische Programmierung in C ++. C Programmierung. Entnommen aus: cprogramming.com.
3. Nach der Akademie (2020). Idee der dynamischen Programmierung. Entnommen aus: afteracademy.com.
4. Aniruddha Chaudhari (2019). Dynamische Programmierung und Rekursion - Unterschied, Vorteile mit Beispiel. CSE-Stapel. Entnommen aus: csestack.org.
5. Code Chef (2020). Tutorial zur dynamischen Programmierung. Entnommen aus: codechef.com.
6. Programiz (2020). Dynamische Programmierung. Entnommen aus: programiz.com.