Suche…


Bemerkungen

In diesem Abschnitt erhalten Sie einen Überblick darüber, was dynamische Programmierung ist und warum ein Entwickler sie verwenden möchte.

Es sollte auch alle großen Themen in der dynamischen Programmierung erwähnen und auf die verwandten Themen verweisen. Da die Dokumentation zur dynamischen Programmierung neu ist, müssen Sie möglicherweise erste Versionen dieser verwandten Themen erstellen.

Einführung in die dynamische Programmierung

Dynamische Programmierung löst Probleme durch Kombinieren der Lösungen für Unterprobleme. Es kann analog zum Divide-and-Conquer-Verfahren sein, bei dem das Problem in disjunkte Unterprobleme unterteilt wird, die Teilprobleme rekursiv gelöst und dann kombiniert werden, um die Lösung des ursprünglichen Problems zu finden. Im Gegensatz dazu gilt die dynamische Programmierung, wenn sich die Teilprobleme überschneiden, dh wenn sich die Teilprobleme Teilprobleme teilen. In diesem Zusammenhang leistet ein Divide-and-Conquer-Algorithmus mehr Arbeit als nötig und löst die häufigen Subsub-Probleme wiederholt. Ein dynamischer Programmieralgorithmus löst jedes Subsub-Problem nur einmal und speichert seine Antwort in einer Tabelle. Dadurch muss die Antwort nicht jedes Mal neu berechnet werden, wenn jedes Subsub-Problem gelöst wird.

Schauen wir uns ein Beispiel an. Der italienische Mathematiker Leonardo Pisano Bigollo , den wir allgemein als Fibonacci kennen, entdeckte eine Reihe von Zahlen, indem er das idealisierte Wachstum der Kaninchenpopulation berücksichtigte. Die Serie ist:

1, 1, 2, 3, 5, 8, 13, 21, ......

Wir können feststellen, dass jede Zahl nach den ersten beiden Zahlen die Summe der zwei vorhergehenden Zahlen ist. Lassen Sie uns nun eine Funktion F (n) formulieren, die uns die n-te Fibonacci-Zahl zurückgibt, dh

F(n) = nth Fibonacci Number

Bisher haben wir das gewusst,

F(1) = 1
F(2) = 1
F(3) = F(2) + F(1) = 2
F(4) = F(3) + F(2) = 3

Wir können es verallgemeinern durch:

F(1) = 1
F(2) = 1
F(n) = F(n-1) + F(n-2)

Wenn wir es nun als rekursive Funktion schreiben wollen, haben wir F(1) und F(2) als Basisfall. Unsere Fibonacci-Funktion wäre also:

Procedure F(n):                //A function to return nth Fibonacci Number
if n is equal to 1
    Return 1
else if n is equal to 2
    Return 1
end if
Return F(n-1) + F(n-2)

Wenn wir nun F(6) aufrufen, werden F(5) und F(4) angerufen, wodurch weitere Anrufe erfolgen. Lassen Sie uns dies grafisch darstellen:

Rekursionsbaum für F (6)

Aus dem Bild können wir sehen, dass F(6) F(5) und F(4) . Nun ruft F(5) F(4) und F(3) . Nach der Berechnung von F(5) können wir mit Sicherheit sagen, dass alle Funktionen, die von F(5) aufgerufen wurden, bereits berechnet wurden. Das heißt, wir haben bereits F(4) berechnet. Aber wir berechnen wieder F(4) wie das rechte Kind von F(6) anzeigt. Müssen wir wirklich neu berechnen? Was wir tun können, ist, sobald wir den Wert von F(4) berechnet haben, speichern wir ihn in einem Array mit dem Namen dp und verwenden ihn bei Bedarf erneut. Wir initialisieren unser dp- Array mit -1 (oder einem beliebigen Wert, der in unserer Berechnung nicht berücksichtigt wird). Dann rufen wir F (6) an, wo unser modifiziertes F (n) so aussehen wird:

Procedure F(n):
if n is equal to 1
    Return 1
else if n is equal to 2
    Return 1
else if dp[n] is not equal to -1            //That means we have already calculated dp[n]
    Return dp[n]
else
    dp[n] = F(n-1) + F(n-2)
    Return dp[n]
end if

Wir haben die gleiche Aufgabe wie zuvor gemacht, jedoch mit einer einfachen Optimierung. Das heißt, wir haben die Memo- Technik verwendet. Zunächst sind alle Werte des dp- Arrays -1 . Wenn F(4) aufgerufen wird, prüfen wir, ob es leer ist oder nicht. Wenn es -1 speichert, berechnen wir seinen Wert und speichern ihn in dp [4] . Wenn es etwas anderes als -1 speichert, haben wir seinen Wert bereits berechnet. Also geben wir einfach den Wert zurück.

