矩阵连乘算法

1、福州大学数学与计算机科学学院计算机算法设计与分析上机实验报告（2）i<=k<j,则：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记录的信息可知计算A1:n的最优加括号方式为(A1:s1n)(As1

2、n+1:n)，进一步递推，A1:s1n的最优加括号方式为(A1:s1s1n)(As1s1n+1:s1s1n)。同理可以确定As1n+1:n的最优加括号方式在ss1n+1n处断开.照此递推下去，最终可以确定A1:n的最优完全加括号方式，及构造出问题的一个最优解。3、动态规划迭代算法设计：用动态规划迭代方式解决此问题，可依据其递归式自底向上的方式进行计算。在计算过程中，保存已解决的子问题的答案。每个子问题只计算一次，而在后面需要时只需简单检查一下，从而避免了大量的重复计算，最终得到多项式时间的算法。4、算法代码：1. /3d1-2 矩阵连乘 动态规划迭代实现2. /A1 30*35 A2 35*1

3、5 A3 15*5 A4 5*10 A5 10*20 A6 20*25 3. /p0-6=30,35,15,5,10,20,254. #include "stdafx.h"5. #include <iostream>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=30,

4、35,15,5,10,20,25;16.17. int *s = new int *L;18. int *m = new int *L;19. for(int i=0;i<L;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. ret

5、urn 0;29. 30.31. int MatrixChain(int n,int *m,int *s,int *p) 32. 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)

6、 * ( Ai+1:j )44.45. sij = i;46.47. for(int k=i+1; k<j; k+)48. 49. /将链ij划分为( Ai:k )* (Ak+1:j) 50. int t = mik + mk+1j + pi-1*pk*pj;51. if(t<mij)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. cout<<"Multiply A"<<i<<","<<sij;68. cout<<" and A"<<(sij+1)<<","&l