Dynamische Programmierung Probleme mit Iteration

Question

Ich habe eine Menge Zeit zu lernen über die Implementierung/Visualisierung von dynamischen Programmierung Probleme mit Iteration, aber ich finde es sehr schwer zu verstehen, kann ich das gleiche mit Rekursion mit Memoization implementieren, aber es ist langsam im Vergleich zur Iteration.

Kann jemand das gleiche anhand eines Beispiels eines schweren Problems oder anhand einiger grundlegender Konzepte erklären. Wie die Matrixkettenmultiplikation, längste palindromische Untersequenz und andere. Ich kann den Rekursionsprozess verstehen und dann die überlappenden Teilprobleme für die Effizienz notieren, aber ich kann nicht verstehen, wie ich dasselbe mit Iteration machen kann.

Danke!

Answer 1

Bei der dynamischen Programmierung geht es darum, die Teilprobleme zu lösen, um die größere zu lösen. Der Unterschied zwischen dem rekursiven Ansatz und dem iterativen Ansatz besteht darin, dass ersterer von oben nach unten und letzterer von unten nach oben verläuft. Mit anderen Worten, mit der Rekursion starten Sie von dem großen Problem, das Sie zu lösen versuchen, und zerhacken es auf ein bisschen kleinere Teilprobleme, auf denen Sie den Prozess wiederholen, bis Sie das Teilproblem erreichen, das Sie so klein lösen können. Dies hat den Vorteil, dass Sie nur die Teilprobleme lösen müssen, die unbedingt benötigt werden, und Memoization verwenden, um sich die Ergebnisse während der Ausführung zu merken. Der Bottom-Up-Ansatz löst zuerst alle Teilprobleme und verwendet die Tabellierung, um sich an die Ergebnisse zu erinnern. Wenn wir nicht zusätzliche Arbeit leisten, um die Teilprobleme zu lösen, die nicht benötigt werden, ist dies ein besserer Ansatz.

Für ein einfacheres Beispiel, schauen wir uns die Fibonacci-Sequenz an. Angenommen, wir möchten F(101) berechnen. Wenn wir es rekursiv tun, beginnen wir mit unserem großen Problem - F(101). Dafür bemerken wir, dass wir F(99) und F(100) berechnen müssen. Dann benötigen wir für F(99)F(97) und F(98). Wir fahren fort, bis wir das kleinste lösbare Teilproblem, nämlich F(1), erreichen und die Ergebnisse notieren. Wenn wir es iterativ machen, beginnen wir mit dem kleinsten Teilproblem, F(1), und fahren den ganzen Weg nach oben fort, wobei wir die Ergebnisse in einer Tabelle behalten (also ist es in diesem Fall im Grunde nur eine einfache for-Schleife von 1 bis 101).

Werfen wir einen Blick auf das Matrix-Ketten-Multiplikationsproblem, das Sie angefordert haben. Wir beginnen mit einer naiven rekursiven Implementierung, dann rekursiver DP und schließlich iterativer DP. Es wird in einer C/C++ - Suppe implementiert, aber Sie sollten in der Lage sein, mitzukommen, auch wenn Sie mit ihnen nicht sehr vertraut sind.

/* Solve the problem recursively (naive) 

    p - matrix dimensions 
    n - size of p 
    i..j - state (sub-problem): range of parenthesis */ 
int solve_rn(int p[], int n, int i, int j) { 
    // A matrix multiplied by itself needs no operations 
    if (i == j) return 0; 

    // A minimal solution for this sub-problem, we 
    // initialize it with the maximal possible value 
    int min = std::numeric_limits<int>::max(); 

    // Recursively solve all the sub-problems 
    for (int k = i; k < j; ++k) { 
     int tmp = solve_rn(p, n, i, k) + solve_rn(p, n, k + 1, j) + p[i - 1] * p[k] * p[j]; 
     if (tmp < min) min = tmp; 
    } 

    // Return solution for this sub-problem 
    return min; 
} 

das Ergebnis zu berechnen, beginnt man mit dem großen Problem:

solve_rn(p, n, 1, n - 1) 

Der Schlüssel von DP ist es, alle Lösungen für die Teilprobleme zu vergessen, sie stattdessen zu erinnern, so dass wir don‘ t müssen sie neu berechnen.Es ist trivial, ein paar Anpassungen an den obigen Code, um zu erreichen, dass zu machen:

/* Solve the problem recursively (DP) 

    p - matrix dimensions 
    n - size of p 
    i..j - state (sub-problem): range of parenthesis */ 
