精华内容
下载资源
问答
  • 矩阵连乘 动态规划

    2018-12-30 09:56:00
    矩阵连乘 动态规划  题目描述:给定n个矩阵{A1,A2,…,An},其中Ai与Ai+1是可乘的,i=1,2 ,…,n-1。如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。例如:  A1={30x35} ; ...

    矩阵连乘 动态规划

      题目描述:给定n个矩阵{A1,A2,…,An},其中Ai与Ai+1是可乘的,i=1,2 ,…,n-1。如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。例如:

      A1={30x35} ; A2={35x15} ;A3={15x5} ;A4={5x10} ;A5={10x20} ;A6={20x25} ;

    最后的结果为:((A1(A2A3))((A4A5)A6))  最小的乘次为15125。

      解题思路:能用动态规划的一个性质就是最优子结构性质,也就是说计算A[i:j]的最优次序所包含的计算矩阵子琏A[i:k]和A[k+1:j]的次序也是最优的。动态规划算法解此问题,可依据其递归式以自底向上的方式进行计算(即先从最小的开始计算)。在计算过程中,保存已解决的子问题答案。每个子问题只计算一次,而在后面需要时只要简单查一下,从而避免大量的重复计算,最终得到多项式时间的算法。我们可以根据下面这个公式来计算结果。其中p[i-1]表示的是第i个矩阵的行数,p[k]表示i:k矩阵合起来后最后得到的列数,p[j]是k+1:j合起来后得到的列数。这个部分的计算方法其实就是计算两个矩阵相乘时总共的乘次数,自己琢磨琢磨就明白了。

    从连乘矩阵个数为2开始计算每次的最小乘次数m[i][j]: m[0][1] m[1][2] m[2][3] m[3][4] m[4][5]  //m[0][1]表示第一个矩阵与第二个矩阵的最小乘次数

    然后再计算再依次计算连乘矩阵个数为3:m[0][2] m[1][3] m[2][4] m[3][5]

                连乘矩阵个数为4:m[0][3] m[1][4] m[2][5]

              连乘矩阵个数为5:m[0][4] m[1][5]

              连乘矩阵个数为6:m[0][5]    //即最后我们要的结果

     

    #include <stdio.h>
    #include <stdlib.h>
    
    #define MAX 100
    
    
    int matrix_chain(int *p, int n, int **m, int **s)
    {
        //a[][]最小乘次数
        //s[][]最小乘数时的断开点
        int i,j,r,k;
        
        for (i = 0; i < n; i++)   //单一矩阵的最小乘次都置为0
        {
            m[i][i] = 0;
        }
        
        for (r = 2; r <= n; r++)  //r为连乘矩阵的个数
        {
            for (i = 0; i <= n-r; i++)   //i表示连乘矩阵中的第一个
            {
                j = i + r -1;         //j表示连乘矩阵中的最后一个
                m[i][j] = 99999;
                for (k = i; k <= j-1; k++)  //在第一个与最后一个之间寻找最合适的断开点,注意,这是从i开始,即要先计算两个单独矩阵相乘的乘次
                {
                    int tmp = m[i][k] + m[k+1][j] + p[i]*p[k+1]*p[j+1];
                    if (tmp < m[i][j])
                    {
                        m[i][j] = tmp;
                        s[i][j] = k;
                    }
                }
            }
        }
        return m[0][n-1];
    }
    
    void print_chain(int i, int j, char **a,int **s)
    {    //递归的方式来把最小乘数的表达式输出
    
        if (i == j)
        {
            printf("%s",a[i]);
        }
        else
        {
            printf("(");
            print_chain(i,s[i][j],a,s);
            print_chain(s[i][j]+1,j,a,s);
            printf(")");
        }
    }
    
    int main()
    {
        //min_part[i][j]存储的是i+1到j+1的最小乘次,因为是从0开始
        //min_point[i][j]存储的是i+1到j+1之间最小乘次时的分割点
        int *p, **min_part, **min_point;
        char **a;
        int n = 6,i;
        int ret;
        
        p = (int *)malloc((n+1)*sizeof(int));
        a = (char **)malloc(n*sizeof(char*));
        min_part = (int **)malloc(n*sizeof(int *));
        min_point = (int **)malloc(n*sizeof(int *));
        
        for (i = 0; i < n; i++)
        {
            min_part[i] = (int *)malloc(n*sizeof(int));  
            min_point[i] = (int *)malloc(n*sizeof(int));
            a[i] = (char *)malloc(n*sizeof(char));
        }
        
        p[0] = 30;   //第一个矩阵的行数
        p[1] = 35;     //第二个矩阵的行数
        p[2] = 15;     //……
        p[3] = 5;     //……    
        p[4] = 10;     //……
        p[5] = 20;     //第六个矩阵的行数
        p[6] = 25;     //第六个矩阵的列数
        
        a[0] = "A1";
        a[1] = "A2";
        a[2] = "A3";
        a[3] = "A4";
        a[4] = "A5";
        a[5] = "A6";
        
        ret = matrix_chain(p,n,min_part,min_point);
        printf("Minest times:%d.\n",ret);
        print_chain(0,n-1,a,min_point);
        
        free(p);
        free(min_part);
        free(min_point);
        free(a);
    
        return 0;
    }
    
    2013/8/1 23:38

    转载自:https://www.cnblogs.com/Jason-Damon/p/3231547.html

    转载于:https://www.cnblogs.com/yangf428/p/10198664.html

    展开全文
  • 矩阵连乘动态规划

    2020-07-27 19:54:47
    题目我就不赘述了,直接进入正题: 假设有矩阵1,2,3…n 核心思路是——在[1~n]之间每个位置都做一次划分k,最小结果=先算[1-k]和[k+1-n]两部分最小乘积+最后两个矩阵乘积次数。...//求矩阵连乘 void function(int

    题目我就不赘述了,直接进入正题:
    假设有矩阵1,2,3…n

    核心思路是——在[1~n]之间每个位置都做一次划分k,最小结果=先算[1-k]和[k+1-n]两部分最小乘积+最后两个矩阵乘积次数。
    矩阵[1-n]一共要划分n-1次,相当于一刀一刀挨个儿切过去,每个子问题同样如此,时间复杂度为n^2。

    可以看到,问题划分为小规模时是分治的思想,但两个小规模之间数据会重复计算好多次,因此采用动态规划,需要中间结果和辅助标记两个二维数组,用空间换时间。具体代码如下:

    //求矩阵连乘
    void function(int ary[], int number,//number指有几个矩阵
    			  vector<vector<int>>& middle, vector<vector<int>>& flag)
    {
    	assert(ary != NULL);
    	//sum是一次计算的个数,比如sum=3,number=5时,计算子结果:1~3,2~4,3~5
    	for (int sum = 2; sum <= number; ++sum)
    	{
    		for (int start = 1; start+sum-1 <= number; ++start)//起始位置
    		{
    			//把范围内的所有矩阵每个地方都划分一遍,求最小值
    			//比如1~3,划分为[1~1,2~3]和[1~2,3~3]
    			int min = INT_MAX;
    			for (int num = 1; num < sum; ++num)
    			{
    				int tmp1 = middle[start][start+num-1];//划分的前半段最小结果
    				int tmp2 = middle[start+num][start+sum-1];//划分的后半段最小结果
    				//前半和后半矩阵最后乘起来时的计算次数
    				int tmp3 = ary[start-1] * ary[start+num-1] * ary[start+sum-1];
    				int tmp = tmp1 + tmp2 + tmp3;//一种情况的最小结果
    				if (tmp < min)//更新最小结果
    				{
    					middle[start][start+sum-1] = tmp;//设置中间结果
    					min = tmp;
    					flag[start][start+sum-1] = start + num - 1;//设置标记
    				}
    			}
    		}
    	}
    	cout << "min = " << middle[1][number] << endl;
    }
    //打印辅助空间
    void Show_vector(vector<vector<int>>& middle)
    {
    	for (int i = 0; i < middle.size(); ++i)
    	{
    		for (int j = 0; j < middle[i].size(); ++j)
    		{
    			cout << setw(8) << middle[i][j];
    		}
    		cout << endl;
    	}
    }
    //回溯标记数组,打印结果
    void TrackBack(int ary[], int start, int end, vector<vector<int>>& flag)
    {
    	if (start == end)
    	{
    		cout << "S" << end;
    		return;
    	}
    	if (start+1 == end)
    	{
    		cout << "S" << start << "*S" << end;
    		return;
    	}
    	if (flag[start][end]-start >= 1) cout << "(";
    	TrackBack(ary, start, flag[start][end], flag);
    	if (flag[start][end]-start >= 1) cout << ")";
    	cout << "*";
    	if (end-flag[start][end]-1 >= 1) cout << "(";
    	TrackBack(ary, flag[start][end]+1, end, flag);
    	if (end-flag[start][end]-1 >= 1) cout << ")";
    }
    int main()
    {
    	int ary[] = {30,35,15,5,10,20,25};//矩阵,简单起见,6个值表示5个行列相连的矩阵
    	int number = sizeof(ary) / sizeof(ary[0]) - 1;//矩阵个数
    	vector<vector<int>> middle;//临时结果,三角形。middle[i][j]表示矩阵[i~j]相乘的最小结果
    	vector<vector<int>> flag;//辅助标记,flag[i][j]=k表示矩阵[i~j]相乘的最小结果从k处划分——[i~k],[k+1~j]
    	middle.resize(number+1);
    	flag.resize(number+1);
    	for (int i = 0; i < number+1; ++i)
    	{
    		middle[i].resize(number+1, 0);
    		flag[i].resize(number+1, 0);
    	}
    	function(ary, number, middle, flag);
    	TrackBack(ary, 1, number, flag);
    	cout << endl;
    	Show_vector(middle);
    	cout << endl;
    	Show_vector(flag);
    	cout << endl;
    	return 0;
    }
    

    结果如下(从上往下分别是最终结果、乘积先后次序、中间结果、辅助标记):
    运行结果
    中间结果二维数组的填写顺序如下,构成了三角形,y轴的i到x轴的j组成了一个范围[i-j]:例如右上角的最终结果15125,指的是矩阵[1~6]的最小次数。
    中间结果二维数组的填写顺序
    辅助标记空间及回溯过程(从右上角开始,根据标记值3分成[1-3]和[4-6]两个区间,再根据区间找对应标记值,当区间元素<=2时无需再次回溯,直接打印结果就好。)
    辅助标记空间及回溯过程

    展开全文
  • 动态规划求解矩阵连乘问题JAVA实现动态规划求解矩阵连乘问题JAVA实现import java.io.*;//输入类class Testio{ public static double readDouble() { try { return Double.valueOf(readString().trim()).doubleValue...

    动态规划求解矩阵连乘问题JAVA实现

    动态规划求解矩阵连乘问题JAVA实现import java.io.*;

    //输入类

    class Testio{ public static double readDouble() { try { return Double.valueOf(readString().trim()).doubleValue();} catch(NumberFormatException ne) { System.err.println("Console.readDouble:Not a double..."); System.exit(-1); return 0.0; } } public static int readInt() { try{return Integer.valueOf(readString().trim()).intValue();} catch(NumberFormatException ne){ System.err.println("Console.readInt:Not an integer...."); System.exit(-1); return -1; } } public static String readString() { String string=new String(); BufferedReader in=new BufferedReader(new InputStreamReader(System.in)); try{ string=in.readLine();} catch(IOException e) { System.out.println("Console.readInt:Not an integer...."); System.exit(-1); }return string; }}

    //public class Juzhen{ public static void Matrix(int p[],int n,int m[][],int s[][]) { for(int i=1;i<=n;i++)m[i][i]=0; for(int r=2;r<=n;r++) for(int i=1;i<=n-r+1;i++) { int j=i+r-1; m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j]; s[i][j]=i; for(int k=i+1;k

    public static void TrackBack(int i,int j,int s[][]){if(i==j) { System.out.print("A"+i); return ; }if(i

    展开全文
  • 矩阵连乘动态规划算法

    千次阅读 2017-06-20 17:35:25
    矩阵连乘动态规划算法题目描述: Java实现:import java.util.Scanner;public class MatrixChain { public static void main(String[] args) { // TODO 自动生成的方法存根 Scanner scan = new Scanner(System....

    矩阵连乘动态规划算法

    题目描述:
    这里写图片描述
    这里写图片描述

    Java实现:

    import java.util.Scanner;
    
    public class MatrixChain {
    
        public static void main(String[] args) {
            // TODO 自动生成的方法存根
            Scanner scan = new Scanner(System.in);
            int n = scan.nextInt();
            int p[] = new int[n+1];
            for(int i=0; i<=n; i++)
                p[i] = scan.nextInt();
    //      int n = 6;
    //      int p[] = {30, 35, 15, 5, 10, 20, 25};
            //非递归
            int m[][] = new int[n+1][n+1];
            int s[][] = new int[n+1][n+1];
            MatrixChain1(p, n, m, s);
            t(1, n, s);
            System.out.println();
            String sss = traceBack(1, n, s);
            System.out.println(sss);
            //自底向上 递归 动态规划
            int s1[][] = new int[n+1][n+1];
            RecurMatrixChain(1, n, p, s1);
            t(1, n, s1);
            System.out.println();
            //自顶向下 递归 动态规划
            int m2[][] = new int[n+1][n+1];
            int s2[][] = new int[n+1][n+1];
            MemoizedMatrixChain(n, m2, s2, p);
            t(1, n, s2);
        }
        //输出计算最优计算次序,括号分离
        public static void t(int i, int j, int s[][]) {
            if (i == j)
                System.out.print("A" + i);
            else {  
                System.out.print("(");
                t(i, s[i][j], s);
                t(s[i][j]+1, j, s);
                System.out.print(")");
            }
        }
        public static String traceBack(int i,int j,int s[][]){
            if(i==j){
                  return "A"+i;
            }
            else{
                   return"("+traceBack(i,s[i][j],s)+traceBack(s[i][j]+1,j,s)+")";
            }
        }
        //非递归方法
        //一维数组P存储n个矩阵的行列值, 二维数组m存储最优值, 二维数组s记录最优断开位置
        public static void MatrixChain1(int p[], int n, int m[][], int s[][]){
            for(int i=1; i<=n; i++)//单个矩阵
                m[i][i] = 0;
            for(int r=2; r<=n; r++){//多个矩阵
                for(int len=1; len<=n-r+1; len++){
                    int j = len + r -1;
                    m[len][j] = m[len+1][j] +p[len-1]*p[len]*p[j];
                    s[len][j] = len;
                    for(int k=len+1; k<j; k++){
                        int t = m[len][k] + m[k+1][j] + p[len-1]*p[k]*p[j];
                        if(t < m[len][j]){
                            m[len][j] = t;
                            s[len][j] = k;
                        }
                    }
                }
            }
        }   
        //一维数组P存储n个矩阵的维数值, 二维数组s记录最优断开位置
        //自底向上 递归 动态规划
        public static int RecurMatrixChain(int i, int j, int p[], int s[][]) {
            if(i==j) return 0;
            int u = RecurMatrixChain(i, i, p, s) + RecurMatrixChain(i+1, j, p, s) + p[i-1]*p[i]*p[j];
            s[i][j] = i;
            for(int k=i+1; k<j; k++){
                int t = RecurMatrixChain(i, k, p, s) + RecurMatrixChain(k+1, j, p, s) + p[i-1]*p[k]*p[j];
                if(t < u){
                    u = t;
                    s[i][j] = k;
                }
            }
            return u;
        }
        //一维数组P存储n个矩阵的维数值, 二维数组m存储最优值, 二维数组s记录最优断开位置
        //自顶向下 递归 动态规划(备忘录方法)
        public static int MemoizedMatrixChain(int n, int m[][], int s[][], int p[]) {
            for(int i=1; i<=n; i++)
                for(int j=i; j<=n; j++)
                    m[i][j] = 0;
            return LookupChain(1, n, m, s, p);
        }
        public static int LookupChain(int i, int j, int m[][], int s[][], int p[]){
            if(m[i][j] > 0) return m[i][j];
            if(i==j) return 0;
            int u = LookupChain(i, i, m, s, p) + LookupChain(i+1, j, m, s, p) + p[i-1]*p[i]*p[j];
            s[i][j] = i;
            for(int k=i+1; k<j; k++){
                int t = LookupChain(i, k, m, s, p) + LookupChain(k+1, j, m, s, p) + p[i-1]*p[k]*p[j];
                if(t < u){
                    u = t;
                    s[i][j] = k;
                }
            }
            m[i][j] =u;
            return u;
        }
    
    }
    
    展开全文
  • 例题分析这次分析过程按照动态规划的三个基本条件来逐步解答:1、寻找最优子结构:假设我们已经找到父矩阵链最优解,当我们划分到最后一步时都是两个子矩阵链(分别被括号包围)相乘,如(A1A2A3A4)(A5A6A7),...
  • 给定n个矩阵{A1,A2,…,An},其中,Ai与Ai+1是可乘的,(i=1,2 ,…,n-1)。用加括号的方法表示矩阵连乘的次序,不同的计算次序计算量(乘法次数)是不同的,找出一种加括号的方法,使得矩阵连乘的次数最小
  • 矩阵连乘问题----动态规划(转载): 给定n个矩阵{A1,A2,…,An},其中Ai与Ai+1是可乘的,i=1,2…,n-1。如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。 解答:我们按照动态规划...
  • 1. 介绍动态规划典型的被用于优化递归算法,因为它们倾向于以指数的方式进行扩展。动态规划主要思想是将复杂问题(带有许多递归调用)分解为更小的子问题,然后将它们保存到内存中,这样我们就不必在每次使用它们时...
  • 递归,动态规划两种方法实现1.递归实现:public class MatrixChainDiGui {static int p[] = { 30, 35, 15, 5, 10, 20, 25 };public static void main(String[] args) {System.out.println(getMatrixChain(1,6));}...
  • 文章和资源同步更新至微信公众号:算法工程师之...那我们今天来看看如何从暴力递归改成动态规划动态规划的实质又是什么?什么情况下可以让暴力递归改成动态规划?从暴力递归到动态规划​mp.weixin.qq.com暴力递归...
  • 矩阵连乘 动态规划 C#

    千次阅读 2012-03-19 10:53:28
    大家好,下面是用动态规划的方法解决矩阵连乘问题,有兴趣的看看 using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace 动态规划2 { class Program { ...
  • #include<iostream> #include<string.h> using namespace std; int dp[110][110]; int main() { int N; while(cin>>N){ memset(dp,0,sizeof(dp)); int p[110]; ...
  • 而每个动态系统的「惯量矩阵」则巧妙地表达了相对应的目标的「优先级」(或重要性),有了这些,机器人就能灵活优雅地对每个时间点做出最适当的规划。 以上就是对如本科技所开发的实时运动规划算法的一个简单介绍,...
  • //求从矩阵 start 到 矩阵 end 的最优乘法次数 int f(int start, int end) { if (opt[start][end] != 0) return opt[start][end]; if (start == end) return 0; if (start == end - 1) { return opt[start]...
  • 若一个矩阵连乘积的计算次序完全确定,也就是说该连乘积已完全加括号,则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为:  (1)单个矩阵是完全加括号的
  • 导语:HMM和CRF模型中利用大量的动态规划算法进行快速运算,本文主要是从比较实用和易于理解的角度,对HMM和CRF模型的前向算法和后向算法进行进行了推导,其中的推导过程,补充了大量细节,面对网络上全文搬运统计...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 920
精华内容 368
关键字:

矩阵连乘动态规划