如何在记忆方法中打印值-动态编程
How to print values in memoization method-Dynamic pragraming
我知道一个可以使用 DP 解决的问题,可以通过制表(自下而上)方法或记忆(自上而下)方法来解决。我个人觉得记忆是简单有效的方法(只需要分析得到递归公式,一旦得到递归公式,暴力递归方法可以很容易地转换为存储子问题的结果并重用它。)唯一的问题是我在这种方法中面临的是,我无法从我按需填写的 table 构建实际结果。
例如,在 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;
}
我知道使用制表方法打印解决方案很容易,但我想用记忆技术来实现。
谢谢。
您的代码正确计算了最小乘法次数,但您难以显示最佳的矩阵乘法链。
有两种可能:
- 当您计算 table 时,您可以存储在另一个记忆数组中找到的最佳索引。
- 您可以根据记忆数组中的结果重新计算最佳分裂点。
第一个涉及在单独的数组中创建分割点:
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
数组)。
[None 此代码已经过测试,因此您可能需要编辑答案以修复错误]。
我知道一个可以使用 DP 解决的问题,可以通过制表(自下而上)方法或记忆(自上而下)方法来解决。我个人觉得记忆是简单有效的方法(只需要分析得到递归公式,一旦得到递归公式,暴力递归方法可以很容易地转换为存储子问题的结果并重用它。)唯一的问题是我在这种方法中面临的是,我无法从我按需填写的 table 构建实际结果。
例如,在 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;
}
我知道使用制表方法打印解决方案很容易,但我想用记忆技术来实现。
谢谢。
您的代码正确计算了最小乘法次数,但您难以显示最佳的矩阵乘法链。
有两种可能:
- 当您计算 table 时,您可以存储在另一个记忆数组中找到的最佳索引。
- 您可以根据记忆数组中的结果重新计算最佳分裂点。
第一个涉及在单独的数组中创建分割点:
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
数组)。
[None 此代码已经过测试,因此您可能需要编辑答案以修复错误]。