动态规划——矩阵连乘的问题
《问题的引出》
看下面一个例子，计算三个矩阵连乘{A1，A2，A3}；维数分别为10*100 , 100*5 , 5*50 按此顺序计算需要的次数（（A1*A2）*A3）:10X100X5+10X5X50=7500次
按此顺序计算需要的次数（A1*（A2*A3））:10X5X50+10X100X50=75000次
所以问题是：如何确定运算顺序，可以使计算量达到最小化。
枚举显然不可，如果枚举的话，相当于一个“完全加括号问题”，次数为卡特兰数,卡特兰数指数增长，必然不行。
《建立递归关系》
子问题状态的建模（很关键）：令m[i][j]表示第i个矩阵至第j个矩阵这段的最优解。
显然如果i=j，则m[i][j]这段中就一个矩阵，需要计算的次数为0；
如果i>j，则m[i][j]=min{m[i][k]+m[k+1][j]+p[i-1]Xp[k]Xp[j]},其中k,在i与j 之间游荡，所以i<=k 代码实现时需要注意的问题：计算顺序！！！ 因为你要保证在计算m[i][j]查找m[i][k]和m[k+1][j]的时候，m[i][k]和m[k+1][j]已经计算出来了。 观察坐标的关系如图： 所以计算顺序如上右图：相应的计算顺序对应代码为13-15行 m[1][n]即为最终求解，最终的输出想为（（A1（A2 A3））（（A4 A5）A6））的形式，不过没有成功，待思考... 1#include 2usingnamespace std; 3constint MAX = 100; 4//p用来记录矩阵的行列，main函数中有说明 5//m[i][j]用来记录第i个矩阵至第j个矩阵的最优解 6//s[][]用来记录从哪里断开的才可得到该最优解 7int p[MAX+1],m[MAX][MAX],s[MAX][MAX]; 8int n;//矩阵个数 9 10void matrixChain(){ 11for(int i=1;i<=n;i++)m[i][i]=0; 12 13for(int r=2;r<=n;r++)//对角线循环 14for(int i=1;i<=n-r+1;i++){//行循环 15int j = r+i-1;//列的控制 16 //找m[i][j]的最小值，先初始化一下，令k=i 17 m[i][j]=m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j]; 18 s[i][j]=i; 19//k从i+1到j-1循环找m[i][j]的最小值 20for(int k = i+1;k 21int temp=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]; 22if(temp 23 m[i][j]=temp; 24//s[][]用来记录在子序列i-j段中，在k位置处 25 //断开能得到最优解 26 s[i][j]=k; 27 } 28 } 29 } 30} 31 32//根据s[][]记录的各个子段的最优解，将其输出 33void traceback(int i,int j){ 34if(i==j)return ; 35 36 traceback(i,s[i][j]); 37 traceback(s[i][j]+1,j); 38 cout<<"Multiply A"< 40 41int main(){ 42 cin>>n; 43for(int i=0;i<=n;i++)cin>>p[i]; 44//测试数据可以设为六个矩阵分别为 45 //A1[30*35],A2[35*15],A3[15*5],A4[5*10],A5[10*20],A6[20*25] 46 //则p[0-6]={30,35,15,5,10,20,25} 47 //输入：6 30 35 15 5 10 20 25 48 matrixChain(); 49 50 traceback(1,n); 51//最终解值为m[1][n]; 52 cout< 53return0; 54} 第二种： #include #include #include #include #define MAX_VALUE 100 #define N 201 //连乘矩阵的个数(n-1) #define random() rand()%MAX_VALUE //控制矩阵的行和列的大小 int c[N][N], s[N][N], p[N]; int matrixchain(int n) //3个for循环实现 { for(int i=0;i c[i][i]=0;//自己根自己之间只有一个矩阵，无需计算为0 for(int L=2;L<=n;L++) for(int i=1;i<=n-L+1;i++)//i表第几个，后面减一调整下表从0开始的问题{ int j=i+L-1; c[i-1][j-1]=INT_MAX;//i-1因为下表从0开始 for(int k=i;k<=j-1;k++)//k全部断链试试，找最好的ij之间 { int q=c[i-1][k-1]+c[k][j-1]+p[i-1]*p[k]*p[j]; if(q { c[i-1][j-1]=q; s[i-1][j-1]=k; } } } return c[1][n];//最终计算到1到n之间总的计算量 } void Print(int s[][N],int i,int j) // 输出矩阵连乘积的计算次序 { if(i==j) printf("A%d",i); else { printf("("); Print(s,i,s[i][j]); // 左半部子矩阵连乘 Print(s,s[i][j]+1,j); //左半部子矩阵连乘 printf(")"); } } int lookupchain(int i,int j) //备忘录方法 { if(c[i][j]>0) return c[i][j]; if(i==j) return 0; int u=lookupchain(i,i)+lookupchain(i+1,j)+p[i-1]*p[i]*p[j]; s[i][j]=i; for(int k=i+1;k { int t=lookupchain(i,k)+lookupchain(k+1,j)+p[i-1]*p[k]*p[j]; if(t { u=t; s[i][j]=k; } } c[i][j]=u; return u; } int main() { srand((int)time(NULL)); for(int i=0;i p[i]=random()+1; clock_t start,end; double elapsed; start=clock(); //cout<<"Count: "< printf("Count: %d\n",lookupchain(1,N-1)); //备忘录方法 end=clock(); elapsed=((double)(end-start));///CLOCKS_PER_SEC; printf("Time: %d\n",elapsed); Print(s,1,N-1); //输出矩阵连乘积的计算次序 system("pause"); return 0; } 第三种： 矩阵连乘问题 【问题】：矩阵链乘问题：给定n个矩阵｛A1,A2,...,An｝，其中Ai与Ai+1是可乘的，i=1，2...，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。 【解题】：这里我采用的是动态划分算法： 设计动态规划算法的步骤。 (1)找出最优解的性质，并刻划其结构特征。 (2)递归地定义最优值。 (3)以自底向上的方式计算出最优值。 (4)根据计算最优值时得到的信息，构造最优解(由子结构的最优解得到原先大问题的最优解)。 【解题关键】：将一系列相乘的矩阵（Ai....Aj）划分为两部分;即（AiA i+1...A k）(A k+1A k+2....Aj)，k的位置要保证左边括号和右边括号相乘的消耗最小。 【思路】：这里我采用两种方法来实现： （1）用三重for循环来实现：根据主对角线的方向及其右边与之平行的对角线方向，由上至下，从左到右分别求出C[i][j]的值，后面要求的值都可以根据前面所求的的值来求。 C[i][j]代表矩阵链Ai..Aj相乘的最小消耗。其中：c[i][i]=0，i=1,2,....n 求解的顺序如下： C[1][2],C[2][3],C[2][3],...,C[N-1][N],C[1][3],C[2][4]....C[N-2][N]..........C[N][N] 最后得到的C[N][N]的值就是我们所求的。 （2）备忘录方法（即递归算法）：将整个矩阵链分成两部分，然后在分别对两边的子矩阵链递归调用算法。 【程序代码】：两种方法都在其中： #include #include #include #include #define MAX_VALUE 100 #define N 201 //连乘矩阵的个数(n-1) #define random() rand()%MAX_VALUE //控制矩阵的行和列的大小int c[N][N], s[N][N], p[N]; int matrixchain(int n) //3个for循环实现 { for(int k=1;k<=n;k++) c[k][k]=0; for(int d=1;d for(int i=1;i<=n-d;i++) { int j=i+d; c[i][j]=INT_MAX; for(int m=i;m { int t=c[i][m]+c[m+1][j]+p[i-1]*p[m]*p[j]; if(t { c[i][j]=t; s[i][j]=m; } } } return c[1][n]; } void Print(int s[][N],int i,int j) // 输出矩阵连乘积的计算次序 { if(i==j) cout<<"A"< else { cout<<"("; Print(s,i,s[i][j]); // 左半部子矩阵连乘 Print(s,s[i][j]+1,j); //左半部子矩阵连乘 cout<<")"; } } int lookupchain(int i,int j) //备忘录方法 { if(c[i][j]>0) return c[i][j]; if(i==j) return 0; int u=lookupchain(i,i)+lookupchain(i+1,j)+p[i-1]*p[i]*p[j]; s[i][j]=i; for(int k=i+1;k { int t=lookupchain(i,k)+lookupchain(k+1,j)+p[i-1]*p[k]*p[j]; if(t { u=t; s[i][j]=k; } } c[i][j]=u; return u; } void main() { srand((int)time(NULL)); for(int i=0;i clock_t start,end; double elapsed; start=clock(); //cout<<"Count: "< cout<<"Count: "< end=clock(); elapsed=((double)(end-start));///CLOCKS_PER_SEC; cout<<"Time: "< Print(s,1,N-1); //输出矩阵连乘积的计算次序 cout< } 【总结】：两种算法的时间复杂度均为o(n3)，,随着数据量的增多，备忘录方法消耗的时间越长；我觉得是由于递归算法，随着数据量增大，调用函数的次数也增大，语句被执行的时间也越多，因此调用函数消耗的时间也增多。 矩阵连乘最佳加括号方式－动态规划算法 一、问题描述 给定n个矩阵{A1,A2,…,A n}，其中A i与A i+1是可乘的，i=1,2,…,n-1。要算出这n个矩阵的连乘积A1A2…A n。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为： （1）单个矩阵是完全加括号的； （2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C 的乘积并加括号，即A=(BC)。 例如，矩阵连乘积A1A2A3A4有5种不同的完全加括号的方式：（A1（A2（A3A4））），（A1（（A2A3）A4）），（（A1A2）（A3A4）），（（A1（A2A3））A4），（（（A1A2）A3）A4）。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序，这决定着作乘积所需要的计算量。若A是一个p×q矩阵，B是一个q×r矩阵，则计算其乘积C=AB的标准算法中，需要进行pqr次数乘。 为了说明在计算矩阵连乘积时，加括号方式对整个计算量的影响，先考察3个矩阵 {A1,A2,A3}连乘的情况。设这三个矩阵的维数分别为10×100，100×5，5×50。加括号的方式只有两种：（（A1A2）A3），（A1（A2A3）），第一种方式需要的数乘次数为10×100×5＋10×5×50＝7500，第二种方式需要的数乘次数为100×5×50＋10×100×50＝75000。第二种加括号方式的计算量时第一种方式计算量的10倍。由此可见，在计算矩阵连乘积时，加括号方式，即计算次序对计算量有很大的影响。于是，自然提出矩阵连乘积的最优计算次序问题，即对于给定的相继n个矩阵{A1,A2,…,A n}（其中矩阵A i的维数为p i-1×p i，i＝1,2,…,n），如何确定计算矩阵连乘积A1A2…A n的计算次序（完全加括号方式），使得依此次序计算矩阵连乘积需要的数乘次数最少。 穷举搜索法的计算量太大，它不是一个有效的算法，本实验采用动态规划算法解矩阵连乘积的最优计算次序问题。 二、算法思路 动态规划——矩阵连乘的问题 《问题的引出》 看下面一个例子，计算三个矩阵连乘{A1，A2，A3}；维数分别为10*100 , 100*5 , 5*50 按此顺序计算需要的次数（（A1*A2）*A3）:10X100X5+10X5X50=7500次 按此顺序计算需要的次数（A1*（A2*A3））:10X5X50+10X100X50=75000次 所以问题是：如何确定运算顺序，可以使计算量达到最小化。 枚举显然不可，如果枚举的话，相当于一个“完全加括号问题”，次数为卡特兰数,卡特兰数指数增长，必然不行。 《建立递归关系》 子问题状态的建模（很关键）：令m[i][j]表示第i个矩阵至第j个矩阵这段的最优解。 显然如果i=j，则m[i][j]这段中就一个矩阵，需要计算的次数为0； 如果i>j，则m[i][j]=min{m[i][k]+m[k+1][j]+p[i-1]Xp[k]Xp[j]},其中k,在i与j 之间游荡，所以i<=k 所以计算顺序如上右图：相应的计算顺序对应代码为13-15行 m[1][n]即为最终求解，最终的输出想为（（A1（A2 A3））（（A4 A5）A6））的形式，不过没有成功，待思考... 1#include 矩阵连乘问题（动态规划） 一、实验目的与要求 1、明确矩阵连乘的概念。 2、利用动态规划解决矩阵连乘问题。 二、实验题： 问题描述： 给定n个矩阵｛A1,A2,...,An｝，其中Ai与Ai+1是可乘的，i=1，2...，n-1。确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。输入数据为矩阵个数和每个矩阵规模，输出结果为计算矩阵连乘积的计算次序和最少数乘次数。 三、实验代码 #include 矩阵连乘问题《算法分析与设计》 设计性实验报告 课程名称：《算法分析与设计》矩阵连乘问题实验题目：长：组员一：成 二：成员成员三：数学与计算机科学系别：系专业班级：指导教师：实验日期： 一、实验目的和要求 实验目的 熟悉动态规划算法设计思想和设计步骤，掌握基 本的程序设计方法，培养学生用计算机解决实际问题的能力。 实验要求 1、根据实验内容，认真编写源程序代码、上机调试程序，书写实验报告。 2、本实验项目考察学生对教材中核心知识的掌握程度和解决实际问题的能力。 3、实验项目可 以采用集中与分散实验相结合的方式进行，学生利用平时实验课时间和课外时间进行 实验，要求在学期末形成完整的项目程序设计报告。 二、实验内容提要 矩阵连乘问题给定n个矩阵{A,A,…,A}， 其中，Ai与Ai+1是可乘的，n21A,A,…,A。由于矩阵乘法满足结n-1。考查这n个矩阵的连乘积i=1,2，…，n12合律，故计算矩阵的连乘积可以有 许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反 复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可 递归地定义为： （1）单个矩阵是完全加括号的； （2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=（BC）。 三、实验步骤下面考虑矩阵连乘积的最优计算次序问题的动态规划方法。（1）分析最优解的结构（最优子结构性质）设计求解具体问题的动态规划算法的第一步是刻画该问 题的最优解结构特征。对于矩阵乘积的最优计算次序问题也不例外。首先，为方便起见，降- 1 - 矩阵乘积Ai Ai+1…Aj简记为A[i:j]。 问题描述：给定n个矩阵：A1,A2,...,A n，其中A i与A i+1是可乘的，i=1，2...，n-1。确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。输入数据为矩阵个数和每个矩阵规模，输出结果为计算矩阵连乘积的计算次序和最少数乘次数。 问题解析：由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。 完全加括号的矩阵连乘积可递归地定义为： （1）单个矩阵是完全加括号的； （2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC) 例如，矩阵连乘积A1A2A3A4有5种不同的完全加括号的方式：(A1(A2(A3A4)))，(A1((A2A3)A4))，((A1A2)(A3A4))，((A1(A2A3))A4)，(((A1A2)A3)A4)。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序，这决定着作乘积所需要的计算量。 看下面一个例子，计算三个矩阵连乘{A1，A2，A3}；维数分别为10*100 , 100*5 , 5*50 按此顺序计算需要的次数 ((A1*A2)*A3):10X100X5+10X5X50=7500次，按此顺序计算需要的次数(A1*(A2*A3)):10*5*50+10*100*50=75000次 所以问题是：如何确定运算顺序，可以使计算量达到最小化。 算法思路： 例：设要计算矩阵连乘乘积A1A2A3A4A5A6，其中各矩阵的维数分别是： A1：30*35; A2：35*15; A3：15*5; A4：5*10; A5：10*20; A6：20*25 递推关系： 设计算A[i:j]，1≤i≤j≤n，所需要的最少数乘次数m[i,j]，则原问题的最优值为m[1,n]。 当i=j时，A[i:j]=A i，因此，m[i][i]=0，i=1,2,…,n 当i 一、问题描述给定n个矩阵{A1,A2,…,An}，其中Ai与Ai+1是可乘的，i=1,2,…,n-1。要算出这n个矩阵的连乘积A1A2…An。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为：（1）单个矩阵是完全加括号的；（2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC)。例如，矩阵连乘积A1A2A3A4有5种不同的完全加括号的方式：（A1（A2（A3A4））），（A1（（A2A3）A4）），（（A1A2）（A3A4）），（（A1（A2A3））A4），（（（A1A2）A3）A4）。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序，这决定着作乘积所需要的计算量。若A是一个p×q矩阵，B是一个q×r矩阵，则计算其乘积C=AB 的标准算法中，需要进行pqr次数乘。为了说明在计算矩阵连乘积时，加括号方式对整个计算量的影响，先考察3个矩阵{A1,A2,A3}连乘的情况。设这三个矩阵的维数分别为10×100，100×5，5×50。加括号的方式只有两种：（（A1A2）A3），（A1（A2A3）），第一种方式需要的数乘次数为10×100×5＋10×5×50＝7500，第二种方式需要的数乘次数为100×5×50＋10×100×50＝75000。第二种加括号方式的计算量时第一种方式计算量的10倍。由此可见，在计算矩阵连乘积时，加括号方式，即计算次序对计算量有很大的影响。于是，自然提出矩阵连乘积的最优计算次序问题，即对于给定的相继n个矩阵{A1,A2,…,An}（其中矩阵Ai的维数为pi-1×pi，i ＝1,2,…,n），如何确定计算矩阵连乘积A1A2…An的计算次序（完全加括号方式），使得依此次序计算矩阵连乘积需要的数乘次数最少。穷举搜索法的计算量太大，它不是一个有效的算法，本实验采用动态规划算法解矩阵连乘积的最优计算次序问题。 二、算法思路动态规划算法的基本思想是将待求解问题分成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，动态规划法经分解得到的子问题往往不是相互独立的，前一子问题的解为后一子问题的解提供有用的信息，可以用一个表来记录所有已解决的子问题的答案，不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。本实验的算法思路是： 1、计算最优值算法MatrixChain()：建立两张表（即程序中的**m和**s，利用二维指针存放），一张表存储矩阵相乘的最小运算量，主对角线上的值为0，依次求2个矩阵、3个矩阵…、直到n个矩阵相乘的最小运算量，其中每次矩阵相乘的最小运算量都在上一次矩阵相乘的最小运算量的基础上求得，最后一次求得的值即为n个矩阵相乘的最小运算量；另 目录： 矩阵连乘问题： 1. 描述矩阵连乘问题 2. 分析矩阵连乘问题以及对递归式的推导（1）直接递归思路 （2）备忘录思路 （3）动态规划思路 3. 伪代码的方式描述算法： （1）直接递归算法 （2）备忘录算法 （3）动态规划算法 4. 把算法转换成程序实现的过程及结果（1）直接递归算法程序 （2）备忘录算法程序 （3）动态规划算法程序 1.描述矩阵连乘问题： 给定n 个矩阵{n A A A ?,2,1}，其中i A 和1+i A 是可乘的，i=1,2,…,n-1。考察这n 个矩阵的连乘积n A A A ?,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)的递归式如下： 1 n=1 P （n ）= ∑-=-1 1 )()(n k k n P k P n>1 解此递归方程可得，P(n)=C(n-1),而C(n)是一个指数增长的函数。因此穷举搜索法不是一个有效的算法。以下将用三种方法来解决矩阵连乘问题的最优加括号方式以及最优解。 2. 分析矩阵连乘问题以及对递归式的推导 将矩阵连乘积j i i A A A ?+,1,简记为A[i:j]。考察计算A[1:n]的最优计算次序。这个问题的一个关键特征是：计算A[1:n]的最优次序包含的计算矩阵子链A[1:k]和A[k+1:n]的次序也是最优的。这是因为：定义矩阵A i 的维数为p i-1×p i ,则A[i:k]的计算次数为p i-1×p k ，A[k+1,j]的计算次数为p k ×p j ，而这两个总的矩阵最后相乘时的计算量是固定的，为p i-1×p k ×p j 。所以，矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。 （1）、直接递归的思路：记计算A[i:j]，1≤i ≤j ≤n ，所需最少数乘次数为m[i][j],则原问题的最优质为m[1][n]。由分析得知：m[i][j]可以递归的定义为： 0 i=j m[i][j]= }]][1[]][[{min 1j k i j k i p p p j k m k i m -≤≤+++ i 华北电力大学科技学院 实验报告 实验名称矩阵连乘问题 课程名称计算机算法设计与分析 专业班级：软件12K1 学生姓名：吴旭 学号：121909020124 成绩： 指导老师：刘老师实验日期：2014.11.14 一、实验内容 矩阵连乘问题，给定n个矩阵{A1,A2,…,A n}，其中A i与A i+1是可乘的，i=1,2,3…,n-1。考察这n个矩阵的连乘A1,A2,…,A n。 二、主要思想 由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已经完全加括号，则可依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归的定义为： (1)单个矩阵是完全加括号的； (2)矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号 的矩阵连乘积B和C的乘积并加括号，即A=(BC)。 运用动态规划法解矩阵连乘积的最优计算次序问题。按以下几个步骤进行 1、分析最优解的结构 设计求解具体问题的动态规划算法的第1步是刻画该问题的最优解的结构特征。为方便起见，将矩阵连乘积简记为A[i:j]。考察计算A[1:n]的最优计算次序。设这个计算次序矩阵在A k和A k+1之间将矩阵链断开，1n,则其相应的完全加括号方式为((A1…A k)(A k+1…A n))。依此次序，先计算A[1:k]和A[k+1:n],然后将计 算结果相乘得到A[1:n]。 2、建立递归关系 设计动态规划算法的第二步是递归定义最优值。对于矩阵连乘积的最优计算次序问题，设计算A[i:j]，1i n，所需的最少数乘次数为m[i][j]，原问题的最优值为m[1][n]。 当i=j时，A[i:j]=A i为单一矩阵，无需计算，因此m[i][i]=0，i=1,2,…n。 当i 动态规划法解矩阵连乘问题 实验内容 给定n个矩阵{A1,A2,….An}，其中Ai与Ai+1是可乘的，i=1,2,3。。。，n-1。我们要计算这n个矩阵的连乘积。由于矩阵乘法满足结合性，故计算矩阵连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则我们可依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。 解题思路 将矩阵连乘积A(i)A(i+1)…A(j)简记为A[i:j]，这里 i <= j。考察计算A[i:j]的最优计算次序。设这个计算次序在矩阵A(k)和A(k+1)之间将矩阵链断开，i <= k < j, 则其相应完全加括号方式为(A(i)A(i+1)…A(k)) * (A(k+1)A(k+2)…A(j))。 特征：计算A[i:j]的最优次序所包含的计算矩阵子链 A[i:k]和A[k+1:j]的次序也是最优的。 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。 设计算A[i:j]，1 <= i <= j <= n，所需要的最少数乘次数m[i,j]，则原问题的最优值为m[1,n] 当i = j时，A[i:j]=Ai，因此，m[i,i] = 0，i = 1,2,…,n 当i < j时，m[i,j] = m[i,k] + m[k+1,j] + p(i-1)p(k)p(j)这里A(i)的维数为 p(i-1)*(i)(注：p(i-1)为矩阵A(i)的行数，p(i)为矩阵A[i]的列数) 实验 实验代码 #include 动态规划算法解矩阵连乘问题 一、实验目的 通过上机实验，要求掌握动态规划算法的问题描述、算法设计思想、程序设计和算法复杂性分析等。 二、实验环境 VC6.0 C++，vs2005 三、实验内容 1 用动态规划算法解矩阵连乘问题 （1）问题的描述 给定n个矩阵{A1,A2,…,A n}，其中A i与A i+1是可乘的，i=1,2,…,n-1。要算出这n个矩阵的连乘积A1A2…A n。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为： （1）单个矩阵是完全加括号的（当然实际上可以不加）； （2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC)。例如，矩阵连乘积A1A2A3A4有5种不同的完全加括号的方式：（A1（A2（A3A4））），（A1（（A2A3）A4）），（（A1A2）（A3A4）），（（A1（A2A3））A4），（（（A1A2）A3）A4）。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序，这决定着作乘积所需要的计算量。若A是一个p×q矩阵，B 是一个q×r矩阵，则计算其乘积C=AB的标准算法中，需要进行pqr次数乘。 （3）为了说明在计算矩阵连乘积时，加括号方式对整个计算量的影响，先考察3个矩阵{A1,A2,A3}连乘的情况。设这三个矩阵的维数分别为10×100，100×5，5×50。加括号的方式只有两种：（（A1A2）A3），（A1（A2A3）），第一种方式需要的数乘次数为10×100×5＋10×5×50＝7500，第二种方式需要的数乘次数为100×5×50＋10×100×50＝75000。第二种加括号方式的计算量时第一种方式计算量的10倍。由此可见，在计算矩阵连乘积时，加括号方式，即计算次序对计算量有很大的影响。于是，自然提出矩阵连乘积的最优计算次序问题，即对于给定的相继n个矩阵{A1,A2,…,A n}（其中矩阵Ai的维数为p i-1×p i，i＝1,2,…,n），如何确定计算矩阵连乘积A1A2…A n的计算次序（完全加括号方式），使得依此次序计算矩阵连乘积需要的数乘次数最少。正如课堂中所分析，穷举法的计算量太大，它不是一个有效的算法，本实验采用动态规划算法解矩阵连乘积的最优计算次序问题。 （2）算法设计思想 动态规划算法的基本思想是将待求解问题分成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，动态规划法经分解得到的子问题往往不是相互独立的，前一子问题的解为后一子问题的解提供有用的信息，可以用一个表来记录所有已解决的子问题的答案，不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。 湖南涉外经济学院计算机科学与技术专业 《算法设计与分析》课程 矩阵连乘备忘录算法 实验报告 班级： 学号： 姓名： 教师： 成绩： 2012年5月 【实验目的】 1 掌握动态规划算法和备忘录方法； 2 利用动态规划备忘录思想实现矩阵连乘； 3 分析实验结果，总结算法的时间和空间复杂度。思考是否能将算法的时间复杂度提高到 O(nlgn) 【系统环境】 Windows 07 平台 【实验工具】 VC++6.0中文企业版 【问题描述】 描述：给定n个矩阵{A1，A2，…，An}，其中Ai与Ai+1可乘的，i=1,2，…，n-1。找出这个n个矩阵的连乘A1A2…An所需相乘的最少次数的方式。 例：矩阵连乘积A1A2A3A4可以有一下五种不同的完全加括号方式： （A1（A2（A3A4））） （A1（（A2A3）A4）） （（A1A2）（A3A4）） （（A1（A2A3））A4） （（（A1A2）A3）A4） 【实验原理】 原理：1、矩阵连乘满足结合律，且不同的结合方式，所需计算的次数不同。 2、利用备忘录方法，用表格保存以解决的子问题答案，降低重复计算，提高效率。 思路：m初始化为0，表示相应的子问题还位被计算。在调用LookupChain时，若m[i][j]>0，则表示其中储存的是所要求子问题的计算结果，直接返回此结果即刻。否则与直接递归算法一样，自顶而下的递归计算，并将计算结果存入m[i][j]后返回。因此，LookupChain总能返回正确的值，但仅在它第一次被调用时计算，以后调用就直接返回计算结果。 方法：用MemorizedMatrixChain函数将已经计算的数据存入表中，用LookupChain函数配合MemorizedMatrixChain函数递归调用计算。 【源程序代码】 #include 福州大学数学与计算机科学学院 《计算机算法设计与分析》上机实验报告（2） i<=k 一。选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、在下列算法中有时找不到问题解的是（ B ）。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 5. 回溯法解旅行售货员问题时的解空间树是（B ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、下列随机算法中运行时有时候成功有时候失败的是（C ） A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法 11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法14．哈弗曼编码的贪心算法所需的计算时间为（ B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 一、选择题 1、衡量一个算法好坏的标准是（ C ）。 （A）运行速度快（B）占用空间少（C）时间复杂度低（D）代码短 2、记号O的定义正确的是（A）。 （A）O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤ f(n) ≤ cg(n) }；（B）O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤ cg(n) ≤ f(n) }；（C）O(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n≥n0 有：0 ≤f(n) 实训二 矩阵连乘问题的动态规划算法与实现 一、 设计目的 1） 掌握动态规划算法思想； 2） 掌握矩阵相乘问题的动态规划,得到矩阵相乘问题的最优解； 3） 进一步掌握动态规划法的基本思想和算法设计方法； 二、 设计内容 1． 任务描述 给定n 个矩阵｛A 1,A 2,…,A n ｝，其中A i 与A i +1是可乘的，i=1,2 ,…,n -1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。 A1 A2 A3 A4 A5 A6 30?35 35?15 15?5 5?10 10?20 20?25 2． 主要数据类型与变量 int p[MAX+1]//如任务描述记录30,35,15,5,10,20,25 m[MAX][MAX]//记录存储相乘次数的 s[MAX][MAX]; //记录从哪里断开的才可得到该最优解 int matrixCount;//矩阵个数 3． 算法或程序模块 void matrixChain(int p[21],int n,int m[20][20],int s[20][20]) 功能: 得到矩阵相乘问题的最优解 void Trackback(int i,int j,int s[20][20]) 功能: 按算法MatrixChain 计算出的断点矩阵s 指示的加括号方式输出计算A[i:j] 的最优计算次序。 任务分配 编 码 陈健翔 成绩 综合分数 测 试 朱敏 成绩 三、测试 找不到好的数据,呼呼就拿书上的例子测试吧！我把二维数组m也输出了看了一下,应该是可以的。检查下断开的点,也是正解。 测试多组数据： #include 矩阵连乘实验报告 ————————————————————————————————作者: ————————————————————————————————日期: ? 华北电力大学科技学院 实验报告 实验名称矩阵连乘问题 课程名称计算机算法设计与分析 专业班级：?软件12K１??学生姓名：吴旭 学号：1２1909０２0１２4 成绩: 指导老师: 刘老师?实验日期：2０１４．11.１4 一、实验内容 矩阵连乘问题,给定n个矩阵｛A1，A２,…，A n｝，其中A i与A i+1是可乘的,ｉ=1,2,3…,n-1。考察这n个矩阵的连乘A1,Ａ２,…,A n。 二、主要思想 由于矩阵乘法满足结合律,故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定,也就是说该连乘积已经完全加括号，则可依此次序反复调用２个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归的定义为: (1)单个矩阵是完全加括号的； (2)矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的 矩阵连乘积Ｂ和Ｃ的乘积并加括号，即Ａ=(BC)。 运用动态规划法解矩阵连乘积的最优计算次序问题。按以下几个步骤进行 1、分析最优解的结构 设计求解具体问题的动态规划算法的第1步是刻画该问题的最优解的结构特征。为方便起见，将矩阵连乘积简记为Ａ［i：j］。考察计算Ａ[1：ｎ]的最优计算次序。设这个计算次序矩阵在Aｋ和A k＋１之间将矩阵链断开,1≤k≤n,则其相应的完全加括号方式为((Ａ …A k)(Ａk+1…A n)）。依此次序，先计算A[１:k]和Ａ[k＋1:ｎ］,然后１ 宁波工程学院电信学院计算机教研室 实验报告 一、实验目的： 通过上级实验，要求掌握动态规划算法的问题描述，算法设计思想，程序设计和算法复杂性分析等。 二、实验环境：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个矩阵相乘的标准算法计算出矩阵连乘积。矩阵连乘最佳加括号方式-动态规划算法
矩阵连乘(数据结构)
矩阵连乘问题(动态规划)
矩阵连乘问题算法分析与设计
动态规划矩阵连乘算法
矩阵连乘问题
矩阵连乘问题
矩阵连乘实验报告
动态规划法解矩阵连乘问题
动态规划算法解矩阵连乘问题
矩阵连乘备忘录算法
矩阵连乘算法
算法分析复习题目及答案
算法分析复习题(含答案)
分治法_矩阵连乘问题
动态规划算法解矩阵连乘问题的源代码
矩阵连乘实验报告
矩阵连乘问题
相关主题
文本预览