矩阵连乘问题Word格式.docx
《矩阵连乘问题Word格式.docx》由会员分享，可在线阅读，更多相关《矩阵连乘问题Word格式.docx（16页珍藏版）》请在冰点文库上搜索。
由此可得P（n）的递归式如下：
1n=1
P（n）=
n>
1
解此递归方程可得，P（n）=C（n-1）,而C（n）是一个指数增长的函数。
因此穷举搜索法不是一个有效的算法。
以下将用三种方法来解决矩阵连乘问题的最优加括号方式以及最优解。
将矩阵连乘积
简记为A[i:
j]。
考察计算A[1:
n]的最优计算次序。
这个问题的一个关键特征是：
计算A[1:
n]的最优次序包含的计算矩阵子链A[1:
k]和A[k+1:
n]的次序也是最优的。
这是因为：
定义矩阵Ai的维数为pi-1×
pi,则A[i:
k]的计算次数为pi-1×
pk，A[k+1,j]的计算次数为pk×
pj，而这两个总的矩阵最后相乘时的计算量是固定的，为pi-1×
pk×
pj。
所以，矩阵连乘计算次序问题的最优解包含着其子问题的最优解。
这种性质称为最优子结构性质。
（1）、直接递归的思路：
记计算A[i:
j]，1≤i≤j≤n，所需最少数乘次数为m[i][j],则原问题的最优质为m[1][n]。
由分析得知：
m[i][j]可以递归的定义为：
0i=j
m[i][j]=
i<
j
m[i][j]给出了最优值，即计算A[i][j]所需的最少数乘次数。
同时还确定了计算A[i：
j]的最优次序中的断开位置k，也就是说，对于这个k有
m[i][j]=
若将对应于m[i][j]的断开位置k记s[i][j],在计算出最优值m[i][j]后，可递归地由s[i][j]构造出相应的最优解。
可以证明该算法的计算时间T（n）有指数下界，由算法的递归部分可得：
O
（1）n=1
T（n）≥
1+
1
因此，当n>
1时，T（n）≥n+2
据此，可用数学归纳法证明T（n）≥2n-1=
直接递归法的计算时间随n的增长指数增长。
（2）、备忘录方法的思路：
备忘录方法为每个子问题建立一个记录项，初始化时，该记录项存入一个特殊的值，表示该问题尚未求解。
在求解过程中，对每个待求的子问题，首先查看其相应的记录项。
若记录项中存储的是初始化时存入的特殊值，则表示该问题第一次遇到，此时计算出该子问题的解，并保存在相应的记录项中，以备以后查看。
若记录项中存储的不是初始化存入的特殊值，（比如初始化为-1，解答后赋值为0），则表示该问题已被计算过，其相应的记录项中存储的应该是该子问题的解答。
此时，只要从记录相中取出该子问题的解答即可，而不必重新计算。
备忘录方法的计算量：
因为是要计算m[i][j],因此只要从n个变量中任意选出2个分别作为i，j，则共有
种选法，即有
个子问题；
当i=j时有n种选法，所以总的子问题就为：
+n=
个。
每填入一个记录项，就要花费O（n）的时间，所以备忘录方法的时间复杂度为O（n3）。
（3）、动态规划方法的思路：
（以6个矩阵相乘为例）
m[i][j]
2
3
4
5
6
x
注意，在m[i][j]中，如果i>
j是没有意义的，因此在表格中都即为x；
而且，如果i=j，则代表单个矩阵，所以m[i][i]=1.
根据直接递归的方法的思路，如果要求m[i][j],就必须要求m[i][k]和m[k+1][j],根据m[i][j]的矩阵，则如果要求解m[1][2]，则需要知道m[1][1]和m[1][2]；
如果要求解m[1][3]，则要知道m[1][1]、m[1][2]和m[1][1]和m[2][3];
以此类推。
通过此规律可以总结出要求某一个元素，就要知道其左方的所有元素的值和其下方的所有元素的值。
动态规划就是按照上图所画的形式进行求解，从左下方求到右上方。
动态规划算法的计算量主要取决于程序中对行、列和加括号的位置k的三重循环。
循环体内的计算量为O
（1）,而三重循环的总次数为O（n3）。
因此该算法的计算时间上界为O（n3）。
和备忘录的算法的时间复杂度一样，都比直接递归的穷举搜索法有效得多。
（1）直接递归算法：
intRecurMatrixChain（inti,intj）
{
if（i==j）return0;
intu=RecurMatrixChain（i,i）+RecurMatrixChain（i+1,j）+p[i-1]*p[i]*p[j];
//递归，p[]为维数
s[i][j]=i;
//记录加括号的位置
for（intk=i+1;
k<
j;
k++）
{
intt=RecurMatrixChain（i,k）+RecurMatrixChain（k+1,j）+p[i-1]*p[k]*p[j];
//递归
if（t<
u）{u=t;
s[i][j]=k;
}//判断哪个值更小，选取哪个
}
return0;
}
（2）备忘录算法：
intMemoizedMatrixChain（intn,int**m,int**s）
for（inti=1;
i<
=n;
i++）
for（intj=i;
j<
j++）
m[i][j]=0;
//把m[i][j]的矩阵的上三角全部赋值为0。
returnLookupChain（1,n）;
intLookupChain（inti,intj）
if（m[i][j]>
0）returnm[i][j];
//如果是已经解决的问题，则标记记录项m[i][j]已经有值,且大于0，避免重复计算。
intu=LookupChain（i,i）+LookupChain（i+1,j）+p[i-1]*p[i]*p[j];
k++）{
intt=LookupChain（i,k）+LookupChain（k+1,j）+p[i-1]*p[k]*p[j];
if（t<
}//找最小值
m[i][j]=u;
returnu;
（3）动态规划算法：
voidMatrixChain（int*p,intn,int**m,int**s）
i++）m[i][i]=0;
for（intr=2;
r<
r++）
for（inti=1;
=n-r+1;
i++）{
intj=i+r-1;
//具体推导由来见下图
m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];
s[i][j]=i;
for（intk=i+1;
intt=m[i][k]+[k+1][j]+p[i-1]*p[k]*p[j];
if（t<
m[i][j]）{m[i][j]=t;
}//s[i][j]记录加括号的位置
}
}
下面的算法Traceback按算法MatrixChain计算出的断点矩阵s指示的加括方式输出计算A[i:
j]的最优计算次序：
voidTraceback（inti,intj,int**s）
if（i==j）return;
Traceback（i,s[i][j],s）;
//递归地对左边进行加括号
Traceback（s[i][j]+1,j,s）;
//递归地对右边进行加括号
cout<
<
"
MultiplyA"
i"
s[i][j];
andA"
（s[i][j]+1）<
"
endl;
//输出最优值和最优解。
程序源代码：
matrix.h
#include<
iostream>
usingnamespacestd;
#defineNUM100
intm[NUM][NUM],s[NUM][NUM],p[NUM];
//m[][]代洙?
表括?
最?
小?
数簓乘?
次?
数簓的?
矩?
阵ó
；
?
s[][]记?
录?
的?
是?
佳?
加ó
括ぁ?
号?
位?
置?
p[]表括?
示?
维?
数簓,A[i]的?
数簓为ap[i-1]×
á
p[i].
intn;
//备?
忘?
方?
法ぁ?
if（m[i][j]>
0）
{
returnm[i][j];
if（i==j）
return0;
intu=LookupChain（i,i）+LookupChain（i+1,j）+p[i-1]*p[i]*p[j];
for（intk=i+1;
k<
k++）
if（t<
u）
{
u=t;
s[i][j]=k;
//把?
m[i][j]的?
上?
三▂角?
全?
部?
赋3值μ为a0。
￡
//动ˉ态?
规?
划?
voidMatrixChain（）
{
m[i][i]=0;
r++）
intj=r+i-1;
m[i][j]=m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j];
for（intk=i+1;
{
inttemp=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
if（temp<
m[i][j]）
m[i][j]=temp;
s[i][j]=k;
//直±
接ó
递蘗归é
if（i==j）{return0;
//递蘗归é
，?
p[]为a维?
数簓
//记?
}//判D断?
哪?
个?
值μ更ü
选?
取?
voidTraceback（inti,intj）
if（i==j）//如?
果?
只?
有瓺一?
则ò
直±
输?
出?
A"
i;
elseif（i+1==j）//加ó
（A"
）"
;
else
（"
Traceback（i,s[i][j]）;
Traceback（s[i][j]+1,j）;
MatrixMultiply.cpp
#include"
matrix.h"
//intn;
//定¨
义?
一?
局?
变?
量?
intmain（）
L:
intchoice;
请输入相乘的矩阵的个数n="
cin>
>
n;
请输入第1个矩阵行数和第1个矩阵到第"
n<
个矩阵的列数：
for（inti=0;
cin>
p[i];
cout<
请选择矩阵连乘的算法:
1.备忘录算法"
2.直接递归算法"
3.动态规划算法"
4.重新输入矩阵"
5.退出程序"
请输入选择的编号：
choice;
while（choice!
=5）{
switch（choice）{
case1:
LookupChain（1,n）;
cout<
动态规划算法：
矩阵连乘的最优值为：
m[1][n]<
矩阵连乘的最优解为：
Traceback（1,n）;
break;
case2:
RecurMatrixChain（0,n）;
case3:
MatrixChain（）;
case4:
gotoL;
case5:
choice=4;
default:
运行结果：
升级会员 