矩阵连乘_实验报告
一、设计分析
l 问题描述：
给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1,2 ,…,n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。
l 设计思路：
设X=(x1,...xm), Y=(y1,y2,...yn)是两个序列，Z=(z1,z2,...zk)是X与Y的LCS。下列结论成立：
⑴ 如xm=yn, 则zk=xm=yn, Zk-1是Xm-1和Yn-1的LCS，即，
LCSXY=LCSXm-1Yn-1+<xm=yn>.
⑵ 若xm≠yn，且zk≠xm，则Z是Xm-1和Y的LCS，即
LCSXY=LCSXm-1Y
⑶ 若xm≠yn,且zk≠yn,则Z是X与Yn-1的LCS，即
LCSXY=LCSXYn-1
由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。
由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序列xi和yj的最长公共子序列的长度。其中， Xi={x1,x2,…xi}；Yj={y1,y2,…,yj}。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时C[i][j]=0。其它情况下，由最优子结构性质可建立递归关系如下：
复杂度分析
算法的计算时间上界为O(n3)。算法所占用的空间显然为O(n2)。
程序代码
c语言实现
三、测试用例
四、实验总结
通过本实验加深了对动态规划算法的理解，总结出动态规划算法的一般步骤：
1、找出最优解的性质，并刻划其结构特征。
2、递归地定义最优值。
3、以自底向上的方式计算出最优值
4、根据计算最优值时得到的信息，构造最优解。
第二篇：矩阵连乘问题
宁波工程学院电信学院计算机教研室
实验报告
一、实验目的：
通过上级实验，要求掌握动态规划算法的问题描述，算法设计思想，程序设计和算法复杂性分析等。
二、实验环境：VC6.0
三、实验内容：
1、用分治法算法解决最接近点对问题
(1)问题的描述
给定n个矩阵{nAAA?,2,1}，其中iA和1?iA是可乘的，i=1,2,…,n-1。考察这n个矩阵的连乘积nAAA?,2,1。由于矩阵乘法具有结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说连乘积已完全加括号，则可依次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘可递归地定义为：（1）单个矩阵是完全加括号的；（2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘B和C的乘积并加括号，即A=（BC）。 矩阵A和B可乘的条件是矩阵A的列数等于矩阵B的行数。若A是一个p×q的矩阵，B是一个q×r的矩阵，那么C=A×B就是一个p×r矩阵。它的计算是三重循环的，计算量是pqr。如果加括号后矩阵的量是不同的，所以我们的问题就是要讨论如何给连乘的矩阵加括号才能使矩阵的计算量最少。 穷举搜索法：对于n个矩阵的连乘积，设有不同的计算次序P(n)。由于可以先在第k个和第k+1个矩阵之间将原矩阵序列分为两个矩阵子序列，k=1,2,...,n-1；然后分别对这两个矩阵子序列完全加括号；最后对所得的结果加括号，得到原矩阵序列的一种完全加括号方式。
解递归方程可得，P(n)=C(n-1),而C(n)是一个指数增长的函数。因此穷举搜索法不是一个有效的算法。以下将用三种方法来解决矩阵连乘问题的最优加括号方式以及最优解。
(2)算法设计思想
由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。
1.分析最优解的结构
设计求解具体问题的动态规划算法的第一步是刻画该问题的最优解的结构特征。我们将矩阵连乘积AiAi+1....Aj简记为A[ i : j ]。考察计算A[ 1: n]的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，1<=k<n，则其相应的完全加括号形式为((A1...Ak)(Ak+1...An))。以此次序，总的计算量为A[ 1 : k ]的计算量加上A[ k+1 : n ]的计算量， 再加上A[ 1 : k ]和A[ k+1 : n ]相称的计算量。
这个问题的关键特征是：计算A[ 1 :n ]的最优次序所包含的计算矩阵子链a[ 1 : k ]和A[ k+1 : n ]的次序也是最优的。因此，矩阵连乘积计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可以用动态规划算法求解的显著特征。
2.建立递归关系
设计动态规划算法的第二步就是递归地定义最优值。对于矩阵连乘积的最有计算次序问题，设计算A[ i : j ], 1<=i<=j<=n，所需的最少数乘次数为m[ i ][ j ]，则原问题的最优值为m[ 1 ][ n]。
当i=j时，A[ i ; j ]=Ai，为单一矩阵，无需计算，因此m[ i ][ i ]=0。
当i < j时，可以利用最优子结构的性质来计算m[ i ][ j ]。事实上，若计算A[ i : j ]的最优次序在Ak和Ak+1之间断开，i<=k<j，则m[ i ][ j ]=m[ i ][ k ]+m[k+1][ j ]+Pi-1*Pk*Pj。其中Pi表示第i个矩阵的列数，也是第i-1个矩阵的行数，P0表示第一个矩阵的行数。由于在计算时并不知道断开点k的位置，所以k还未定。不过k的位置只有j-i个可能。从而m[ i ][ j ]可以递归地定义为
当i=j m[ i ][ j ] = 0
当i<j m[ i ][ j ] = min{ m[ i ][ k ]+m[ k+1 ][ j ]+Pi-1*Pk*Pj }
m[ i ][ j ]给出了最优值，即计算A[ i : j ]所需的最少数乘次数。同时还确定了计算A[ i : j ]的最优次序中的断开位置k，也就是说，对于这个k有
m[ i ][ j ]=m[ i [ k ]+m[ k+1 ][ j] + Pi-1*Pk*Pj
若将对应于m[ i ][ j ]的断开位置k记为s[ i ][ j ]， 在计算最优值m[ i ][ j ]后，可以递归地有s[ i ][ j ]构造出相应的最优解。
3.计算最优值
根据计算m[ i ][ j ]的递归式，容易写一个递归算法计算m[ 1 ][ n ]。但是简单地递归将好费指数计算时间。在递归计算时，许多子问题被重复计算多次。这也是该问题可以用动态规划算法求解的又一显著特征。
用动态规划算法解决此问题，可依据其递归是以自底向上的方式进行计算。在计算的过程中，保存以解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算。
(3)程序设计（程序清单及说明）
#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()
{
//矩阵：M1[8,30] M2[30,53] M3[53,55] M4[55,60] M5[60,30] M6[30,40]
//上述矩阵的最数字
int p[L]={8,30,53,55,60,30,40};
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 M"<<i<<","<<s[i][j];
cout<<" and M"<<(s[i][j]+1)<<","<<j<<endl; }
(4)数据输入和输出结果（运行结果截屏显示）
(5)算法复杂性分析
算法matrixChina的主要计算量取决于算法中对r，i和k的三重循环，循环体内的计算量为O（1），而3重循环的总次数为O（n3）。一次该算法的时间上界为O（n3）。所占空间为O（n3）。