Wie man Werte in Memoization Methode-Dynamische Pragrammierung

Question

Ich weiß für ein Problem, das mit DP gelöst werden kann, kann entweder durch Tabulierung (Bottom-up) Ansatz oder Memoisierung (Top-Down) Ansatz gelöst werden. persönlich finde ich memoization ist einfach und sogar effiziente Ansatz (Analyse erforderlich, nur rekursive Formel, sobald rekursive Formel erhalten, eine brute-force rekursive Methode kann leicht konvertiert werden, um Sub-Problem-Ergebnis speichern und wiederverwenden.) Das einzige Problem, dass Ich bin in diesem Ansatz konfrontiert ist, ich bin nicht in der Lage, das tatsächliche Ergebnis aus der Tabelle, die ich auf Nachfrage gefüllt.

Zum Beispiel, in Matrix Product Parenthesization problem (um zu entscheiden, in welcher Reihenfolge die Multiplikationen auf Matrizen durchzuführen, so dass die Kosten der Multiplikation minimal ist) kann ich minimale Kosten berechnen, nicht in der Lage, in algo Ordnung zu generieren. Angenommen, A ist eine 10 × 30-Matrix, B ist eine 30 × 5-Matrix und C ist eine 5 × 60-Matrix. Dann,

(AB)C = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 operations 
A(BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 operations. 

hier bin ich in der Lage, min-cost als 27000 zu bekommen, aber nicht in der Lage zu bekommen, die A (BC) ist.

Ich habe das verwendet. Nehmen wir an, F [i, j] stelle die kleinste Multiplikationszahl dar, die benötigt wird, um Ai ..... Aj zu multiplizieren, und eine Matrix p [] wird gegeben, die die Matrizenkette darstellt, so dass die i-te Matrix Ai die Dimension p [i-1 hat ] XP [i]. So

    0     if i=j 
    F[i,j]= 
        min(F[i,k] + F[k+1,j] +P_i-1 * P_k * P_j where k∈[i,j) 

Unten ist die Implementierung, die ich geschaffen habe.

#include<stdio.h> 
#include<limits.h> 
#include<string.h> 
#define MAX 4 
int lookup[MAX][MAX]; 

int MatrixChainOrder(int p[], int i, int j) 
{ 
    if(i==j) return 0; 
    int min = INT_MAX; 
    int k, count; 

    if(lookup[i][j]==0){ 
     // recursively calculate count of multiplcations and return the minimum count 
     for (k = i; k<j; k++) { 
      int gmin=0; 
      if(lookup[i][k]==0) 
       lookup[i][k]=MatrixChainOrder(p, i, k); 

      if(lookup[k+1][j]==0) 
       lookup[k+1][j]=MatrixChainOrder(p, k+1, j); 

      count = lookup[i][k] + lookup[k+1][j] + p[i-1]*p[k]*p[j]; 
      if (count < min){ 
       min = count; 

   printf("\n****%d ",k); // i think something has be done here to represent the correct answer ((AB)C)D where first mat is represented by A second by B and so on. 

  } 

     } 
     lookup[i][j] = min; 
    } 

    return lookup[i][j]; 
} 

// Driver program to test above function 
int main() 
{ 
    int arr[] = {2,3,6,4,5}; 
    int n = sizeof(arr)/sizeof(arr[0]); 

    memset(lookup, 0, sizeof(lookup)); 
    int width =10; 

    printf("Minimum number of multiplications is %d ", MatrixChainOrder(arr, 1, n-1)); 
    printf("\n ---->"); 
    for(int l=0;l<MAX;++l) 
    printf(" %*d ",width,l); 
    printf("\n"); 
    for(int z=0;z<MAX;z++){ 
     printf("\n %d--->",z); 
    for(int x=0;x<MAX;x++) 
    printf(" %*d ",width,lookup[z][x]); 
    } 

    return 0; 
} 

I Auftabellierung Ansatz weiß mit der Lösung Druck ist viel einfach, aber ich will es in memoization Technik tun.

Danke.

Answer 1

Ihr Code berechnet korrekt die Mindestanzahl von Multiplikationen, aber Sie haben Mühe, die optimale Kette von Matrixmultiplikationen anzuzeigen.

ist es zwei Möglichkeiten:

1. Wenn Sie die Tabelle zu berechnen, können Sie den besten Index in einem anderen memoization Array gefunden speichern.
2. Sie können die optimalen Aufteilungspunkte aus den Ergebnissen im Memoisierungsarray neu berechnen.

Die erste die Split-Punkte in einem separaten Array erstellen würde bedeuten:

int lookup_splits[MAX][MAX]; 

Und dann in Ihrer MatrixChainOrder Funktion ohne Aktualisierung:

... 
    if (count < min) { 
     min = count; 
     lookup_splits[i][j] = k; 
    } 

Sie können dann die Multiplikationskette erzeugen rekursiv wie folgt:

void print_mult_chain(int i, int j) { 
    if (i == j) { 
     putchar('A' + i - 1); 
     return; 
    } 
    putchar('('); 
    print_mult_chain(i, lookup_splits[i][j]); 
    print_mult_chain(lookup_splits[i][j] + 1, j); 
    putchar(')'); 
} 

Sie können die Funktion mit print_mult_chain(1, n - 1) von main aufrufen.

Die zweite Möglichkeit besteht darin, dass Sie lookup_splits nicht zwischenspeichern und wenn nötig neu berechnen. Diese

int get_lookup_splits(int p[], int i, int j) { 
    int best = INT_MAX; 
    int k_best; 
    for (int k = i; k < j; k++) { 
     int count = lookup[i][k] + lookup[k+1][j] + p[i-1]*p[k]*p[j]; 
     if (count < best) { 
      best = count; 
      k_best = k; 
     } 
    } 
    return k; 
} 

ist im Wesentlichen die gleiche Berechnung Sie innen tat MatrixChainOrder, also, wenn Sie mit dieser Lösung gehen sollten Sie den Code Faktor in geeigneter Weise zwei Kopien vermeiden müssen.

Mit dieser Funktion können Sie print_mult_chain oben anpassen, um es anstelle des lookup_splits Arrays zu verwenden. (Sie müssen das Array in) übergeben.

[Dieser Code wurde nicht getestet, daher müssen Sie möglicherweise die Antwort bearbeiten, um Fehler zu beheben].