首页 > 代码库 > 矩阵连乘
矩阵连乘
动态规划解矩阵连乘
动态规划的基本要素
1：最有子结构
2:重叠子问题
动态规划适用于解最优化问题，通常有四个步骤
（1） 找出最优解的性质，并刻画其结构性质。
（2） 递归的定义最优质
（3） 以自底向上的方式计算出最优质
（4） 根据计算最优质时得到的信息，构造最优解
我们以矩阵连乘为例。
｛A1,A2,...An｝Ai与Ai+1是可乘的。
矩阵乘法满足结合律，所以可以有很多不同的计算次序，可以用加括号的方式确定每一种计算次序，我们的目的是找出最有计算次序。
很明显所有的计算次序是一个Catalan数呈指数增长，穷举算法不是一个有效算法
下面用动态规划解矩阵连乘的最有计算次序问题
我们用A[i:j]表示Ai到Aj的计算次许，则我们的目的是求A[1:n]
设矩阵在Ak和Ak+1处断开，则先计算Ak和Ak+1然后将计算结果相乘得到A[1:n]用反证法可是证明当A[1:n]的计算次序是最优的其所包含的矩阵子链的计算次序也是最优的。
（2）建立递归关系
A[i:j],1<=i<=j<=n,所需要的最少数乘次数为m[i][j]我们可以得出一下递归关系
m[i][j] = 0 when i= j;
m[i][j] = m[i][k] + m[k+1][j] + pi-1*pk*pj; when i<j;
(3)计算最优值
根据m[i][j]的递归式我们很容易写一个递归算法m[1][n]这里不再赘述。
（4）下面是书上的计算次序图
上传不了图片
下面是我实现这个算法的代码
package martixchain;import java.io.Reader;import java.util.Scanner;import javax.security.auth.kerberos.KerberosKey;import org.omg.CORBA.PUBLIC_MEMBER;/*-------------------------------------------------------------- * Author: DingWenchao * Writtern: Dec 3,2014 * * martixchain *to produce the optimal array->the optimal computing orders *example:matrix[30,35,15,5,10,20,25]-> matrix 30 35 5 10 20 25 *to produce: 15125 ((A1(A2A3))((A4A5)A6)) * *Tests: matrix[30,35,15,5,10,20,25] *expected is : 15125 ((A1(A2A3))((A4A5)A6)) * -------------------------------------------------------------*/public class Martix_chain{ public static void main(String args[]){ System.out.println("Enter the number of martix"); Scanner reader = new Scanner(System.in); int n = reader.nextInt(); int []p = new int[n+1]; System.out.println("Enter ther a array of number " + "for eample 30 35 15 5 10 20 25 stand for six martixs 30*35,35*15,15*5,5*10,10*20,20*25 "); for(int i = 0;i <= n;i++){ p[i] = reader.nextInt(); } reader.close(); martix mx = new martix(n, p); int[][]s = mx.martixChain(); for(int i = 1;i<=n;i++){ for(int j = 1;j<=n;j++){ System.out.println(s[i][j]); } } mx.traceback(1, n); }}class martix{ int n; //the number of martix. int[]p; //the array of martix. int[][]m; //to save each of int[][]s;//to save k martix(int n,int[]p){//construct function this.n = n; this.p = p; this.m = new int[n+1][n+1]; this.s = new int[n+1][n+1]; } int[][] martixChain(){ for(int i = 1;i <= n;i++)m[i][i] = 0; for(int r = 2;r <= n;r++)//diagonal cycle for(int i = 1;i <= n-r+1;i++){// int j = i + r - 1; m[i][j] = m[i][i] + m[i+1][j] + p[i-1]*p[i]*p[j]; 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]){ m[i][j] = t; s[i][j] = k; } } } return s; } void traceback(int i,int j){ if(i == j) return; traceback(i,s[i][j]); traceback(s[i][j]+1,j ); System.out.println("Multiplay A" + i + "," + s[i][j] + "and A" + (s[i][j]+1)+"," + j); }}
矩阵连乘
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。