动态规划算法学习十例之八
矩阵链乘法最优结合问题一、《问题的引出》
看下面一个例子，计算三个矩阵连乘{A1，A2，A3}；维数分别为10*100 , 100*5 , 5*50
按此顺序计算需要的次数（（A1*A2）*A3）:10X100X5+10X5X50=7500次
按此顺序计算需要的次数（A1*（A2*A3））:10X5X50+10X100X50=75000次
所以问题是：如何确定运算顺序，可以使计算量达到最小化。
二、问题描述
已知：给定n个矩阵构成的一个矩阵链(A1, A2, ..., An)，矩阵Ai的维数为pi-1×pi
求：决定该矩阵链的乘法结合顺序（即加括号），使得矩阵链乘法的运行时间最短
三、几个前提概念
矩阵链乘法的运行时间将以乘法（单行×单列）的次数来衡量
A是p×q矩阵，B是q×r矩阵，则A×B的运行时间为pqr
矩阵乘法满足结合律
四、首先判断是否具有最优子结构
假设Ai...Aj的矩阵链乘法的最优解是在Ak与Ak+1之间分开的，即(Ai...Ak)(Ak+1...Aj)，则子序列也必须是矩阵链乘法的最优解。
由此可知，问题的最优解包含子问题的最优解，满足最优子结构
五、递归表达式
设m为矩阵链Ai...Aj的乘法的最短运行时间，m即为问题所求的最优解的值
设s为运行时间为m时的k值，此函数用于递归构造最优解
递归表达式如下
http://dl.iteye.com/upload/attachment/0074/6358/771d675a-bd34-394f-88aa-89df7d458619.gif
其中矩阵Ai的维数为pi-1 x pi
六、然后进行自底向上的求解
矩阵m是一个上三角矩阵（不需要考虑i>j的情况），且对角线上的元素值均为0
由上面的递归表达式知，m的值只取决于m和m（k≥i且k＜j），
因此自底向上的求解过程实际是按子序列的长度递增来进行的
最后构造最优解
在推导过程中记录s的值，用于递归构造最优解（即矩阵链的圆括号添加顺序）
import java.util.Scanner; public class MatrixChain { private int[] p; private long[][] m; private int[][] s; public MatrixChain(int[] p,long[][] m,int[][] s){ this.p=p; this.m=m; this.s=s; } public long matrixChain() { int n = p.length - 1; for (int i = 1; i <= n; i++) { m = 0; } for (int r = 2; r <= n; r++) { for (int i = 1; i <= n - r + 1; i++) { int j = i + r - 1; m = m+m + p * p * p; s = i; for (int k = i + 1; k < j; k++) { long t = m + m + p * p * p; if (t < m) { m = t; s = k; } } } } return m; } publicvoid printResult(int i,int j)//输出最优加括号方式{ if(i==j) System.out.print("A"+i); else{ System.out.print("("); printResult(i,s); printResult(s+1,j); System.out.print(")"); } } public static void main(String[] args) { Scanner in=new Scanner(System.in); int n=in.nextInt()+1;//矩阵个数 int p[]=new int; for(int i=0;i<n;i++) p=in.nextInt();//矩阵维数 long m[][] = new long; int s[][] = new int; MatrixChain mc = new MatrixChain(p,m,s); System.out.println("最短运行时间="+mc.matrixChain()); for (int i = 1; i < n; i++) { for (int j = 1; j < n; j++) { System.out.print(m + " "); } System.out.println(); } System.out.println(); for (int i = 1; i < n; i++) { for (int j = 1; j < n; j++) { System.out.print(s+""); } System.out.println(); } System.out.println("最好的结合顺序"); mc.printResult(1,n-1); }}
两次运行：
C:\test>javaMatrixChain
4
50 10 40 30 5
最短运行时间=10500
0 20000 27000 10500
0 0 12000 8000
0 0 0 6000
0 0 0 0
0111
0022
0003
0000
最好的结合顺序
(A1(A2(A3A4)))
C:\test>javaMatrixChain
6
30 35 15 5 10 20 25
最短运行时间=15125
0 15750 7875 9375 11875 15125
0 0 2625 4375 7125 10500
0 0 0 750 2500 5375
0 0 0 0 1000 3500
0 0 0 0 0 5000
0 0 0 0 0 0
011333
002333
000333
000045
000005
000000
最好的结合顺序
((A1(A2A3))((A4A5)A6))
下载源码：
页:
[1]