《矩阵连乘算法(完整版)实用资料.doc》由会员分享，可在线阅读，更多相关《矩阵连乘算法(完整版)实用资料.doc（79页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、矩阵连乘算法（完整版）实用资料(可以直接使用，可编辑 完整版实用资料，欢迎下载）福州大学数学与计算机科学学院计算机算法设计与分析上机实验报告（2）i=kj,则：mij=mik+mk+1j+pi-1pkpj。由于在计算是并不知道断开点k的位置，所以k还未定。不过k的位置只有j-i个可能。因此，k是这j-i个位置使计算量达到最小的那个位置。综上，有递推关系如下：若将对应mij的断开位置k记为sij，在计算出最优值mij后，可递归地由sij构造出相应的最优解。sij中的数表明，计算矩阵链Ai:j的最佳方式应在矩阵Ak和Ak+1之间断开，即最优的加括号方式应为(Ai:k)(Ak+1:j)。从s1n记录
2、的信息可知计算A1:n的最优加括号方式为(A1:s1n)(As1n+1:n)，进一步递推，A1:s1n的最优加括号方式为(A1:s1s1n)(As1s1n+1:s1s1n)。同理可以确定As1n+1:n的最优加括号方式在ss1n+1n处断开.照此递推下去，最终可以确定A1:n的最优完全加括号方式，及构造出问题的一个最优解。3、动态规划迭代算法设计：用动态规划迭代方式解决此问题，可依据其递归式自底向上的方式进行计算。在计算过程中，保存已解决的子问题的答案。每个子问题只计算一次，而在后面需要时只需简单检查一下，从而避免了大量的重复计算，最终得到多项式时间的算法。4、算法代码：1. /3d1-2 矩
3、阵连乘 动态规划迭代实现2. /A1 30*35 A2 35*15 A3 15*5 A4 5*10 A5 10*20 A6 20*25 3. /p0-6=30,35,15,5,10,20,254. #include stdafx.h5. #include 6. using namespace std;7.8. const int L = 7;9.10. int MatrixChain(int n,int *m,int *s,int *p); 11. void Traceback(int i,int j,int *s);/构造最优解 12.13. int main()14. 15. int pL
4、=30,35,15,5,10,20,25;16.17. int *s = new int *L;18. int *m = new int *L;19. for(int i=0;iL;i+)20. 21. si = new intL;22. mi = new intL;23. 24.25. cout矩阵的最少计算次数为：MatrixChain(6,m,s,p)endl;26. cout矩阵最优计算次序为：endl;27. Traceback(1,6,s);28. return 0;29. 30.31. int MatrixChain(int n,int *m,int *s,int *p) 32.
5、 33. for(int i=1; i=n; i+)34. 35. mii = 0;36. 37. for(int r=2; r=n; r+) /r为当前计算的链长（子问题规模）38. 39. for(int i=1; i=n-r+1; i+)/n-r+1为最后一个r链的前边界40. 41. int j = i+r-1;/计算前边界为r，链长为r的链的后边界42.43. mij = mi+1j + pi-1*pi*pj;/将链ij划分为A(i) * ( Ai+1:j )44.45. sij = i;46.47. for(int k=i+1; kj; k+)48. 49. /将链ij划分为( A
6、i:k )* (Ak+1:j) 50. int t = mik + mk+1j + pi-1*pk*pj;51. if(tmij)52. 53. mij = t;54. sij = k;55. 56. 57. 58. 59. return m1L-1;60. 61.62. void Traceback(int i,int j,int *s)63. 64. if(i=j) return;65. Traceback(i,sij,s);66. Traceback(sij+1,j,s);67. coutMultiply Ai,sij;68. cout and A(sij+1),jB-D-HLP-S-U
7、O-B-E-H-L-P-S-U推广到x轴m段y轴n段的情形：用动态规划法需要做2mn+（m+n-2）次加法，mm次比较；而如果用穷举法，需要次加法， 次比较。若m=n, 动态规划法要做2n2 +2n-2次加法，n2 次比较，因此复杂度为O(n2) ;而穷举法需要次加法， 次比较 ，O(n2n+1)。第二小节 动态规划问题货郎担问题 1. 动态规划方法的思想- 动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。2. 货郎担问题：- 某售货员要到若干个村庄售货，各村庄之间的路程是已知的，为了提高效率，售货员决定从所在商店出发，到
8、每个村庄售一次货然后返回商店，问他应选择一条什么路线才能使所走的总路程最短？实质 - 从某点出发,遍历其余点,再回到原点,求总路径消耗最少的路线.例设共有4个要经过的点- -1，2，3，4-各个点之间的花费如下： 1-2 : 10; 1-3 : 15; 1-4 : 20; 2-1 : 5; 2- 3 : 9; 2- 4 : 10; 3-1 : 6; 3- 2 : 13; 3- 4 : 12; 4-1 : 8; 4- 2 : 8; 4- 3 : 9; （最短路径 ：1- 2-4-3-1） 1 2 3 42456758587853.问题的解决1.) 问题的描述:l T(V1; V) - 表示从V1
9、出发,经过顶点集合V中的点各一次,再回到点 V1的最短路径. 2.) 动态规划函数: T(vi; V) = mindij + T(vj ; V-vj) (vj 属于 V)l T(vi; V):就是 从V中任何一点vi出发, 经过V中的点各一次,再回到 点 vi的最短路径.l Dij:表示从点vi出发,到某点vj的耗费(有方向性).l 注:这是一个递归定义的函数,关键是每次的函数T(vi; V)它所处理的点 集逐渐减少.3.)实例:(如上图)求从v1出发的货郎担问题. 解: T(v1; V)= T(v1; v1, v2, v3, v4)= min d12 + T(v2; v3, v4),d13
10、+ T(v3; v2, v4), d14 + T(v4; v2, v3) /实例意义:初始的货郎担问题是从点v1出发,涉及其余3点v2,v3,v4;那按照动态规划“分而治之”的思想(这里就是把问题规模缩小,而问题的数量可多一些),我们可先计算分别从v2, v3, v4出发,涉及(v2, v3, v4)三点的三条货郎担路线的路耗,再各自加上相应的dij,这样,最后就得到3个总路耗,再做一个min运算,就可求出初始问题的解.T(v2; v3, v4)= min d23 + T(v3; v4), d24 + T(v4;v3)T(v3; v4)= d34 + T(v4, )T(v4; v3)= d43
11、 + T(v3, )T(v4, )= d41T(v3, )= d31T(v3; v4)= d34+ d41=6+9=15T(v4; v3)= d43+ d31=8+8=16T(v2; v3, v4)= min d23 + d34+ d41, d24 + d43+ d31= min 7+6+9, 6+8+8=22同理:T(v3; v2, v4)= min d32 + d24+ d41, d34 + d42+ d21= min 5+6+9, 6+5+4=15T(v4; v2, v3)= min d42 + d23+ d31, d43 + d32+ d21= min 5+7+8, 8+5+4=17则
12、最后: T(v1; v1, v2, v3, v4)= min d12 + T(v2; v3, v4),d13 + T(v3; v2, v4), d14 + T(v4; v2, v3) = min 2+22,5+15,8+17 =20所选的路线是:1-3-4-2-1第三小节 动态规划问题投资问题一 问题描述：投资问题就是考虑如何把有限资源分配给若干个工程的问题。二 给定条件：1.资源总数（设为a） 2.工程个数（设为n） 3.每项工程投资的利润（不同数目的投资所获得的利润不同），用向量Gi (1in)表示。 n三 问题求解：求出一个a的分划x1, x2,., xn,0xia, 且 xi a,使得
13、以下式表示的利润为最大： i=1 n G(a)= Gi (xj) 0xja i=1 其中Gi (xj)是把资源xj分配给第I项工程能获得的最大利润。四 问题分析： i）若Gi 是x的线性函数，则为线性规划问题。ii）若Gi 不是线性函数，则要用动态规划求最佳分配。用总量为a的资金在n个项目上进行投资以取得最大的利润，可以转化为下述的问题：将总量资金a分为两部分z(0za)及a-z，分别用在第n个项目及剩下的n-1个项目上进行投资，获得的最大利润G(a)=max(第n个项目上资金量为z的利润与用a-z的资金在n-1个项目上投资的最大利润之和)。这样问题就转化为”求用a-z的资金在n-1个项目上投
14、资的最大利润”，与我们的原问题” 求总量为a的资金在n个项目上进行投资以取得最大的利润”性质完全一致，仅仅是问题的规模比原问题少了一个项目，如此将问题的规模细化下去，一直到项目数为1为止，则问题迎刃而解。我们在对原问题进行”分而治之”的过程当中，最终实现了最优化的求解。五 问题解决方案：设fi(x)：前i个项目共投资资金x所产生的最大利润；di(x)：产生fi(x)在项目i上的资金数。由上分析可给出投资问题的动态规划函数方程：f1(x)= G1(x);d1(x)=x x=0,1afi(x)=maxGi(z)+ fi-1(x-z) z=0,1x; x=0,1adi(x)=产生fi(x)的z值 i
15、=2,3.n;六 问题举例：设有8（万元）的投资可分给3个项目，每个项目的利润函数如下表（一）所示： 表（一）利润函数表x0 1 2 3 4 5 6 7 8 G1(x)G2(x)G3(x)0 5 15 40 80 90 95 98 1000 5 15 40 60 70 73 74 750 4 26 40 45 50 51 52 53解题步骤：第1步：设项目1是可用于投资的唯一项目，把x万元投资到项目1，利润为 f1(x)= G1(x) 这就得到表（二）的最后一行的值，投资到项目1的最优数量为 d1(x)=x x=0,18；第二步：设资金8万元可投资到项目1和项目2。由第1步已知任意数量的资源投
16、资到项目1所产生的最优，所以下到各种和式中的最大值就是目前情况下的最大利润： G2(0)+ f1(8)=0+100=100 G2(1)+ f1(7)=5+98=103 G2(2)+ f1(6)=15+95=110G2(3)+ f1(5)=40+90=130 G2(4)+ f1(4)=80+60=140G2(5)+ f1(3)=70+40=110 G2(6)+ f1(2)=73+15=88G2(7)+ f1(1)=74+5=79 G2(8)+ f1(0)=75+0=75 可见将8万元投资于项目1和2 ，所能获得的最大利润f2(8)及投资到项目2的最优数量分别为：f2(8)=maxG2(z)+ f
17、1(8-z)=140 z=0,18d2(8)=4；第三步：假设以任意x(8)万元投资到项目1和2，对每个x值，计算从项目1和2所产生的最优利润，即：f2(x)=maxG2(z)+ f1(x-z) z=0,1x;投资到项目2的数量为d2(x)=产生f2(x)的z值。得到所表（二）的结果。第四步：将8万元投资于3个项目，这就是原问题。则f3(8)应取下述各量的最大值： G3(0)+ f2(8)=0+140=140 G3(1)+ f2(7)=4+120=124 G3(2)+ f2(6)=26+96=126G3(3)+ f2(5)=40+90=130 G3(4)+ f2(4)=45+80=125G3(
18、5)+ f2(3)=50+40=90 G3(6)+ f2(2)=51+15=66G3(7)+ f2(1)=52+5=57 G3(8)+ f2(0)=53+0=53 因此将8万元以最优方式投资到3个项目时所获得的最大利润及投资到项目3的分别为： f3(8) =G3(0)+ f2(8)=140 d3(8)=0； 表（二）向项目1，2投资所到的利润表x0 1 2 3 4 5 6 7 8 f1(x)d1(x)f2(x)d2(x)0 5 15 40 80 90 95 98 1000 1 2 3 4 5 6 7 8 0 5 15 40 80 90 95 120 1400 1 2 3 0 0 0 3 4 因
19、为d3(8)=0；故剩下8万元要最优的投资到项目1和2中。由表（二）易知，当项目1和2 可用时，d2(8)=4表示 投资到项目2的最优数量，因此项目1应投资剩下的4万元。第四小节 动态规划问题矩阵连乘积问题一、求矩阵的连乘积1、一个实际的例子（体现了乘积顺序对矩阵连乘的重要性）a) 例子 在讲这个问题之前先举个例子MA *B *C ，其中A=( aij)10*100 B=( bij)100*5 C=( cij)5*50根据矩阵乘法的结合律，则有M（A *B ）*C和MA *（B*C）两个方案但是可以发现他们所做的乘法的次数是不相同的以M（A *B ）*C为例令AB=M=(mij)10*5，因此
20、mij（其中,I=1,210；j1，25）故计算AB共进行了10*5*100=5000次乘法M= MC（其中,I=1,210；j1，250）故计算MC共进行了10*5*50=2500次乘法总共需要 500025007500次乘法同理，MA *（B*C）方案需要 100*5*50+10*100*50=25000+50000=75000次乘法，两者相差近十倍！B）结论不难得出，矩阵相乘的结合方式对计算结果所需要的乘法操作总数有很大的影响。但是M相乘的个数增多至n个，求出所有的可能结合方式的乘法操作次数，再从中找出操作次数最小的结合方式，其工作量是惊人的! 对于n个矩阵的连乘积，设有P（n）个不同的
21、计算次序。由于我们可以先在第k和k1个矩阵之间将原矩阵序列分为两个矩阵子序列，k1，2，n1。然后分别对这两个矩阵子序列完全加括号。最后对所得结果加括号，得到原矩阵序列得一种完全加括号方式。由此，可以得到关于P（n）得递归式如下：P（n）=1 , n=1时P（n） ，n1时解此递归方程可得，P（n）C（n1）其中，C（n）P（n）=P(1)P(n-1)+P(2)P(n-2)+P（n1）P（1）P（2）1P（n）这样的话这种枚举的方法实际上是不可能的。这里用动态规划的方法可以提供一种O（n3）的算法。如果可以找出乘法次数最少的的结合方式来计算的话，那么就减少了不少工作量。2、动态规划法求解的方案
22、（还是以一个实际的例子来讲动态规划法的算法）a） 算法分析举例最佳的乘积方案是（A1A2Ai）（AI1AI2An ）则A1A2Ai和AI1AI2An必须达到最佳。令mij为计算乘积AIAI1Aj的最少乘法数，显然有mij mii0， I，j1，2n其中mik是求AIAI1Ak乘积时最佳方案的乘积数目，m会1；j是求Ak1Ak2Aj乘积时的最佳方案的乘积数，AIAI1Ak是ri*rk+1阶矩阵，Ak1Ak2Aj是rk+1*rj+1矩阵，rirk+1 rj+1是求（AIAI1Ak）（Ak1Ak2Aj）所需的乘数法利用上式将之变为多段判决即可以计算以下4个矩阵为例A130*35，A235*15，A3
23、15*5，A45*10 n4为例m1230*35*15=1575030*35*15=15750m2335*15*5=2625m3415*5*10=750m13min m12+30*15*5, m23+30*35*5= min 15750+2250, 2625+5250=7875m24min m23+30*5*10, m34+35*15*10= min 2625+1750, 750+5250=4375m14min m12+ m34+30*15*10, m24+30*35*10, m13+30*5*10= min 15750+4500,4375+10500, 7875+30*5*10=9375故最
24、佳方案为：（A1（A2 A3）A4）J=1 2 3 4I=1 2 34 0m12m13m140m23m240m340B） 算法时间空间复杂性分析计算顺序是沿着对角线进行的。如果编程的话，程序如下（！c程序只供参考，不作为讲课内容）void MatrixChain (int p, int n, int n*m, int *s) for (int r=2; r=n; r+) for (int i=1; i=n-r+1; i=i+) int j=I+r-1; mij=mi+1j+Pi-1*pi*pj; sij=I; for (int k=i+1; kj; K+) int t=mik+mk+1j+pI
25、-1*pk*pj; if (tmij mij=t; sIj=k; 计算量主要取决于程序中对r，I，k的三重循环。循环体内的计算量为O（1），而三重循环的总次数为O(n3),由此该算法的计算时间上界为O(n3)，算法所占用的空间显然为 O(n2)，显然比穷举搜索法有效的多。二、动态规划的基本要素（综合讲过的几个例子,总结算法的基本要素）从以上的最优计算次序的动态规划算法可以看出，这些算法的有效性依赖于问题本身所具有的两个重要性质：最优子结构性质和子问题重叠性质。从一般意义上讲，问题所具有的这两个重要的性质是该问题可用动态算法求解的基本要素。1最优子结构设计动态规划算法的第一步通常是要刻画最优解的
26、结构。当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。问题的最优解子结构性质提供了该问题可用动态规划求解的重要线索。比如，在矩阵连乘积最优解计算次序问题中，我们注意到，若A1、A2An的最优完全加括号方式在Ak和AK1之间将矩阵链断开，则由此确定的子链A1、A2Ak和AK1、AK2An得完全加括号方式也最优。即该问题具有最优解子结构性质。在分析该问题得最优解导出得其子问题得解不是最优的，然后再设法说明在这个假设下可构造出一个比原问题最优解更好的解，从而导致矛盾。在动态规划算法中，问题的最优子结构性质使我们能够自底向上的方法递归的从子问题地最优解逐步构造出整个问题地最优解。同
27、时，它也使我们能在相对小的子问题空间中考虑问题。例如，在矩阵连乘积最优解次序问题中，子问题空间是输入地矩阵链的所有不同子链组成的。所有不同子链的个数为O（n2），因而子空间规模为O（n2）2重叠子问题可用动态规划算法求解问题应具备地另一基本要素是子问题地重叠性质。在用递归算法自顶向下解此问题时。每次产生地子问题并不总是新问题，有些子问题被反复计算多次。多态规划算法正式利用了这种子问题地重叠性质，对每个问题只解一次，尔后将其解保存在一个表格中，当再次需解此问题时，只是简单地用常数时间查看一下结果。通常，不同地子问题个数随输入问题地大小呈多项式增长。因此，用动态规划算法通常只需多项式时间，从而得较
28、高得解题效率。例如，搜索法和动态规划求解矩阵连乘法（这里略去具体）由此可以看出，在解某个问题得直接递归算法所产生得递归数中，相同的子问题反复出现，并且不同子问题的个数又相对减少时，用动态规划算法是有效的三、分治法和动态规划法的比较动态规划算法与分治法类似，其根本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解，与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。(! 这里严求真已经提过了)若用分治法来求解这类问题，则分解得到的子问题数目太多，以至于最后解原问题需耗费指数时间。然而，不同子问题的数目常常只有多项式量级。在用
29、分治法求解时，有些子问题被重计算了很多次。如果我们保存已解决子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，从而得到多项式时间的算法。为了达到这个目的，我们可以用一个表来记录所有已解决的子问题的答案。不管该子问题以后是否被用到，只要被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但他们具有相同的填表格式。 !！另外提一下（因为第五周的课上，石浩讲分治法求矩阵乘积时说无法看出分治法体现在哪里,后来在一本书上看到如下的解释）分治法中的矩阵乘法即Strassen矩阵乘法中。其分之思想是，将幂为2的矩阵A，B，C中每一个矩阵都分成4个大小
30、相等的子矩阵，每个矩阵都是(n/2)*(n/2)的方阵，由此可将方程CAB重写为分治法的基本思想是将一个矩阵为n的问题分解为k个规模较小的子问题，这些子问题的解合并得到原问题的解。参考资料：算法分析与设计 周培德 机械工业出版社 （教材）计算机算法设计与分析王晓东 电子工业出版社算法与复杂性 卢开澄 高等教育出版社计算机算法导引设计与分析 卢开澄 清华大学出版社计算机算法基础 余祥宣 崔国华 邹海明 华中科技大学出版社Visual C+技术交流汇螺旋矩阵群号：1、92782147 2、87423191 3、1262095221、我早期写的螺旋矩阵#include #include #inclu
31、de void main()int Num,Count20=0,k=1,i,Sum,j,Member1010=0,Mod=3,Line;int Row=0,Column=-1,f,x,y,Value=0;printf(请输入一个不大于10的数:);scanf(%d,&Num);f=Num;Sum=(Num-1)*2+1;Count0=Num;doNum-;for(i=0;i1);for(i=0;iSum;i+)Line=+Mod%4;for(j=0;jCounti;j+)Value+;switch(Line)case 0:Column+;MemberRowColumn=Value;break;
32、case 1:Row+;MemberRowColumn=Value;break;case 2:Column-;MemberRowColumn=Value;break;case 3:Row-;MemberRowColumn=Value;break;default:break;for(x=0;xf;x+)for(y=0;yf;y+)printf(%dt,Memberxy);printf(n);2、网上普遍的螺旋矩阵#include #define N 8main()int i,j,n=1,aNN;for(i=0;i=N/2;i+)for(j=i;jN-i;j+)aij=n+;for(j=i+1;ji;j-)aN-i-1j=n+;for(j=N-i-1;ji;j-)aji=n+;for(i=0;iN;i+)printf(nn);for(j=0;jN;j+)