Diese einfache Optimierung mittels Memoization wird als Dynamische Programmierung bezeichnet .

Ein Problem kann mithilfe der dynamischen Programmierung gelöst werden, wenn es einige Merkmale aufweist. Diese sind:

  • Teilprobleme:
    Ein DP-Problem kann in ein oder mehrere Teilprobleme unterteilt werden. Zum Beispiel: F(4) kann in kleinere Teilprobleme F(3) und F(2) . Da die Unterprobleme unserem Hauptproblem ähnlich sind, können sie mit derselben Technik gelöst werden.
  • Überlappende Teilprobleme:
    Ein DP-Problem muss überlappende Teilprobleme haben. Das heißt, es muss einen gemeinsamen Teil geben, für den dieselbe Funktion mehrmals aufgerufen wird. Zum Beispiel: F(5) und F(6) haben F(3) und F(4) gemeinsam. Aus diesem Grund haben wir die Werte in unserem Array gespeichert.

Überlappendes Teilproblemdiagramm

  • Optimale Unterkonstruktion:
    Angenommen, Sie werden aufgefordert, die Funktion g(x) zu minimieren. Sie wissen, dass der Wert von g(x) von g(y) und g(z) abhängt. Wenn wir nun g(x) minimieren können, indem wir sowohl g(y) als auch g(z) minimieren, können wir nur sagen, dass das Problem eine optimale Unterstruktur hat. Wenn g(x) nur durch Minimieren von g(y) minimiert wird und wenn das Minimieren oder Maximieren von g(z) keinen Einfluss auf g(x) , hat dieses Problem keine optimale Unterstruktur. In einfachen Worten, wenn die optimale Lösung eines Problems aus der optimalen Lösung des Teilproblems herausgefunden werden kann, können wir sagen, dass das Problem eine optimale Unterstruktur-Eigenschaft hat.

Status in der dynamischen Programmierung verstehen

Lassen Sie uns mit einem Beispiel besprechen. Von n Artikel, in wie viele Möglichkeiten , wie Sie r Elemente auswählen können? Sie wissen, dass es mit gekennzeichnet ist nCr . Denken Sie jetzt an einen einzelnen Artikel.

  • Wenn Sie den Gegenstand nicht auswählen, müssen Sie danach r Gegenstände aus den verbleibenden n-1 Gegenständen entnehmen, die von gegeben werden (n-1) Cr .
  • Wenn Sie den Gegenstand auswählen, müssen Sie danach r-1 Gegenstände aus den verbleibenden n-1 Gegenständen entnehmen, die von gegeben werden (n-1) C (r-1) .

Die Summe dieser beiden ergibt die Gesamtzahl der Möglichkeiten. Das ist:
nCr = (n-1) Cr + (n-1) C (r-1)

Wenn wir nCr(n,r) als Funktion betrachten, nimmt man n und r als Parameter und bestimmt nCr können wir die oben genannte Beziehung schreiben als:

nCr(n,r) = nCr(n-1,r) + nCr(n-1,r-1)

Dies ist eine rekursive Beziehung. Um es zu beenden, müssen wir die Basisfälle bestimmen. Wir wissen das, nC1 = n und nCn = 1 . Anhand dieser beiden als Basisfälle kann unser Algorithmus ermittelt werden nCr wird sein:

Procedure nCr(n, r):
if r is equal to 1
    Return n
else if n is equal to r
    Return 1
end if
Return nCr(n-1,r) + nCr(n-1,r-1)

Wenn wir uns die Prozedur grafisch ansehen, sehen wir einige Rekursionen, die mehrmals aufgerufen werden. Zum Beispiel: Wenn wir n = 8 und r = 5 nehmen , erhalten wir:

Rekursionsbaum mit überlappendem Teilproblem

Wir können diesen wiederholten Aufruf vermeiden, indem wir ein Array verwenden, dp . Da es 2 Parameter gibt, benötigen wir ein 2D-Array. Wir initialisieren das dp- Array mit -1 , wobei -1 den Wert noch nicht berechnet hat. Unser Verfahren wird sein:

Procedure nCr(n,r):
if r is equal to 1
    Return n
else if n is equal to r
    Return 1
else if dp[n][r] is not equal to -1        //The value has been calculated
    Return dp[n][r]
end if
dp[n][r] := nCr(n-1,r) + nCr(n-1,r-1)
Return dp[n][r]

