矩阵连乘

动态规划解矩阵连乘

动态规划的基本要素

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);
	}
}