动态规划课程设计(矩阵链乘问题)

矩阵连乘问题（动态规划算法）动态规划算法思想简介：将⼀个问题分解为多个⼦问题，这点和分治法类似，但是每个⼦问题不是独⽴的⽽是相互联系的，所以我们在求解每个⼦问题的时候可能需要重复计算到其他的⼦问题，所以我们将计算过的⼦问题的解放进⼀个表中，这样就能避免了重复计算带来的耗费，这就是动态规划的基本思想；⼀般地，动态规划思想⼀般⽤来解最优化问题，主要分为以下四个步骤：（1）找出最优解的性质，并刻画其结构特征；（2）递归地定义最优值；（3）以⾃底向上的⽅式计算出最优值；（4）根据计算得到的最优值时得到的信息，构造最优解；同时，问题的最优⼦结构性质也是该问题可⽤动态规划算法求解的显著特征，这⾥的最优⼦结构性质即指：问题的最优解也即代表着它的⼦问题有了最优解；问题描述：分析过程如下：（1）分析最优⼦结构的性质：（2）分析递归关系，以及利⽤⾃底向上的⽅式进⾏计算：（3）获取最优值和最优解：代码如下：#ifndef MATRIX_CHAIN_H#define MATRIX_CHAIN_Hvoid matrix_chain(int *p, int n, int **m, int **s);void traceback(int i, int j, int **s);#endif#include <iostream>#include "matrix_chain.h"using namespace std;//利⽤动态规划算法获取最优值void matrix_chain(int *p, int n, int **m, int **s) //p:各个矩阵的列数，n：矩阵个数，m：m[i:j]矩阵i到j的相乘次数，s:对应的分开位置{for (int i = 0; i < n; i++){m[i][i] = 0;}for (int r = 2; r <= n; r++){for (int i = 0; i < n - r + 1; i++){int j = i + r - 1;m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j];s[i][j] = i;for (int k = i + 1; k < j; k++){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;}}}}}//利⽤s[i][j]获取最优解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 A" << i << " , " << s[i][j];cout << "and A" << (s[i][j] + 1) << " , " << j << endl;}#include <iostream>#include "matrix_chain.h"using namespace std;int main(void){int matrix_num = 0; //矩阵个数cout << "请输⼊矩阵个数：" << endl;cin >> matrix_num;int **m = new int *[matrix_num];for (int i = 0; i < matrix_num; i++)m[i] = new int[matrix_num];int **s = new int *[matrix_num];for (int i = 0; i < matrix_num; i++)s[i] = new int[matrix_num];int *p = new int[matrix_num];cout << "请输⼊各矩阵的列数：" << endl;for (int i = 0; i < matrix_num; i++){cin >> p[i];}matrix_chain(p, matrix_num, m, s);traceback(0, matrix_num - 1, s);system("pause");return1;}可结合我的另⼀篇关于贪⼼算法的博客进⾏⽐较，了解这两者的区别；。

6.4多个矩阵连乘模块设计软件行业中客户总是在变更需求银行对我们公司开发的乘法模块还不满意。

他们的真实想法并不是实现两个矩阵的乘法，而是是能一次够实现多个矩阵按照算法运算法则的乘法，因此要求我们进一步改进我们的系统，实现多个矩阵的连乘功能，并且需要看到我们设计的程序能够满足他们的运行效率要求时才付二期款。

⏹给定n 个矩阵，其中与是可乘的，。

考察这n 个矩阵的连乘积⏹由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。

这种计算次序可以用加括号的方式来确定。