Bestimmen nCr Wir brauchten zwei Parameter n und r . Diese Parameter werden als Zustand bezeichnet . Wir können einfach daraus schließen, dass die Anzahl der Zustände die Anzahl der Dimensionen des dp- Arrays bestimmen. Die Größe des Arrays ändert sich je nach Bedarf. Unsere dynamischen Programmieralgorithmen werden das folgende allgemeine Muster beibehalten:

Procedure DP-Function(state_1, state_2, ...., state_n)
Return if reached any base case
Check array and Return if the value is already calculated.
Calculate the value recursively for this state
Save the value in the table and Return

Die Bestimmung des Zustands ist einer der wichtigsten Aspekte der dynamischen Programmierung. Es besteht aus der Anzahl der Parameter, die unser Problem definieren und deren Berechnung optimieren. Wir können das gesamte Problem optimieren.

Aufbau einer DP-Lösung

Egal wie viele Probleme Sie mit der dynamischen Programmierung (DP) lösen, es kann Sie trotzdem überraschen. Aber wie alles andere im Leben, macht Übung Sie besser. Vor diesem Hintergrund betrachten wir den Prozess der Erstellung einer Lösung für DP-Probleme. Weitere Beispiele zu diesem Thema helfen Ihnen zu verstehen, was DP ist und wie es funktioniert. In diesem Beispiel versuchen wir zu verstehen, wie eine DP-Lösung von Grund auf erstellt wird.

Iterative VS rekursiv:
Es gibt zwei Techniken zum Erstellen einer DP-Lösung. Sie sind:

  • Iterativ (for-cycle verwenden)
  • Rekursiv (Rekursion verwenden)

Ein Algorithmus zum Berechnen der Länge der längsten gemeinsamen Teilsequenz der zwei Strings s1 und s2 würde beispielsweise so aussehen:

Procedure LCSlength(s1, s2):
Table[0][0] = 0
for i from 1 to s1.length
    Table[0][i] = 0
endfor
for i from 1 to s2.length
    Table[i][0] = 0
endfor
for i from 1 to s2.length
    for j from 1 to s1.length
        if s2[i] equals to s1[j]
            Table[i][j] = Table[i-1][j-1] + 1
        else
            Table[i][j] = max(Table[i-1][j], Table[i][j-1])
        endif
    endfor
endfor
Return Table[s2.length][s1.length]

Dies ist eine iterative Lösung. Es gibt einige Gründe, warum es so codiert ist:

  • Iteration ist schneller als Rekursion.
  • Die Bestimmung der Komplexität von Zeit und Raum ist einfacher.
  • Der Quellcode ist kurz und sauber

Wenn Sie sich den Quellcode anschauen, können Sie leicht verstehen, wie und warum er funktioniert, aber es ist schwer zu verstehen, wie Sie diese Lösung finden. Die beiden oben genannten Ansätze übersetzen jedoch in zwei verschiedene Pseudo-Codes. Eine verwendet Iteration (Bottom-Up) und eine andere Methode verwendet Rekursion (Top-Down). Letzteres ist auch als Memo-Technik bekannt. Die beiden Lösungen sind jedoch mehr oder weniger gleichwertig und eine kann leicht in eine andere umgewandelt werden. In diesem Beispiel zeigen wir Ihnen, wie Sie eine rekursive Lösung für ein Problem finden.

Beispielproblem:
Nehmen wir an, Sie haben N ( 1, 2, 3, ..., N ) Weine nebeneinander in einem Regal. Der Preis des i- ten Weins beträgt p [i] . Der Preis der Weine steigt jedes Jahr. Angenommen , das ist Jahr 1 zu Jahr y der Preis des i - ten Wein sein: Jahr * Preis des Weines = y * p [i]. Sie möchten Ihre Weine verkaufen, aber ab diesem Jahr müssen Sie genau einen Wein pro Jahr verkaufen. Sie dürfen jedes Jahr nur den Wein ganz links oder ganz rechts verkaufen, und Sie können die Weine nicht neu anordnen, dh sie müssen in der gleichen Reihenfolge bleiben wie am Anfang.

Zum Beispiel: Nehmen wir an, Sie haben 4 Weine im Regal und ihre Preise sind (von links nach rechts):

+---+---+---+---+
| 1 | 4 | 2 | 3 |
+---+---+---+---+

Die optimale Lösung wäre, die Weine in der Reihenfolge 1 -> 4 -> 3 -> 2 zu verkaufen, wodurch wir insgesamt einen Gewinn erzielen können: 11 + 32 + 23 + 44 = 29

