首页 > 代码库 > 动态规划-矩阵链乘法
动态规划-矩阵链乘法
问题描述：
给定由n个要相乘的矩阵构成的序列（链）<A1,A2,...,An>，要计算乘积A1A2...An，可以将两个矩阵相乘的标准算法作为一个子程序，通过加括号确定计算的顺序（对同一矩阵链，不同的计算顺序所需要的计算次数大不相同）。
目标问题：给定n个矩阵构成的矩阵链<A1,A2,...,An>，其中，i=1,2,...,n，矩阵Ai的维数为pi-1×pi，对乘积A1A2...An以一种最小计算次数加全部括号。
穷尽搜索：
令P(n)表示一串n个矩阵可能的加全部方案数。当n=1时，只有一种方案。当n>1时，一个矩阵链乘积变成两个子矩阵链乘积的乘积，分裂的地方可能发生在第k个矩阵和第k+1个矩阵之间，k=2,3,...,n-1。那么，P(n)=∑(k=2,3,...,n-1)P(k)*P(n-k)。这是关于n的指数形式，因此穷尽搜索不是好的策略。
动态规划：
1、寻找最优子结构
寻找最优子结构，利用这一子结构，根据子问题的最优解构造原问题的一个最优解。对于矩阵链相乘的问题，用Ai..j表示A1A2...An的求积结果，其中i≤j。对于某个k(1<k<j)，首先计算Ai..k和Ak+1..j，然后计算它们相乘最终得到Ai..j。计算Ai..j的代价就是计算Ai..k和Ak+1..j的代价之和，再加上两者相乘的代价。
最优子结构如下：
假设AiAi+1...Aj的最优加括号方式在k和k+1处分开，则对前缀子链AiAi+1...Ak的加括号必须是一个最优加括号，为什么呢？如果存在有对AiAi+1...Ak有一个更优的加括号，那么会产生一个对AiAi+1...Aj的更优加括号，这与假设矛盾。同理，后缀子链Ak+1Ak+2...Aj也必须是一个最优加括号。
现在利用最优子结构，根据子问题的最优解构造原问题的最优解。即保证寻找一个最优的位置分割乘积。
2、递归求解
假设m[i,j]表示计算AiAi+1...Aj最优解的花费代价，1≤i≤j≤n。整个问题，计算A1..n的代价为m[1,n]。如果i=j,m[i,j]=0;当i<j时，假设最优加括号是将AiAi+1...Aj分裂成AiAi+1...Ak和Ak+1Ak+2...Aj。则m[i,j]等于计算Ai..k和Ak+1..j的最小代价，再加上这二者相乘的代价。即：
m[i,j]=m[i,k]+m[k+1,j]+pi-1pkpj (i<k<j)
上述公式假设已经知道k值，实际上，只知道k有j-i个值，分别是k=i，i+1,i+2...,j-1，k是其中最佳的值，需要通过如下方式确定k值：
m[i,j]=min(i≤k<j){m[i,j]=m[i,k]+m[k+1,j]+pi-1pkpj } (i<j)
各个m[i,j]的值给出了子问题的最优解的代价。为了跟踪如何构造一个最优解，定义s[i,j]，让其记录AiAi+1...Aj最优解分裂处的k值。
3、计算最优解的代价
可轻易根据上述递归公式写出计算m[1,n]的递归算法。但是，它和穷尽搜索类似，具有指数时间。
可以观察到，原问题只有较少的子问题：每一对满足i<j的（i,j）对应一个子问题，总共不超过n2个。一个递归算法在递归树的不同分支中可能会多次遇到同一个子问题，子问题重叠是判断是否能够采用动态规划方法的第二个标志（第一个标志是最优子结构）。
对于矩阵链相乘问题不使用递归方式，而是使用自底向上的表格法计算最优解的代价。如下代码计算最优解的代价，其中Ai的维数为pi-1×pi,i=1,2,....,n。输入序列p=<p0,p1,p2,...,pn>，使用一个辅助表m[1...n,1...n]保存m[i,j]的值，使用s[1...n,1...n]记录取得最优m[i,j]时分裂处的k值。s用来构造最优解。
1 public void Matrix_Chain_Order() 2 { 3 for (int i = 1; i <= n; i++) { 4 m[i][i] = 0; 5 } 6 for (int l = 2; l <= n; l++) 7 { 8 for (int i = 1; i <= n-l+1; i++) 9 {10 int j = i+l-1;11 m[i][j] = 2147483647;12 for (int k = i; k <= j-1; k++) 13 {14 int q = m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];15 if(q<m[i][j])16 {17 m[i][j] = q;18 s[i][j] = k;19 } 20 } 21 } 22 } 23 }
4、构造最优解
利用保存在表格s[1..n，1..n]内的、经过计算的信息来构造一个最优解并不难。在每一个表项s[i,j]中记录了AiAi+1..Aj在Ak与Ak+1之间取得最优解的k值。计算A1..n最优解时，最终相乘的顺序就是A1..s[1,n]As[1,n]+1..n。s[1,s[1.n]]决定A1..s[1,n]最优解处的值，s[s[1,n]+1,n]则决定As[1,n]+1..n最优解处的值。下面程序递归的计算出一个矩阵链相乘的最优顺序。
1 public void Print_Optimal_Parens(int i,int j) 2 { 3 if(i==j) 4 { 5 System.out.print("A"+i); 6 } 7 else 8 { 9 System.out.print("(");10 Print_Optimal_Parens(i, s[i][j]);11 Print_Optimal_Parens(s[i][j]+1, j);12 System.out.print(")");13 }14 }
程序实现：
/* * To change this template, choose Tools | Templates * and open the template in the editor. */package agrith;/** * * @author ning */public class Matrix_Chain { private int [] p; private int [][]s; private int [][] m; private int n; public int getN() { return n; } public void setN(int n) { this.n = n; } public int[] getP() { return p; } public void setP(int[] p) { this.p = p; } public int[][] getS() { return s; } public void setS(int[][] s) { this.s = s; } public int getM(int i,int j) { return m[i][j]; } public void setM(int[][] m) { this.m = m; } public void Matrix_Chain_Order() { for (int i = 1; i <= n; i++) { m[i][i] = 0; } for (int l = 2; l <= n; l++) { for (int i = 1; i <= n-l+1; i++) { int j = i+l-1; m[i][j] = 2147483647; for (int k = i; k <= j-1; k++) { int q = m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]; if(q<m[i][j]) { m[i][j] = q; s[i][j] = k; } } } } } public void Print_Optimal_Parens(int i,int j) { if(i==j) { System.out.print("A"+i); } else { System.out.print("("); Print_Optimal_Parens(i, s[i][j]); Print_Optimal_Parens(s[i][j]+1, j); System.out.print(")"); } }} matrix_Chain.Matrix_Chain_Order(); System.out.println("最优解花费的代价："+matrix_Chain.getM(1, n-1)); System.out.println("最优解的顺序："); matrix_Chain.Print_Optimal_Parens(1, n-1); } }
程序结果：
最优解花费的代价：15125
最优解的顺序：
((A1(A2A3))((A4A5)A6))