admin 管理员组文章数量: 887053
矩阵链相乘问题【对维数为序列＜5, 10, 3, 12, 5, 50, 6＞的各矩阵，找出矩阵链乘积的一个最优加全部括号。】
题目【矩阵链相乘问题】
题解
用递推公式
m[i][j]表示为：
i=j时，m[i][j]填0；i>j时，m[i][j]为空；i<j时，求min。
后一级基于前一级dp出的最优解(每一级即与对角线平行的线)
i\j 1 2 3 4 5 6
1 0
2 0
3 0
4 0
5 0
6 0
----------------------------------------------
i=1,j=2：m[1][2]=min{0+0+5×10×3}=150；
i=2,j=3：m[2][3]=min{0+0+10×3×12}=360；
i=3,j=4：m[3][4]=min{0+0+3×12×5}=180；
i=4,j=5：m[4][5]=min{0+0+12×5×50}=3000；
i=5,j=6：m[5][6]=min{0+0+5×50×6}=1500；
i\j 1 2 3 4 5 6
1 0 150
2 0 360
3 0 180
4 0 3000
5 0 1500
6 0
------------------------------------------------
i=1,j=3：
m[1][3]
=min{m[1][1]+m[2][3]+p0p1p3，m[1][2]+m[3][3]+p0p2p3} //m[2][3]和m[1][2]就用前一级的360和150
=min{0+360+5×10×12，150+0+5×3×12}
=330；
i=2,j=4：
m[2][4]
=min{m[2][2]+m[3][4]+p1p2p4，m[2][3]+m[4][4]+p1p3p4} //m[3][4]和m[2][3]就用前一级的180和360
=min{0+180+10×3×5，360+0+10×12×5}
=330；
i=3,j=5：
m[3][5]
=min{m[3][3]+m[4][5]+p2p3p5，m[3][4]+m[5][5]+p2p4p5}//m[4][5]和m[3][4]就用前一级的3000和180
=min{0+3000+3×12×5，180+0+3×5×50}
=930；
i=4,j=6：
m[4][6]
=min{m[4][4]+m[5][6]+p3p4p6，m[4][5]+m[6][6]+p3p5p6}//m[5][6]和m[4][5]就用前一级的1500和3000
=min{0+1500+12×5×6，3000+0+12×50×6}
=1860；
i\j 1 2 3 4 5 6
1 0 150 330
2 0 360 330
3 0 180 930
4 0 3000 1860
5 0 1500
6 0
----------------------------------------------------------
i=1,j=4：
m[1][4]
=min{m[1][1]+m[2][4]+p0p1p4，m[1][2]+m[3][4]+p0p2p4，m[1][3]+m[4][4]+p0p3p4}
=min{0+330+5×10×5，150+180+5×3×5，330+0+5×12×5}
=min{580，405，630}
=405
i=2,j=5：
m[2][5]
=min{m[2][2]+m[3][5]+p1p2p5，m[2][3]+m[4][5]+p1p3p5，m[2][4]+m[5][5]+p1p4p5}
=min{0+930+10×3×50，360+3000+10×12×50，330+0+10×5×50}
=min{2430，9360，2830}
=2430
i=3,j=6：
m[3][6]
=min{m[3][3]+m[4][6]+p2p3p6，m[3][4]+m[5][6]+p2p4p6，m[3][5]+m[6][6]+p2p5p6}
=min{0+1860+3×12×6，180+1500+3×5×6，930+0+3×50×6
=min{2076，1770，1830}
=1770
i\j 1 2 3 4 5 6
1 0 150 330 405
2 0 360 330 2430
3 0 180 930 1770
4 0 3000 1860
5 0 1500
6 0
----------------------------------------------------------
i=1,j=5：
m[1][5]
=min{m[1][1]+m[2][5]+p0p1p5，m[1][2]+m[3][5]+p0p2p5，
m[1][3]+m[4][5]+p0p3p5，m[1][4]+m[5][5]+p0p4p5}
=min{0+2430+5×10×50，150+930+5×3×50，330+3000+5×12×50，405+0+5×5×50}
=min{4930，1830，6330，1655}
=1655
i=2,j=6：
m[2][6]
=min{m[2][2]+m[3][6]+p1p2p6，m[2][3]+m[4][6]+p1p3p6，
m[2][4]+m[5][6]+p1p4p6，m[2][5]+m[6][6]+p1p5p6}
=min{0+1770+10×3×6，360+3000+10×12×6，330+1500+10×5×6，2430+0+10×50×6}
=min{，4080，2130，5430}
=1950
i\j 1 2 3 4 5 6
1 0 150 330 405 1655
2 0 360 330 2430 1950
3 0 180 930 1770
4 0 3000 1860
5 0 1500
6 0
----------------------------------------------------------
终于到最后了，只要求出m[1][6]就可以了！
m[1][6]
=min{m[1][1]+m[2][6]+p0p1p6，m[1][2]+m[3][6]+p0p2p6，
m[1][3]+m[4][6]+p0p3p6，m[1][4]+m[5][6]+p0p4p6，m[1][5]+m[6][6]+p0p5p6}
=min{0+1950+5×10×6，150+1770+5×3×6，
330+1860+5×12×6，405+1500+5×5×6，1655+0+5×50×6}
=min{2250，2010，2550，2055，3155}
=2010
所以矩阵连乘的最小值m[1][6]=2010
此时，
m[1][6]=m[1][2]+m[3][6]+p0p2p6
m[3][6]= m[3][4]+m[5][6]+p2p4p6
画的括号为：(A1A2) ( (A3A4) (A5A6) )
核心代码：
void matrixChain(int p[], int m[][], int s[][])
//p用来记录矩阵，m[i][j]表示第i个矩阵到第j个矩阵的最优解，s[][]记录从哪里断开可以得到最优解
{int n = len - 1;for (int i = 1; i <= n; i++) // 初始化数组m[i][j] = 0;for (int r = 2; r <= n; r++) // 对角线循环{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]; // 找m[i][j]的最小值，初始化使k=i;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]){s[i][j] = k; // 在k位置断开得到最优解m[i][j] = t;}}}}
}本文标签： 矩阵链相乘问题对维数为序列＜5 10 3 12 5
版权声明：本文标题：矩阵链相乘问题【对维数为序列＜5, 10, 3, 12, 5, 50, 6＞的各矩阵，找出矩阵链乘积的一个最优加全部括号。】 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1717240329h694067.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论