Gieriger Ansatz:
Nach einem Brainstorming für eine Weile könnten Sie die Lösung finden, um den teuren Wein so spät wie möglich zu verkaufen. Ihre gierige Strategie lautet also:

Every year, sell the cheaper of the two (leftmost and rightmost) available wines.

Obwohl die Strategie nicht erwähnt, was zu tun ist, wenn die beiden Weine das gleiche kosten, fühlt sich die Strategie irgendwie richtig an. Aber leider nicht. Wenn die Preise der Weine sind:

+---+---+---+---+---+
| 2 | 3 | 5 | 1 | 4 |
+---+---+---+---+---+

Die gierige Strategie würde sie in der Reihenfolge 1 -> 2 -> 5 -> 4 -> 3 für einen Gesamtgewinn von verkaufen: 21 + 32 + 43 + 14 + 5 * 5 = 49

Aber wir können es besser machen, wenn wir die Weine in der Reihenfolge 1 -> 5 -> 4 -> 2 -> 3 verkaufen, um einen Gesamtgewinn von: 21 + 42 + 13 + 34 + 5 * 5 = 50

Dieses Beispiel sollte Sie überzeugen, dass das Problem auf den ersten Blick nicht so einfach ist. Es kann jedoch mit der dynamischen Programmierung gelöst werden.

Backtracking:
Es ist praktisch, die Memoization-Lösung für ein Problem zu finden, um eine Backtrack-Lösung zu finden. Die Backtrack-Lösung wertet alle gültigen Antworten für das Problem aus und wählt die beste Lösung aus. Für die meisten Probleme ist es einfacher, eine solche Lösung zu finden. Bei der Annäherung an eine Backtrack-Lösung kann es drei Strategien geben:

  1. Es sollte eine Funktion sein, die die Antwort mittels Rekursion berechnet.
  2. es sollte die Antwort mit return- Anweisung zurückgeben.
  3. Alle nicht lokalen Variablen sollten schreibgeschützt verwendet werden, dh die Funktion kann nur lokale Variablen und ihre Argumente ändern.

Für unser Beispielproblem versuchen wir, den Wein ganz links oder ganz rechts zu verkaufen, die Antwort rekursiv zu berechnen und den besseren zurückzugeben. Die Backtrack-Lösung würde folgendermaßen aussehen:

// year represents the current year
// [begin, end] represents the interval of the unsold wines on the shelf
Procedure profitDetermination(year, begin, end):
if begin > end                  //there are no more wines left on the shelf
    Return 0
Return max(profitDetermination(year+1, begin+1, end) + year * p[begin], //selling the leftmost item
           profitDetermination(year+1, begin, end+1) + year * p[end])   //selling the rightmost item

Wenn wir das Verfahren mit profitDetermination(1, 0, n-1) , wobei n die Gesamtzahl der Weine ist, wird die Antwort zurückgegeben.

Bei dieser Lösung werden einfach alle möglichen gültigen Kombinationen des Verkaufs der Weine ausprobiert. Wenn am Anfang n Weine stehen, wird dies überprüft 2 ^ n Möglichkeiten. Obwohl wir jetzt die richtige Antwort erhalten, wächst die zeitliche Komplexität des Algorithmus exponentiell.

Die korrekt geschriebene Backtrack-Funktion sollte immer eine Antwort auf eine gut formulierte Frage darstellen. In unserem Beispiel stellt das Verfahren profitDetermination eine Antwort auf die Frage dar: Was ist der beste Gewinn, den wir durch den Verkauf der Weine mit im Array p gespeicherten Preisen erzielen können, wenn das laufende Jahr das Jahr ist und sich die Zeitspanne der unverkauften Weine erstreckt? Ende], inklusive? Sie sollten immer versuchen, eine solche Frage für Ihre Backtrack-Funktion zu erstellen, um zu sehen, ob Sie sie richtig verstanden haben und genau verstehen, was sie tut.

Zustandsbestimmung:
State ist die Anzahl der in der DP-Lösung verwendeten Parameter. In diesem Schritt müssen wir uns überlegen, welche der Argumente, die Sie an die Funktion übergeben, redundant sind, dh wir können sie aus den anderen Argumenten konstruieren oder brauchen sie überhaupt nicht. Wenn solche Argumente vorhanden sind, müssen wir sie nicht an die Funktion übergeben. Wir berechnen sie innerhalb der Funktion.

In der Beispielfunktion profitDetermination oben gezeigt, das Argument year ist überflüssig. Dies entspricht der Anzahl der bereits verkauften Weine plus eins. Es kann anhand der Gesamtzahl der Weine von Anfang an minus der Anzahl der Weine, die wir nicht verkauft haben, plus eins ermittelt werden. Wenn wir die Gesamtzahl der Weine n als globale Variable speichern, können wir die Funktion wie folgt umschreiben:

