WizenZhang
10/4/2018 - 11:31 AM
【动态规划】矩阵连乘问题【3.1】
给定n个矩阵：A1,A2,...,An，其中Ai与Ai+1是可乘的，i=1，2...，n-1。确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。输入数据为矩阵个数和每个矩阵规模，输出结果为计算矩阵连乘积的计算次序和最少数乘次数。 例：设要计算矩阵连乘乘积A1A2A3A4A5A6，其中各矩阵的维数分别是： A1：3035; A2：3515; A3：155; A4：510; A5：1020; A6：2025 1、重叠递归 2、备忘录递归算法 备忘录方法用表格保存已解决的子问题答案，在下次需要解决此子问题时，只要简单查看该子问题的解答，而不必重新计算。备忘录方法为每一个子问题建立一个记录项，初始化时，该记录项存入一个特殊的值，表示该子问题尚未求解。在求解的过程中，对每个带求的子问题，首先查看其相应的记录项。若记录项中存储的是初始化时存入的特殊值，则表示该问题是第一次遇到，此时计算出该子问题的解，并将其保存在相应的记录项中，以备以后查看。若记录项中存储的已不是初始化时存入的特殊值，则表示该子问题已被计算过，相应的记录项中存储的是该子问题的解答。此时从记录项中取出该子问题的解答即可，而不必重新计算。 3、动态规划迭代实现 用动态规划迭代方式解决此问题，可依据其递归式自底向上的方式进行计算。在计算过程中，保存已解决的子问题的答案。每个子问题只计算一次，而在后面需要时只需简单检查一下，从而避免了大量的重复计算，最终得到多项式时间的算法。
//3d1-2 矩阵连乘 动态规划迭代实现
//A1 30*35 A2 35*15 A3 15*5 A4 5*10 A5 10*20 A6 20*25
//p[0-6]={30,35,15,5,10,20,25}
#include "stdafx.h"
#include <iostream>
using namespace std;
const int L = 7;
int MatrixChain(int n,int **m,int **s,int *p);
void Traceback(int i,int j,int **s);//构造最优解
int main()
{
int p[L]={30,35,15,5,10,20,25};
int **s = new int *[L];
int **m = new int *[L];
for(int i=0;i<L;i++)
{
s[i] = new int[L];
m[i] = new int[L];
}
cout<<"矩阵的最少计算次数为："<<MatrixChain(6,m,s,p)<<endl;
cout<<"矩阵最优计算次序为："<<endl;
Traceback(1,6,s);
return 0;
}
int MatrixChain(int n,int **m,int **s,int *p)
{
for(int i=1; i<=n; i++)
{
m[i][i] = 0;
}
for(int r=2; r<=n; r++) //r为当前计算的链长（子问题规模）
{
for(int i=1; i<=n-r+1; i++)//n-r+1为最后一个r链的前边界
{
int j = i+r-1;//计算前边界为r，链长为r的链的后边界
m[i][j] = m[i+1][j] + p[i-1]*p[i]*p[j];//将链ij划分为A(i) * ( A[i+1:j] )
s[i][j] = i;
for(int k=i+1; k<j; k++)
{
//将链ij划分为( A[i:k] )* (A[k+1:j])
int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
if(t<m[i][j])
{
m[i][j] = t;
s[i][j] = k;
}
}
}
}
return m[1][L-1];
}
void Traceback(int i,int j,int **s)
{
if(i==j) return;
Traceback(i,s[i][j],s);
Traceback(s[i][j]+1,j,s);
cout<<"Multiply A"<<i<<","<<s[i][j];
cout<<" and A"<<(s[i][j]+1)<<","<<j<<endl;
}
//3d1-2 矩阵连乘 备忘录递归实现
//A1 30*35 A2 35*15 A3 15*5 A4 5*10 A5 10*20 A6 20*25
//p[0-6]={30,35,15,5,10,20,25}
#include "stdafx.h"
#include <iostream>
using namespace std;
const int L = 7;
int LookupChain(int i,int j,int **m,int **s,int *p);
int MemoizedMatrixChain(int n,int **m,int **s,int *p);
void Traceback(int i,int j,int **s);//构造最优解
int main()
{
int p[L]={30,35,15,5,10,20,25};
int **s = new int *[L];
int **m = new int *[L];
for(int i=0;i<L;i++)
{
s[i] = new int[L];
m[i] = new int[L];
}
cout<<"矩阵的最少计算次数为："<<MemoizedMatrixChain(6,m,s,p)<<endl;
cout<<"矩阵最优计算次序为："<<endl;
Traceback(1,6,s);
return 0;
}
int MemoizedMatrixChain(int n,int **m,int **s,int *p)
{
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
m[i][j]=0;
}
}
return LookupChain(1,n,m,s,p);
}
int LookupChain(int i,int j,int **m,int **s,int *p)
{
if(m[i][j]>0)
{
return m[i][j];
}
if(i==j)
{
return 0;
}
int u = LookupChain(i,i,m,s,p) + LookupChain(i+1,j,m,s,p)+p[i-1]*p[i]*p[j];
s[i][j]=i;
for(int k=i+1; k<j; k++)
{
int t = LookupChain(i,k,m,s,p) + LookupChain(k+1,j,m,s,p) + p[i-1]*p[k]*p[j];
if(t<u)
{
u=t;
s[i][j] = k;
}
}
m[i][j] = u;
return u;
}
void Traceback(int i,int j,int **s)
{
if(i==j) return;
Traceback(i,s[i][j],s);
Traceback(s[i][j]+1,j,s);
cout<<"Multiply A"<<i<<","<<s[i][j];
cout<<" and A"<<(s[i][j]+1)<<","<<j<<endl;
}
//3d1-1 重叠子问题的递归最优解
//A1 30*35 A2 35*15 A3 15*5 A4 5*10 A5 10*20 A6 20*25
//p[0-6]={30,35,15,5,10,20,25}
#include "stdafx.h"
#include <iostream>
using namespace std;
const int L = 7;
int RecurMatrixChain(int i,int j,int **s,int *p);//递归求最优解
void Traceback(int i,int j,int **s);//构造最优解
int main()
{
int p[L]={30,35,15,5,10,20,25};
int **s = new int *[L];
for(int i=0;i<L;i++)
{
s[i] = new int[L];
}
cout<<"矩阵的最少计算次数为："<<RecurMatrixChain(1,6,s,p)<<endl;
cout<<"矩阵最优计算次序为："<<endl;
Traceback(1,6,s);
return 0;
}
int RecurMatrixChain(int i,int j,int **s,int *p)
{
if(i==j) return 0;
int u = RecurMatrixChain(i,i,s,p)+RecurMatrixChain(i+1,j,s,p)+p[i-1]*p[i]*p[j];
s[i][j] = i;
for(int k=i+1; k<j; k++)
{
int t = RecurMatrixChain(i,k,s,p) + RecurMatrixChain(k+1,j,s,p) + p[i-1]*p[k]*p[j];
if(t<u)
{
u=t;
s[i][j]=k;
}
}
return u;
}
void Traceback(int i,int j,int **s)
{
if(i==j) return;
Traceback(i,s[i][j],s);
Traceback(s[i][j]+1,j,s);
cout<<"Multiply A"<<i<<","<<s[i][j];
cout<<" and A"<<(s[i][j]+1)<<","<<j<<endl;
}