矩阵链乘问题

应用动态规划

给定n个矩阵的序列Ai ， 计算A1A2A3*...An. 矩阵乘法满足结合律，乘法的计算顺序不同，需要计算的次数就不同，

假设A1是pq的矩阵A2是qr的矩阵，那么计算A1A2的结果需要计算pq*r次计算A1A2A3 A1(10100) A2(1005) A3(550) 如果按照（A1A2)A3计算，需要计算次数是101005 + 105*50 = 7500次如果按照A1(A2A3)计算，需要计算次数是 100550 + 1010050 = 75000次不同的计算顺序计算效率可能会差10倍

矩阵链乘可以描述为：给定n个矩阵的链，给定一个括号化方案，使得矩阵乘法次数最少

动态规划的第一步是确定最优子结构

对Ai....Aj求最佳括号化，必然要在中间加一个分割点，原序列转化为两个子序列Ai..Ak , Ak+1..Aj 设d[i,j]表示计算链i~j所需的最小代价 原问题的代价 = Ai..Ak 的代价 + Ak+1..Aj + 两者相乘的代价 d[i][j] = d[i][k] + d[k+1][j] + p[k-1] * p[k] * p[k+1] k in (i,j) 如何利用最优子结构的性质 从子问题的最优解构造出原问题的最优解？ 每个子问题的求解都要划分链，找到子问题最优的划分点，然后将子问题的最优解合并起来。 设s[i，j]记录子链i~j的最优划分点的位置，那么s[1,n]将链划分为两个子链，如此递归的划分，就得到了原问题的最优划分方案，

状态转移代码

void MATRIX_CHAIN_ORDER() { for(int i=1;i<=n;i++) d[i][i] = 0; for(int l=1;l<n;l++) { for(int i=1;i+l<=n;i++) { int j = i+l; d[i][j] = INF; for(int k =i;k<j;k++) { int mid = d[i][k] + d[k+1][j] + p[k-1]*p[k]*p[k+1]; if(mid<d[i][j]) { d[i][j] = mid; s[i][j] = k; } } } } }

如此，计算出了每个区间的最优划分点。时间复杂度O(n^3)

最后一步：构造最优解

根据每个区间的最优划分点还原出结果

void mer(int x,int y) { if(x>y)return; if(x==y)printf("A%d",x); else { printf("("); mer(x,s[x][y]); printf("*"); mer(s[x][y]+1,y); printf(")"); } }

转载于:https://www.cnblogs.com/star-and-me/p/8642030.html