矩阵连乘计算次序 可以用 加括号的方式 来确定。特别的,完全加括号的矩阵连乘积可递归地定义为:
给定n个矩阵𝐴1,⋯, 𝐴𝑛,其中第i个矩阵的维度为𝑝(𝑖−1)×𝑝𝑖,以及它们的一个完全加括号方案:
构建原问题最优解 与 子问题最优解之间的关系:
按以下顺序计算:
m(1,2)
=30 * 35 * 15 = 15750m(2,3)
=35 * 15 * 5 = 2625m(3,4)
=15 * 5 * 10 = 750m(4,5)
=5 * 10 * 20 = 1000m(5,6)
=10 * 20 * 25 = 5000m(1,3)
=7875时,有两种情况,k = 1 或者 k =2 时,(下面的数据就可以使用上面算法的,这就是自底向上
)m(2,4)
=4375时,有两种情况,k = 2 或者k =3 时,(同上)m(3,5)
=2500,k=3 或者 k=4m(4,6)
=3500,k=4 或者 k=5m(1,4)
=9375时,k 有三次情况,k=1,k=2,k=3,(同上)m(2,5)
=7125时,k 有三次情况,k=2,k=3,k=4m(3,6)
=5375m(1,5)
=11875时,k 有四次情况,k=1,k=2,k=3,k=4,(同上)m(2,6)
=10500m(1,6)
= 15125时,k 有五次情况,k=12345,(同上)
import java.util.Scanner;/*** DP 算法之 矩阵连乘*/
public class Main {public static long[][] memoTable; // 存放局部最优值public static int[][] bestK ; // 存放 划括号k 的位置public static int[] dim ; // 存放矩阵的值public static int matrixNum; // 二位矩阵 的维度/*** 自底向上地计算最优值,结果保存在全局变量memoTable和bestK中* @param matrixNum* @return*/static long MatrixChain(int matrixNum) {int i,j,len,k;for(i=1; i<=matrixNum; i++) //单个矩阵的情形,定义数乘次数为0memoTable[i][i] = 0;for(len=2; len<=matrixNum; len++){ //计算长度为len的矩阵链最优值for(i=1; i<=matrixNum-len+1; i++) { //矩阵链的开始矩阵下标j = i+len-1; //矩阵链的结束矩阵下标memoTable[i][j] = 100000000; //预定义的一个充分大数for(k=i; k //枚举划分位置long ans = memoTable[i][k] + memoTable[k+1][j] +dim[i-1]*dim[k]*dim[j];if (ans < memoTable[i][j]){ //更新最优信息bestK[i][j] = k;memoTable[i][j] = ans;}}//end of for k}//end of for i}//end of for lenreturn memoTable[1][matrixNum];}/*** 递归构造最优解* @param i* @param j* @param bestK* @return*/public static String traceback(int i,int j,int[][] bestK) {if(i==j) {return String.format("A%s", i);}if(i==j-1){return String.format("A%sA%s", i, j);}int position = bestK[i][j];StringBuilder sb = new StringBuilder();if(i!=position) {sb.append("(");}sb.append(traceback(i, position, bestK));if(i!=position) {sb.append(")");}if(position+1!=j) {sb.append("(");}sb.append(traceback(position+1, j, bestK));if(position+1!=j) {sb.append(")");}return sb.toString();}public static void main(String[] args) {Scanner in = new Scanner(System.in);System.out.println("请输入矩阵的个数:");matrixNum = in.nextInt();System.out.println("请输入矩阵的行数和列数:");dim = new int[matrixNum+1];for(int i = 0;i <= matrixNum;i++) {dim[i] = in.nextInt();}memoTable = new long[matrixNum+1][matrixNum+1];bestK = new int[matrixNum+1][matrixNum+1];long min = MatrixChain(matrixNum);System.out.println("矩阵连乘的最小次数是:" + min);System.out.println(String.format("矩阵的连乘次序:%s", traceback(1, matrixNum, bestK)));}
}
子解
是其相应子问题
的最优解
。反证法
:首先假设由问题最优解S导出的子问题的解不是最优的,然后再推导在这个假设下可构造出比S更好的解 S’,从而得到矛盾。子问题的重叠性质
。对每一个子问题只解一次,而后将其解保存在一个表格中
,当再次需要解此子问题时,只是简单地用常数时间查看一下结果。多项式
增长。因此用动态规划算法只需要多项式时间,从而获得较高的解题效率。 【降低复杂度不是本章的目标了!!
】long MatrixChain(int i, int j){if (i == j) {//单个矩阵的情形memoTable[i][j] = 0;return 0;}long ans, min = 100000000;//预定义的一个充分大数for (int k=i; kans = MatrixChain(i,k) + MatrixChain(k+1,j)+ dim[i-1]*dim[k]*dim[j]; //递归计算if (ans < min) {min = ans;}}return min; }
//递归调用前用 memset(memoTable,-1,sizeof(memoTable))初始化备忘录表为-1
long MatrixChainMemo(int i,int j){if (memoTable[i][j] != -1)return memoTable[i][j]; //备忘录表中有答案,则跳出递归调用过程if (i == j) {//单个矩阵的情形memoTable[i][j] = 0;return 0;}long ans,max = 100000000;//预定义的一个充分大数for (int k=i; kans = MatrixChainMemo(i,k)+MatrixChainMemo(k+1,j)
+dim[i-1]*dim[k]*dim[j]; //递归计算if (ans < max) {bestK[i][j]=k;max = ans;}}memoTable[i][j] = max; //用递归执行结果更新备忘录表return max;
}
最优子结构
特征;状态表示S(x~1~,x~2~,…)
和状态递推方程
,递归地定义最优值;状态转移顺序
,以自底向上
的方式计算出最优值;(从最小问题计算起,保存最优子结果,在计算更大的问题时就可以调用之)构造最优解
。