Procedure profitDetermination(begin, end):
if begin > end
    Return 0
year := n - (end-begin+1) + 1        //as described above
Return max(profitDetermination(begin+1, end) + year * p[begin],
           profitDetermination(begin, end+1) + year * p[end])

Wir müssen auch über den Bereich der möglichen Werte der Parameter nachdenken, die aus einer gültigen Eingabe stammen können. In unserem Beispiel kann jeder Parameter begin und end Werte von 0 bis n-1 enthalten . In einer gültigen Eingabe erwarten wir auch begin <= end + 1 . Es kann O(n²) verschiedene Argumente geben, mit denen unsere Funktion aufgerufen werden kann.

Memoization:
Wir sind jetzt fast fertig. Um die Backtrack-Lösung mit zeitlicher Komplexität umzuwandeln O (2 ^ n) in Memoization-Lösung mit zeitlicher Komplexität O (n ^ 2) verwenden wir einen kleinen Trick, der nicht viel Aufwand erfordert.

Wie oben erwähnt, gibt es nur O (n ^ 2) verschiedene Parameter, mit denen unsere Funktion aufgerufen werden kann. Mit anderen Worten gibt es nur O (n ^ 2) verschiedene Dinge können wir tatsächlich berechnen. Wo also? O (2 ^ n) Zeit Komplexität kommen und was berechnet sie !!

Die Antwort lautet: Die exponentielle zeitliche Komplexität ergibt sich aus der wiederholten Rekursion und berechnet aus diesem Grund immer wieder dieselben Werte. Wenn Sie den oben genannten Code für ein beliebiges Array von n = 20 Weinen ausführen und berechnen, wie oft die Funktion für die Argumente begin = 10 und end = 10 aufgerufen wurde, erhalten Sie eine Nummer 92378 . Das ist eine enorme Zeitverschwendung, um die gleiche Antwort wie oft zu berechnen. Wir könnten dies verbessern, indem wir die Werte speichern, sobald wir sie berechnet haben. Jedes Mal, wenn die Funktion nach einem bereits berechneten Wert fragt, müssen wir die gesamte Rekursion nicht erneut ausführen. Wir haben ein Array dp [N] [N] , initialisieren Sie es mit -1 (oder einem beliebigen Wert, der in unserer Berechnung nicht berücksichtigt wird), wobei -1 den noch nicht berechneten Wert angibt. Die Größe des Arrays wird durch den maximal möglichen Wert von beginnen bestimmt und enden , wie wir die entsprechenden Werte bestimmter speichern werden beginnen , und Endwerte in unserem Angebote. Unser Verfahren würde folgendermaßen aussehen:

Procedure profitDetermination(begin, end):
if begin > end
    Return 0
if dp[begin][end] is not equal to -1                //Already calculated
    Return dp[begin][end]
year := n - (end-begin+1) + 1
dp[begin][end] := max(profitDetermination(year+1, begin+1, end) + year * p[begin],
           profitDetermination(year+1, begin, end+1) + year * p[end])
Return dp[begin][end]

Dies ist unsere erforderliche DP-Lösung. Mit unserem sehr einfachen Trick läuft die Lösung O (n ^ 2) Zeit, denn es gibt O (n ^ 2) verschiedene Parameter, mit denen unsere Funktion aufgerufen werden kann, und für jeden von ihnen läuft die Funktion nur einmal mit O (1) Komplexität.

Sommerlich:
Wenn Sie ein Problem identifizieren können, das mit DP gelöst werden kann, führen Sie die folgenden Schritte aus, um eine DP-Lösung zu erstellen:

  • Erstellen Sie eine Rückverfolgungsfunktion, um die richtige Antwort bereitzustellen.
  • Entfernen Sie die redundanten Argumente.
  • Schätzen und minimieren Sie den maximalen Bereich der möglichen Parameterparameter.
  • Versuchen Sie, die zeitliche Komplexität eines Funktionsaufrufs zu optimieren.
  • Speichern Sie die Werte, damit Sie sie nicht zweimal berechnen müssen.

Die Komplexität einer DP-Lösung ist: Bereich der möglichen Werte Die Funktion kann mit der * Zeitkomplexität jedes Aufrufs aufgerufen werden .



Modified text is an extract of the original Stack Overflow Documentation
Lizenziert unter CC BY-SA 3.0
Nicht angeschlossen an Stack Overflow