⏹若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积},...,,{21n A A A i A 1+i A 1,...,2,1-=n i nA A A (21)D C B A , , ,1050⨯=A 4010⨯=B 3040⨯=C 530⨯=D )))(((D BC A )))(((D C AB )))(((D BC A )))(((CD B A )))(((CD AB 16000, 10500, 36000, 87500, 34500◆设有四个矩阵，它们的维数分别是：◆总共有五中完全加括号的方式∑==qk kjikijba c 1⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡⨯⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡qr q q r r pq p p q q pr r n r r b b b b b b b b b a a a a a a a a a c c c c c c c c c 212222111211212222111211212222111211matrixMultiply(int[][]a,int[][]b,int[][]c,int ra,int ca,int rb,int cb){if(ca!=rb)Throw new IllegalArgumentException (“矩阵不可乘”);for(int i=0;i<ra;i++)for(int j=0;i<cb;j++){int sum=a[i][0]*b[0][j];for(int k=1;k<rb;k++)Sum+=a[i][k]*b[k][j];c[i][j]=sum;}对于p X q 矩阵A 和一个q X r 矩阵B , AB 需要？标准乘法计算.∑==qk kjikijba c 1⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡⨯⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡qr q q r r pq p p q q pr r n r r b b b b b b b b b a a a a a a a a a c c c c c c c c c 212222111211212222111211212222111211matrixMultiply(int[][]a,int[][]b,int[][]c,int ra,int ca,int rb,int cb){if(ca!=rb)Throw new IllegalArgumentException (“矩阵不可乘”);for(int i=0;i<ra;i++)for(int j=0;i<cb;j++){int sum=a[i][0]*b[0][j];for(int k=1;k<rb;k++)Sum+=a[i][k]*b[k][j];c[i][j]=sum;}对于p X q 矩阵A 和一个q X r 矩阵B , AB 需要？标准乘法计算.( A1X (A 2X A 3) )20 X 100 X 10 = 2000020 X 10 X 50 = 1000030000 次运算20 X 100 X 50 = 100000100X 10 X 50 = 50000150000 次运算如果A 1, A 2, and A 3是20X100, 100X10, 和10X50 矩阵,A 1X A 2X A 3乘积运算次数是多少?( (A 1X A 2) X A 3)矩阵连乘问题给定n个矩阵｛A1,A2,…,A n｝，其中A i与A i+1是可乘的，i=1,2 ,…,n-1。

动态规划法解矩阵连乘问题实验内容给定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]的列数)实验实验代码#in elude <iostream>#in elude <vector>using n amespaee std ;class matrix_cha in{public:matrix_eha in(const vector <int> & c){ cols = c ;count = cols.size (); mc.resize (co unt);s.resize (co unt);for (i nt i = 0; i < count; ++i) { mc[i].resize (co unt); s[i].resize (co unt);}for (i = 0; i < count; ++i) { for (int j = 0; j < count; ++j) { mc[i][j] = 0 ;s[i][j] = 0 ;//记录每次子问题的结果void lookup_cha in () {__lookup_cha in (1, count - 1);min_count = mc[1][co unt - 1];cout << "min _multi_co unt = "<< min_count << endl ;//输出最优计算次序__trackback (1, count - 1);}//使用普通方法进行计算void calculate () {int n = count - 1; //矩阵的个数// r表示每次宽度// i,j表示从从矩阵i到矩阵j// k表示切割位置for (i nt r = 2; r <= n; ++ r) {for (int i = 1; i <= n - r + 1; ++ i) {int j = i + r - 1 ;//从矩阵i到矩阵j连乘，从i的位置切割，前半部分为0mc[i][j] = mc[i+1][j] + cols[i-1] * cols[i] * cols[j];s[i][j] = i ;for (int k = i + 1; k < j; ++ k) {int temp = mc[i][k] + mc[k + 1][j] +cols[i-1] * cols[k] * cols[j];if (temp < mc[i][j]) {mc[i][j] = temp ;s[i][j] = k ;}} // for k} // for i} // for rmin_count = mc[1][ n];cout << "min _multi_co unt = "<< min_count << endl ;//输出最优计算次序__trackback (1, n);private:int __lookup_cha in (int i, i nt j) {//该最优解已求出，直接返回if (mc[i][j] > 0) {return mc[i][j];}if (i == j) {return 0 ; //不需要计算，直接返回}//下面两行计算从i到j按照顺序计算的情况int u = __lookup_cha in (i, i) + __lookup_cha in (i + 1, j)+ cols[i-1] * cols[i] * cols[j];s[i][j] = i ；for (int k = i + 1; k < j; ++ k) {int temp = __lookup_cha in (i, k) + __lookup_cha in(k + 1, j)+ cols[i - 1] * cols[k] * cols[j];if (temp < u) {u = temp ;s[i][j] = k ；}}mc[i][j] = u ;return u ;}void __trackback (int i, i nt j) {if (i == j) {return ;}__trackback (i, s[i][j]);__trackback (s[i][j] + 1, j);cout <<i << "," << s[i][j] << " " << s[i][j] + 1 << "," << j << endl;}private:vector<int> cols ; // 列数int count ; // 矩阵个数+ 1vector<vector<int> > mc; //从第i个矩阵乘到第j个矩阵最小数乘次数vector<vector<int> > s; //最小数乘的切分位置int min_count ; //最小数乘次数};int mai n(){//初始化con st i nt MATRIX_COUNT = 6 ;vectorvi nt> c(MA TRIX_COUNT + 1);c[0] = 30 ;c[1] = 35 ;c[2] = 15 ;c[3] = 5 ;c[4] = 10 ;c[5] = 20 ;c[6] = 25 ;matrix_cha in me (c); // mc.calculate (); mc」o okup_cha in (); return 0 ;}实验结果实验验证从s 可知计算顺序为((A1(A2A3))((A4A5))A6))实验总结在这次实验中懂得了动态规划法运用方法和解题思路的重要性，在这个程序中如何 建立动态规划的过程建立递归过程 保存已解决的子问题答案。

算法设计与分析——矩阵连乘问题（动态规划）⼀、问题描述引出问题之前我们先来复习⼀下矩阵乘积的标准算法。

int ra,ca;//矩阵A的⾏数和列数int rb,cb;//矩阵B的⾏数和列数void matrixMultiply(){for(int i=0;i<ra;i++){for(int j=0;j<cb;j++){int sun=0;for(int k=0;k<=ca;k++){sum+=a[i][k]*b[k][j];}c[i][j]=sum;}}}给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。

如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。

例如，给定三个连乘矩阵{A1，A2，A3}的维数分别是10*100，100*5和5*50，采⽤（A1A2）A3，乘法次数为10*100*5+10*5*50=7500次，⽽采⽤A1（A2A3），乘法次数为100*5*50+10*100*50=75000次乘法，显然，最好的次序是（A1A2)A3，乘法次数为7500次。

加括号的⽅式对计算量有很⼤的影响，于是⾃然地提出矩阵连乘的最优计算次序问题，即对于给定的相继n个矩阵，如何确定矩阵连乘的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。

⼆、问题分析矩阵连乘也是Catalan数的⼀个常⽤的例⼦，关于时间复杂度的推算需要参考离散数学关于Catalan的内容。

下⾯考虑使⽤动态规划法解矩阵连乘积的最优计算次序问题。

1、分析最优解的结构问题的最优⼦结构性质是该问题可以⽤动态规划求解的显著特征！！！2、建⽴递归关系3、计算最优值public static void matrixChain(int n) {for (int i = 1; i <= n; i++) {m[i][i] = 0;}for (int r = 2; r <= n; r++) {//i与j的差值for (int i = 1; i <= n - r + 1; i++) {int j = i + r - 1;m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j];s[i][j] = i;for (int k = i + 1; k < j; k++) {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;}}}}}4、构造最优解public static void traceback(int i, int j) {if (i == j) {System.out.printf("A%d", i); // 输出是第⼏个数据return;}System.out.printf("(");traceback(i, s[i][j]);// 递归下⼀个数据System.out.printf(" x ");traceback(s[i][j] + 1, j);System.out.printf(")");}三、总结。

一、实验目的通过本次实验，加深对动态规划算法的理解和应用，掌握解决矩阵连乘问题的方法，提高算法分析和设计能力。

二、实验原理矩阵连乘问题是指给定n个矩阵，每个矩阵都与它的前一个矩阵可乘，求计算这些矩阵连乘积的最优计算次序，以使计算过程中所需的数乘次数最少。

由于矩阵乘法满足结合律，因此可以通过加括号的方式确定不同的计算次序。

三、实验步骤1. 问题描述：给定n个矩阵A1, A2, ..., An，其中Ai与Ai-1是可乘的。

求计算矩阵连乘积A1A2...An的最优计算次序，使得计算过程中所需的数乘次数最少。

2. 输入数据：矩阵个数n，每个矩阵的规模。

3. 输出结果：计算矩阵连乘积的最优计算次序和最少数乘次数。

4. 算法设计：- 定义一个二维数组m[i][j]，其中m[i][j]表示计算矩阵AiAi-1...Aj的最少数乘次数。

- 初始化m[i][i] = 0，因为单个矩阵无需计算。

- 对于每个子问题A[i:j]，计算m[i][j]的最小值：- 遍历k从i到j-1，将问题分解为A[i:k]和Ak+1:j，计算m[i][k]和m[k+1][j]的和，并加上k个矩阵的维度乘积。

- 取上述和的最小值作为m[i][j]的值。

5. 递归关系：- 当i = j时，m[i][j] = 0。

- 当i < j时，m[i][j] = min(m[i][k] + m[k+1][j] + p[i-1]p[k]p[j])，其中k从i到j-1，p[i-1]表示矩阵Ai-1的行数，p[j]表示矩阵Aj的列数。

6. 自底向上计算：- 从m[1][1]开始，按照递归关系计算m[1][2]，m[1][3]，...，m[1][n]。

- 然后计算m[2][3]，m[2][4]，...，m[2][n]，以此类推，直到计算m[1][n]。

7. 输出最优计算次序：- 从m[1][n]开始，根据递归关系和子问题的最优解，逐步确定每个子问题的最优计算次序，直到得到整个问题的最优计算次序。

矩阵链乘法（动态规划）
⼀题意描述：
给定由n个要相乘的矩阵构成的序列（链）<A1,A2,A3,····A n>。

由于矩阵满⾜结合律（加括号⽅式表⽰结合⽅式），不同的计算⽅式导致的求出最终计算结果的代价相异，有的花的时间很少，有的⽅式所花时间很多，那么下⾯的任务就是求出算出结果所需要的最少时间及⼀个最优解。

⼆思路分析：
设p(n)表⽰⼀串n个矩阵可能的加全部括号⽅案数。

当n=1时，只有⼀个矩阵，此时p(1)=1。

当n>=2时，⼀个加全部括号的矩阵乘积等于两个加全部括号的⼦矩阵乘积的乘积，⽽且这两个⼦乘积之间的分裂可能发⽣在第k个和第k+1个矩阵之间，其中k=1，2，····，n-1;因此可以求得递归式：
1.找局部最优解：把问题：转化成两个最优⼦问题：及
2.构造递归解：
⾸先定义m[i,j]为解决⼦问题A[i....j]的最⼩计算次数，那么解决整个问题A[1,n]所花的最⼩时间为m[1,n]。

那么递归⽅程可以写成如下形式：
为了跟踪如何构造⼀个最优解我们可以定义s[i,j]为这样的⼀个k值，在该处分裂乘积后可得⼀个最优解。

3.构造函数进⾏求解
输出最优路径的函数⾃⼰编写，经过调⽤数组s[i][j]即可。

动态规划之矩阵链相乘问题（算法导论）问题描述：给定n个矩阵序列，(A1,A2,A3,A4,...,An). 计算他们的乘积：A1A2A3...An.由于矩阵的乘法运算符合结合律，因⽽可以通过调整计算顺序，从⽽降低计算量。

样例分析：⽐如有三个矩阵分别为：A1: 10*100,A2: 100*5,A3: 5*50假如现在按照(A1A2)A3的顺序计算需要的计算量为：10*100*5+10*5*50=7500次运算。

若按照A1(A2A3)的顺序计算，需要的计算量为：100*5*50+10*100*50=75000次运算。

上⾯两种不同的运算顺序所有的计算量相差⼗倍。

因⽽，⼀种最优的计算顺序将能很⼤程度的减少矩阵连乘的运算量。

问题解析：此问题的⽬的是寻找⼀种最优的括号化⽅案。

下⾯⽤动态规划的思想来进⾏分析：1、动态规划的第⼀步：寻找最优⼦结构。

为⽅便起见，使⽤Ai..j表⽰AiAi+1...Aj的乘积结果矩阵。

对于k(i<=k<j), 计算Ai..j所需要的计算量为：Ai..k 和 Ak+1..j 以及⼆者相乘的代价和。

2、设m[i][j]为Ai..j的最优计算顺序所要花费的代价。

则其求解公式为：if i == j, m[i][j] = 0; //因为只有⼀个矩阵时计算代码为0，即不需要计算。

m[i][j]=min{m[i][k] + m[k+1][j] + Pi-1PkPj} i<=k<j3、为了能够输出求解顺序，需要保存区间中的⼀些分割点。

假如Ai..j中的最优分割点为k，则我们使⽤s[i][j]=k。

即在Ai..j 中，分别计算Ai..k 和 Ak+1..j 所⽤的计算开销最⼩。

4、采⽤⾃底向上的表格法。

依次求解矩阵长度为2,3,...,n的最优计算顺序。

算法思想：1、对m[i][i]全部初始化为0.2、在矩阵链A1..n中，依次计算长度len为2,3,...,n的m[i][j]⼤⼩。

C语⾔矩阵连乘（动态规划）详解动态规划法题⽬描述：给定n个矩阵{A1,A2....An}，其中Ai与Ai+1是可以相乘的，判断这n个矩阵通过加括号的⽅式相乘，使得相乘的次数最少!以矩阵链ABCD为例按照矩阵链长度递增计算最优值矩阵链长度为1时，分别计算出矩阵链A、B、C、D的最优值矩阵链长度为2时，分别计算出矩阵链AB、BC、CD的最优值矩阵链长度为3时，分别计算出矩阵链ABC、BCD的最优值矩阵链长度为4时，计算出矩阵链ABCD的最优值动归⽅程：分析:k为矩阵链断开的位置d数组存放矩阵链计算的最优值，d[i][j]是以第i个矩阵为⾸，第j个矩阵为尾的矩阵链的最优值，i > 0m数组内存放矩阵链的⾏列信息，m[i-1]和m[i]分别为第i个矩阵的⾏和列（i = 1、2、3...）c语⾔实现代码：#include <stdio.h>#define N 20void MatrixChain(int p[N],int n,int m[N][N],int s[N][N]){int i,j,t,k;int r; //记录相乘的矩阵个数变量for(i=1;i<=n;i++){m[i][i]=0; //当⼀个矩阵相乘时，相乘次数为 0}//矩阵个数从两个开始⼀次递增for(r=2;r<=n;r++){//从某个矩阵开始for(i=1;i<=n-r+1;i++){//到某个矩阵的结束j=i+r-1;//拿到从 i 到 j 矩阵连乘的次数m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];//拿到矩阵连乘断开的位置s[i][j]=i;//寻找加括号不同，矩阵连乘次数的最⼩值，修改 m 数组，和断开的位置 s 数组for(k=i+1;k<j;k++){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;}}}}}int main(void){int n,n1,m1,i,j=2;int p[N]={0}; //存储矩阵的⾏和列数组int m[N][N]={0}; //存储矩阵与矩阵相乘的最⼩次数int s[N][N]={0}; //存储矩阵与矩阵相乘断开的位置printf("请输⼊矩阵个数:\n");scanf("%d",&n);for(i=1;i<=n;i++){printf("请输⼊第%d个矩阵的⾏和列(n1*m1 格式):",i);scanf("%d*%d",&n1,&m1);if(i==1){p[0]=n1;p[1]=m1;}else{p[j++]=m1;}}printf("\n记录矩阵⾏和列:\n");for(i=0;i<=n;i++){printf("%d ",p[i]);}printf("\n");MatrixChain(p,n,m,s);printf("\n矩阵相乘的最⼩次数矩阵为:\n");for(i=1;i<=n;i++){for(j=1;j<=n;j++){printf("%d ",m[i][j]);}printf("\n");}printf("\n矩阵相乘断开的位置矩阵为:\n");for(i=1;i<=n;i++){for(j=1;j<=n;j++){printf("%d ",s[i][j]);}printf("\n");}printf("矩阵最⼩相乘次数为:%d\n",m[1][n]);return 0;}感谢阅读，希望能帮助到⼤家，谢谢⼤家对本站的⽀持！。