int solve_r(int p[], int n, int i, int j) { 
    /* We need to remember the results for state i..j. 
     This can be done in a matrix, which we call dp, 
     such that dp[i][j] is the best solution for the 
     state i..j. We initialize everything to 0 first. 

     static keyword here is just a C/C++ thing for keeping 
     the matrix between function calls, you can also either 
     make it global or pass it as a parameter each time. 

     MAXN is here too because the array size when doing it like 
     this has to be a constant in C/C++. I set it to 100 here. 
     But you can do it some other way if you don't like it. */ 
    static int dp[MAXN][MAXN] = {{0}}; 

    /* A matrix multiplied by itself has 0 operations, so we 
     can just return 0. Also, if we already computed the result 
     for this state, just return that. */ 
    if (i == j) return 0; 
    else if (dp[i][j] != 0) return dp[i][j]; 

    // A minimal solution for this sub-problem, we 
    // initialize it with the maximal possible value 
    dp[i][j] = std::numeric_limits<int>::max(); 

    // Recursively solve all the sub-problems 
    for (int k = i; k < j; ++k) { 
     int tmp = solve_r(p, n, i, k) + solve_r(p, n, k + 1, j) + p[i - 1] * p[k] * p[j]; 
     if (tmp < dp[i][j]) dp[i][j] = tmp; 
    } 

    // Return solution for this sub-problem 
    return dp[i][j];; 
} 

Wir mit dem großen Problem starten auch:

solve_r(p, n, 1, n - 1) 

Iterative Lösung ist nur, na ja, laufen alle die Staaten, sondern von der Spitze des Beginnens:

/* Solve the problem iteratively 

    p - matrix dimensions 
    n - size of p 

    We don't need to pass state, because we iterate the states. */ 
int solve_i(int p[], int n) { 
    // But we do need our table, just like before 
    static int dp[MAXN][MAXN]; 

    // Multiplying a matrix by itself needs no operations 
    for (int i = 1; i < n; ++i) 
     dp[i][i] = 0; 

    // L represents the length of the chain. We go from smallest, to 
    // biggest. Made L capital to distinguish letter l from number 1 
    for (int L = 2; L < n; ++L) { 
     // This double loop goes through all the states in the current 
     // chain length. 
     for (int i = 1; i <= n - L + 1; ++i) { 
      int j = i + L - 1; 
      dp[i][j] = std::numeric_limits<int>::max(); 

      for (int k = i; k <= j - 1; ++k) { 
       int tmp = dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j]; 
       if (tmp < dp[i][j]) 
        dp[i][j] = tmp; 
      } 
     } 
    } 

    // Return the result of the biggest problem 
    return dp[1][n-1]; 
} 

das Ergebnis zu berechnen, es rufen sie einfach an:

solve_i(p, n) 

---

Erklärung der Schleifenzähler im letzten Beispiel:

Lassen Sie uns sagen, dass wir die Multiplikation von 4 Matrizen optimieren müssen: A B C D. Wir machen einen iterativen Ansatz, also berechnen wir zuerst die Ketten mit der Länge von zwei: (A B) C D, A (B C) D und A B (C D). Und dann Ketten von drei: (A B C) D und A (B C D). Das ist, was L, i und j sind.

L stellt die Kettenlänge, es von 2 zu n - 1 geht (n4 ist in diesem Fall so, dass 3 ist).

i und j repräsentieren die Anfangs- und Endposition der Kette. Bei L = 2 geht i1-3 und j geht 2-4:

(A B) C D  A (B C) D  A B (C D) 
^^   ^^   ^^ 
i j    i j    i j 

Bei L = 3, i1-2 geht, und j geht 3-4:

(A B C) D  A (B C D) 
^ ^  ^^
i j   i j 

Also im Allgemeinen geht i von 1 zu n - L + 1 und j ist .

Lassen Sie uns nun mit dem Algorithmus fortfahren unter der Annahme, dass wir auf dem Schritt sind, wo wir (A B C) D haben. Wir müssen nun die Teilprobleme berücksichtigen, die bereits berechnet sind: ((A B) C) D und (A (B C)) D. Das ist, was k ist für. Es durchläuft alle Positionen zwischen i und j und berechnet die Unterprobleme.

Ich hoffe, dass ich geholfen habe.

Answer 2

Das Problem mit der Rekursion ist die hohe Anzahl von Stapelrahmen, die gedrückt/gepoppt werden müssen. Dies kann schnell zum Flaschenhals werden.

Die Fibonacci-Serie kann mit iterativer DP oder Rekursion mit Memoisierung berechnet werden. Wenn wir F (100) in DP berechnen, brauchen wir nur eine Anordnung der Länge 100, z. int[100] und das ist der Mut unseres benutzten Gedächtnisses.Wir berechnen alle Einträge der Array-Vorabfüllung f[0] und f[1], wie sie definiert sind, um 1 zu sein. und jeder Wert hängt nur von den vorherigen zwei ab.

Wenn wir eine rekursive Lösung verwenden, beginnen wir bei fib(100) und arbeiten weiter. Jeder Methodenaufruf von 100 bis 0 wird auf den Stapel geschoben, AND wird überprüft, ob es protokolliert ist. Diese Operationen addieren sich und die Iteration leidet nicht unter diesen. In Iteration (von unten nach oben) wissen wir bereits, dass alle vorherigen Antworten gültig sind. Der größere Einfluss ist wahrscheinlich die Stapelrahmen; und bei einer größeren Eingabe können Sie eine StackOverflowException für was sonst trivial mit einem iterativen DP-Ansatz erhalten.