algorithm - 如何在内存方法中打印值-动态编程

Question

我知道可以使用 DP 解决的问题可以通过制表(自下而上)方法或内存(自上而下)方法来解决。我个人觉得内存是简单有效的方法(只需要分析得到递归公式，一旦得到递归公式，暴力递归方法可以很容易地转换为存储子问题的结果并重用它。)唯一的问题是我在这种方法中面临的是，我无法从我按需填写的表格中构建实际结果。

例如，在 Matrix Product Parenthesization problem 中(决定以何种顺序对矩阵执行乘法以使乘法成本最小)我能够计算出不能在算法中生成顺序的最小成本。

例如，假设 A 是 10 × 30 矩阵，B 是 30 × 5 矩阵，C 是 5 × 60 矩阵。然后，

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

在这里我可以获得最低成本 27000 但无法获得 A(BC) 的订单。

我用过这个。假设 F[i, j] 表示乘以 Ai.....Aj 所需的最少乘法次数，并且给出数组 p[] 表示矩阵链，使得第 i 个矩阵 Ai 的维度为 p[i-1 ] x p[i].所以

                    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)

下面是我创建的实现。

#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;
}

我知道使用制表方法打印解决方案很容易，但我想用内存技术来实现。

谢谢。

Answer 1

您的代码正确计算了最小乘法次数，但您难以显示最佳的矩阵乘法链。

有两种可能:

1. 当您计算表时，您可以存储在另一个内存数组中找到的最佳索引。
2. 您可以根据内存数组中的结果重新计算最佳 split 点。

第一个涉及在单独的数组中创建分割点:

int lookup_splits[MAX][MAX];

然后在您的 MatrixChainOrder 函数中更新它:

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

然后您可以像这样递归地生成乘法链:

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(')');
}

您可以使用 print_mult_chain(1, n - 1) 从 main 调用该函数。

第二种可能性是您不缓存 lookup_splits 并在必要时重新计算它。

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;
}

这基本上与您在 MatrixChainOrder 中所做的计算相同，因此如果您采用此解决方案，则应适当分解代码以避免出现两个副本。

有了这个函数，您可以调整上面的 print_mult_chain 来使用它而不是 lookup_splits 数组。 (您需要传入 p 数组)。

[此代码均未经过测试，因此您可能需要编辑答案以修复错误]。