动态规划矩阵连乘算法
- 格式:docx
- 大小:99.24 KB
- 文档页数:12
问题解析:由于矩阵乘法满足结合律,故计算矩阵的连乘积可以有许多不同的计算次序。
这种计算次序可以用加括号的方式来确定。
若一个矩阵连乘积的计算次序完全确定,也就是说该连乘积已完全加括号,则可以依此次序反复调用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<j时,若A[i:j]的最优次序在A k和A k+1之间断开,i<=k<j,则:m[i][j]=m[i][k]+m[k+1][j]+p i-1p k p j。
矩阵连乘问题的算法
一、矩阵连乘问题
矩阵连乘问题是指在矩阵计算中,给定n个矩阵,求这n个矩阵的连乘积的最优解问题。
矩阵连乘问题既可以用于组合优化,也可以用于信息处理系统中查找最优路径的搜索算法。
它是最基本的组合优化问题。
二、矩阵连乘问题的算法
1. 动态规划法:动态规划法是求解矩阵连乘问题的常用算法。
它采用递归方法,将原问题分解为若干个子问题,然后求出各子问题的最优解,最后组合出原问题的最优解。
2. 贪心算法:贪心算法是一种经典的最优化算法,也可以用于求解矩阵连乘问题,即通过某种启发式规则,在每一步中都使最优决策,最终得到最优解。
3. 分支定界法:分支定界法是一种由搜索算法和界定法相结合而成的最优化算法,也可以用于求解矩阵连乘问题。
该算法按照树状的层次结构,向下搜索一个在每一步骤都使得当前最优的路径,然后上溯形成最优解。
4. 模拟退火算法:模拟退火算法是一种搜索算法,它可以用于求解矩阵连乘问题。
它采用一种模拟物理过程的原理,通过不断地改变解的状态,以求出相对最优解。
- 1 -。
矩阵连乘问题(动态规划算法)动态规划算法思想简介:将⼀个问题分解为多个⼦问题,这点和分治法类似,但是每个⼦问题不是独⽴的⽽是相互联系的,所以我们在求解每个⼦问题的时候可能需要重复计算到其他的⼦问题,所以我们将计算过的⼦问题的解放进⼀个表中,这样就能避免了重复计算带来的耗费,这就是动态规划的基本思想;⼀般地,动态规划思想⼀般⽤来解最优化问题,主要分为以下四个步骤:(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;}可结合我的另⼀篇关于贪⼼算法的博客进⾏⽐较,了解这两者的区别;。
动态规划法解矩阵连乘问题实验内容给定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))实验总结在这次实验中懂得了动态规划法运用方法和解题思路的重要性,在这个程序中如何 建立动态规划的过程建立递归过程 保存已解决的子问题答案。
动态规划之矩阵连乘卓淑琴(安徽中医学院医药信息工程;安徽合肥 230009)摘要:动态规划是求解最优化问题的一种方法,该文主要研究其求解问题的基本思想及其具体步骤,详细分析其用于矩阵连乘问题上的算法设计。
关键词:动态规划,矩阵连乘,最优解中图分类号:TP360.1 文献标识码:AThe dynamic programming of matrix continuous multiplyZHUO Shu -qin(Medical information engineering institute An Hui University of Traditional Chinese Medicine, Hefei230009 Anhui)Abstract:The dynamic programming optimization problem solving is a kind of method, this paper mainly studies the basic idea of solving problem and its specific steps, and a detailed analysis on the matrix continuous multiply on the question of the algorithm design.Key words: Dynamic programming; Matrix continuous multiply ;The optimal solution.0.引言动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。
20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,提出了著名的最优化原理(principle of optimality),把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法——动态规划。
算法设计与分析——矩阵连乘问题(动态规划)⼀、问题描述引出问题之前我们先来复习⼀下矩阵乘积的标准算法。
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个要相乘的矩阵构成的序列(链)<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]⼤⼩。
矩阵连乘问题是一个经典的优化问题,其目标是在给定一组矩阵和它们之间的乘法顺序下,找出最少的括号方案数,使得乘法操作可以按照给定的顺序进行。
假设有n个矩阵A1, A2, ..., An,我们需要计算它们的连乘积。
每个矩阵Ai都有m×m的元素。
矩阵连乘问题可以转化为以下动态规划问题:
1. 定义dp[i][j]为计算矩阵Ai到Aj的连乘积所需的最少括号方案数。
2. 初始化dp[i][i]=0,表示单个矩阵不需要任何括号。
3. 对于i<j,计算dp[i][j]的递推关系:
dp[i][j] = dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j],其中k=i,...,j-1。
其中p是任意一个正整数,表示矩阵的维度m。
4. 最终答案为dp[1][n]。
以下是Python代码实现:
计算结果为:最少需要15个括号方案数。
动态规划之矩阵连乘【问题描述】给定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个矩阵构成的序列{A1,A2,...,An},对乘积A1A2...An,找到最⼩化乘法次数的加括号⽅法。
1)寻找最优⼦结构此问题最难的地⽅在于找到最优⼦结构。
对乘积A1A2...An的任意加括号⽅法都会将序列在某个地⽅分成两部分,也就是最后⼀次乘法计算的地⽅,我们将这个位置记为k,也就是说⾸先计算A1...Ak和Ak+1...An,然后再将这两部分的结果相乘。
最优⼦结构如下:假设A1A2...An的⼀个最优加括号把乘积在Ak和Ak+1间分开,则前缀⼦链A1...Ak的加括号⽅式必定为A1...Ak的⼀个最优加括号,后缀⼦链同理。
⼀开始并不知道k的确切位置,需要遍历所有位置以保证找到合适的k来分割乘积。
2)构造递归解设m[i,j]为矩阵链Ai...Aj的最优解的代价,则3)构建辅助表,解决重叠⼦问题从第⼆步的递归式可以发现解的过程中会有很多重叠⼦问题,可以⽤⼀个nXn维的辅助表m[n][n] s[n][n]分别表⽰最优乘积代价及其分割位置k 。
辅助表s[n][n]可以由2种⽅法构造,⼀种是⾃底向上填表构建,该⽅法要求按照递增的⽅式逐步填写⼦问题的解,也就是先计算长度为2的所有矩阵链的解,然后计算长度3的矩阵链,直到长度n;另⼀种是⾃顶向下填表的备忘录法,该⽅法将表的每个元素初始化为某特殊值(本问题中可以将最优乘积代价设置为⼀极⼤值),以表⽰待计算,在递归的过程中逐个填⼊遇到的⼦问题的解。
动态规划实现矩阵链乘法问题矩阵链乘法问题( matrix-chain multiplication problem ) (1)问题描述 给定n个矩阵的链<A 1 ,A 2 ,…,A n >,其中i=1,2,…,n,矩阵A i的维数为p i-1 ×p i。
求⼀个完全“括号化⽅案”,使得计算乘积A 1 A 2 …A n 所需的标量乘法次数最⼩ (2)最优括号化⽅案的结构特征 ⽤记号 A i,j表⽰ A i A i+1 …A j通过加括号后得到的⼀个最优计算模式,且恰好在A k与A k+1之间分开。
则“前缀”⼦链A i A i+1 …A k必是⼀个最优的括号化⼦⽅案,记为A i,k;同理“后缀”⼦链A k+1 A k+2 …A j也必是⼀个最优的括号化⼦⽅案,记为A k+1,j。
(3)⼀个递归求解的⽅案 对于矩阵链乘法问题,我们将所有对于1≤i≤j≤n确定A i A i+1 …A j的最⼩代价括号⽅案作为⼦问题。
令m[i,j]表⽰计算矩阵A i,j所需要的标量乘法的次数最⼩值,则最优解就是计算A i...n所需的最低代价就是m[1,n] 递归定义m[i,j]。
①对于i=j的情况下,显然有m=0,不需要做任何标量乘法运算。
所以,对于所有的i=1、2......n,m[i,i] = 0. ②当i < j的情况,就按照最优括号化⽅案的结构特征进⾏计算m[i,j]。
假设最优括号化⽅案的分割点在矩阵A k和A k+1之间,那么m的值就是A i...k和A k+1...j的代价加上两者量程的代价的最⼩值。
即。
该公式的假设是最优分割点是已知的,但是实际上不知道。
然⽽,k只有j-i中情况取值。
由于最优分割点k必定在i~j内取得,只需要检查所有可能的情况,找到最优解即可。
可以得出⼀个递归公式 m只是给出了⼦问题最优解的代价,但是并未给出构造最优解的⾜够信息(即分割点的位置信息)。
所以,在此基础之上,我们使⽤⼀个⼆维数组s[i,j]来保存 A i A i+1 …A j 的分割点位置k。
矩阵连乘问题【问题】:矩阵链乘问题:给定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<iostream.h>#include<stdlib.h>#include<limits.h>#include<time.h>#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<n;d++)for(int i=1;i<=n-d;i++){ int j=i+d;c[i][j]=INT_MAX;for(int m=i;m<j;m++){ int t=c[i][m]+c[m+1][j]+p[i-1]*p[m]*p[j];if(t<c[i][j]){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"<<i;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<j;k++){int t=lookupchain(i,k)+lookupchain(k+1,j)+p[i-1]*p[k]*p[j];if(t<u){u=t;s[i][j]=k;}}c[i][j]=u;return u;}void main(){srand((int)time(NULL));for(int i=0;i<N;i++) // 随机生成数组p[],各个元素的值的范围:1~MAX_VALUE p[i]=random()+1;clock_t start,end;double elapsed;start=clock();//cout<<"Count: "<<matrixchain(N-1)<<endl; //3重for循环实现cout<<"Count: "<<lookupchain(1,N-1)<<endl; //备忘录方法end=clock();elapsed=((double)(end-start));///CLOCKS_PER_SEC;cout<<"Time: "<<elapsed<<endl;Print(s,1,N-1); //输出矩阵连乘积的计算次序cout<<endl;}【总结】:两种算法的时间复杂度均为o(n3),,随着数据量的增多,备忘录方法消耗的时间越长;我觉得是由于递归算法,随着数据量增大,调用函数的次数也增大,语句被执行的时间也越多,因此调用函数消耗的时间也增多。
矩阵连乘算法
矩阵连乘是指将多个矩阵相乘的计算过程。
例如,对于三个矩阵A,B,C,其连乘结果可以表示为:A x B x C。
矩阵连乘算法是一个动态规划算法,用于寻找最优的矩阵连乘顺序,从而实现最小化矩阵乘法的操作次数。
该算法的基本思想是从最小的子问题开始逐步递推,找到最佳的矩阵连乘顺序。
具体实现过程如下:
1. 定义一个二维数组m[][],其中m[i][j]表示从第i个矩阵到第j个矩阵的最小操作次数。
2. 对于每个长度为1的子序列,即i=j的情况,m[i][j]=0。
3. 对于每个长度大于1的子序列,即i<j的情况,计算m[i][j]的值,其中k是一个中间点,它将序列分为两个子序列:i到k和k+1到j。
用以下公式更新
m[i][j]的值:
m[i][j] = min{m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]}
其中p[]为矩阵的维数,p[i-1]表示第i个矩阵的行数,p[i]表示第i个矩阵的列
数,p[j]表示第j个矩阵的列数。
4. 最后,m[1][n]的值即为矩阵连乘的最小操作次数。
该算法的时间复杂度为O(n^3),其中n为矩阵的个数。
实现矩阵连乘的动态规划算法1.计算连个矩阵乘积的标准算法://标准算法void MatrixMultiply(int a[][MAXN], int b[][MAXN], int p, int q, int r){int sum[MAXN][MAXN];memset(sum, 0, sizeof(sum));int i, j, k;//遍历矩阵a的⾏for (k = 0; k < p; k++){//遍历矩阵b的列for (j = 0; j < r; j++){//对应位置相乘for (i = 0; i < q; i++){sum[k][j] += a[k][i] * b[i][j];}}}}所以A、B两个矩阵相乘的计算量为p*q*r。
2. 计算连个矩阵乘积的动态规划算法:#include<stdio.h>#include<stdlib.h>#include<Windows.h>#define MAX 100int matrix_chain(int *p, int n, int **m, int **s){//a[][]最⼩乘次数//s[][]最⼩乘数时的断开点int i,j,r,k;for (i = 0; i < n; i++) //单⼀矩阵的最⼩乘次都置为0{m[i][i] = 0;}for (r = 2; r <= n; r++) //r为连乘矩阵的个数{for (i = 0; i <= n-r; i++) //i表⽰连乘矩阵中的第⼀个{j = i + r -1; //j表⽰连乘矩阵中的最后⼀个m[i][j] = 99999;for (k = i; k <= j-1; k++) //在第⼀个与最后⼀个之间寻找最合适的断开点,注意,这是从i开始,即要先计算两个单独矩阵相乘的乘次{int tmp = m[i][k] + m[k+1][j] + p[i]*p[k+1]*p[j+1];if (tmp < m[i][j]){m[i][j] = tmp;s[i][j] = k;}}}}return m[0][n-1];}void print_chain(int i, int j, char **a,int **s){ //递归的⽅式来把最⼩乘数的表达式输出if (i == j){printf("%s",a[i]);}else{printf("(");print_chain(i,s[i][j],a,s);print_chain(s[i][j]+1,j,a,s);printf(")");}}int main(){//min_part[i][j]存储的是i+1到j+1的最⼩乘次,因为是从0开始//min_point[i][j]存储的是i+1到j+1之间最⼩乘次时的分割点int *p, **min_part, **min_point;char **a;int n = 6,i;int ret;p = (int *)malloc((n+1)*sizeof(int));a = (char **)malloc(n*sizeof(char*));min_part = (int **)malloc(n*sizeof(int *)); min_point = (int **)malloc(n*sizeof(int *));for (i = 0; i < n; i++){min_part[i] = (int *)malloc(n*sizeof(int)); min_point[i] = (int *)malloc(n*sizeof(int));a[i] = (char *)malloc(n*sizeof(char));}p[0] = 30; //第⼀个矩阵的⾏数p[1] = 35; //第⼆个矩阵的⾏数p[2] = 15; //……p[3] = 5; //……p[4] = 10; //……p[5] = 20; //第六个矩阵的⾏数p[6] = 25; //第六个矩阵的列数a[0] = "A1";a[1] = "A2";a[2] = "A3";a[3] = "A4";a[4] = "A5";a[5] = "A6";ret = matrix_chain(p,n,min_part,min_point); printf("Minest times:%d.\n",ret);print_chain(0,n-1,a,min_point);printf("\n");free(p);free(min_part);free(min_point);free(a);system("pause");return 0;}3.递归加括号的过程的运算量://加括号的过程是递归的。