精华内容
下载资源
问答
  • 动态规划矩阵链乘法
    2018-05-05 13:23:49

    矩阵链乘法

    问题描述

    给定一个 nn 个矩阵的序列(矩阵链) <A1,A2,…,AnA1,A2,…,An>,我们希望计算它们的乘积

     

    A1A2…AnA1A2…An


    为了计算表达式,我们可以先用括号明确计算次序,然后利用标准的矩阵相乘算法进行计算。由于矩阵乘法满足结合律,因此任何加括号的方法都会得到相同的计算结果。我们称有如下性质的矩阵乘积链为完全括号话:它是单一矩阵,或者是两个完全括号化的矩阵乘积链的积,且已外加括号。例如,如果矩阵链为<A1,A2,A3,A4A1,A2,A3,A4>,则共有 5 种完全括号化的矩阵乘积链:

    (A1(A2(A3A4))),(A1(A2A3(A4))),((A1A2)(A3A4)),((A1A2A3)(A4)),(((A1A2)A3)A4)(A1(A2(A3A4))),(A1(A2A3(A4))),((A1A2)(A3A4)),((A1A2A3)(A4)),(((A1A2)A3)A4)


    两个矩阵 AA 和 BB 只有相容,即AA的列数等于 BB 的行数时,才能相乘。如果 AA 是 p×qp×q 的矩阵,BB 是 q×rq×r 的矩阵那么乘积 CC 是 p×rp×r 的矩阵。计算 CC 的代价为 pqrpqr,我们使用标量乘法的次数来表示计算代价。
    矩阵链乘法问题:给定 nn 个矩阵的链<A1,A2,…,AnA1,A2,…,An>,矩阵 AiAi 的规模为 pi−1×pi(1≤i≤n)pi−1×pi(1≤i≤n),求完全括号化方案,使得计算乘积 A1A2…AnA1A2…An所需的标量乘法次数最少。

    动态规划求解

    最优解结构

    为了方便起见,我们用符号 Ai.j(i≤j)Ai.j(i≤j) 表示AiAi+1…AjAiAi+1…Aj 乘积的结果矩阵。
    假设AiAi+1…AjAiAi+1…Aj 的最优括号化方案的分割点在 AkAk 和 Ak+1Ak+1 之间。那么,继续对”前缀”子链 AiAi+1…AkAiAi+1…Ak,”后缀” Ak+1Ak+2…AjAk+1Ak+2…Aj 进行括号化 (独立求解)。

    递归定义

    令 m[i,j]m[i,j] 表示计算矩阵 Ai.jAi.j 所需标量乘法次数的最小值,原问题的最优解—–计算A1..nA1..n 所需的最低代价就是 m[1,n]m[1,n]。
    我们假设 AiAi+1…AjAiAi+1…Aj 的最优括号化方案的分割点在矩阵 AkAk 和 Ak+1Ak+1 之间,其中 i≤k<ji≤k<j。 那么,m[i,j]m[i,j] 就等于计算 Ai.kAi.k 和 Ak+1.jAk+1.j 的代价加上两者相乘的代价的最小值:

     

    m[i,j]=m[i,k]+m[k+1,j]+pi−1pkpjm[i,j]=m[i,k]+m[k+1,j]+pi−1pkpj


    因此递归求解公式为
    if i==j

    m[i,j]=0m[i,j]=0


    else if i<j

    m[i,j]=min{m[i,k]+m[k+1,j]+pi−1pkpj},i≤k<jm[i,j]=min{m[i,k]+m[k+1,j]+pi−1pkpj},i≤k<j

    计算最优值

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    
    public static void getMatrixChanOrder(int[] p) {
    	int n = p.length;
    	long[][] dp = new long[n][n];
    	int[][] s = new int[n][n];
    	for (int i = 0; i < n; i++) {
    		dp[i][i] = 0;
    	}
    	for (int l = 2; l < n; l++) {
    		for (int i = 1; i <= n - l; i++) {
    			int j = i + l - 1;
    			dp[i][j] = Long.MAX_VALUE;
    				for (int k = i; k < j; k++) {
    				long temp = dp[i][j];
    				dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j]);
    				if(temp!=dp[i][j]){
    					s[i][j]=k;
    				}
    			}
    		}
    	}
    	System.out.println(dp[1][n-1]+" "+s[1][n-1]);
    }
    

    假定矩阵 AiAi 的规模为 pi−1×pi,(i=1,2,…,n)pi−1×pi,(i=1,2,…,n),输入的序列 p=p=<p0,p1,…,pnp0,p1,…,pn>
    比如:

    矩阵A1A1A2A2A3A3A4A4A5A5A6A6
    规模30×3530×3535×1535×1515×515×55×105×1010×2010×2020×2520×25

    1
    
    int[] p = { 30, 35, 15, 5, 10, 20, 25 };
    

     

    构造最优解

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    
    public static void printOptimal(int[][] s,int i,int j){
    	if(i==j){
    		System.out.print("A"+i);
    	}else{
    		System.out.print("(");
    		printOptimal(s,i,s[i][j]);
    		printOptimal(s,s[i][j]+1,j);
    		System.out.print(")");
    	}
    }
    

    完整代码以及相应示例图见 https://github.com/lemon2013/algorithm/blob/master/MatrixChain.java

     

    更多相关内容
  • 矩阵链乘法问题( matrix-chain multiplication problem )(1)问题描述给定n个矩阵的链,其中i=1,2,…,n,矩阵A i的维数为pi-1 ×p i 。求一个完全“括号化方案”,使得计算乘积A 1 A 2 …A n 所需的标量乘法次数最小...

    矩阵链乘法问题( matrix-chain multiplication problem  )

    (1)问题描述

    给定n个矩阵的链,其中i=1,2,…,n,矩阵A i的维数为pi-1 ×p i 。求一个完全“括号化方案”,使得计算乘积A 1 A 2 …A n 所需的标量乘法次数最小

    (2)最优括号化方案的结构特征

    用记号 A i,j 表示 Ai A i+1 …A j 通过加括号后得到的一个最优计算模式,且恰好在A k 与A k+1 之间分开。则“前缀”子链Ai A i+1 …A k 必是一个最优的括号化子方案,记为A i,k ;同理“后缀”子链A k+1 A k+2 …Aj 也必是一个最优的括号化子方案,记为A k+1,j。

    (3)一个递归求解的方案

    对于矩阵链乘法问题,我们将所有对于1≤i≤j≤n确定Ai A i+1 …A j 的最小代价括号方案作为子问题。令m[i,j]表示计算矩阵A i,j 所需要的标量乘法的次数最小值,则最优解就是计算A i…n所需的最低代价就是m[1,n]

    递归定义m[i,j]。

    ①对于i=j的情况下,显然有m=0,不需要做任何标量乘法运算。所以,对于所有的i=1、2……n,m[i,i] = 0.

    ②当i < j的情况,就按照最优括号化方案的结构特征进行计算m[i,j]。假设最优括号化方案的分割点在矩阵Ak和Ak+1之间,那么m的值就是Ai…k和Ak+1…j的代价加上两者量程的代价的最小值。即

    081e710e6f6ff9e6b9cbf8ff914ff7e2.png。该公式的假设是最优分割点是已知的,但是实际上不知道。然而,k只有j-i中情况取值。由于最优分割点k必定在i~j内取得,只需要检查所有可能的情况,找到最优解即可。可以得出一个递归公式

    e4e9c8803682dae32acc4e49148f8917.png

    m只是给出了子问题最优解的代价,但是并未给出构造最优解的足够信息(即分割点的位置信息)。所以,在此基础之上,我们使用一个二维数组s[i,j]来保存 Ai A i+1 …A j的分割点位置k。

    (4)我们采用自底向上表格方法来代替上述递归公式算法来计算最优代价。过程中假定矩阵A的规模为Pi-1Xpi,输入是一个序列p=,长度为p.length = n+1.其中使用一个辅助表m来记录代价m[i,j],另一个表s来记录分割点的位置信息,以便于构造出最优解。

    ab54f9117e08eda59b3f6e97a9859ca7.png

    简单介绍一下算法:首先在3~4行对所有的i=1、2……n计算m[i,i]=0。然后在5~13行中的第一个for循环,使用(3)中的递归公式对所有的i=1~n-1计算m[i,i+1](长度为l=2的最小计算代价)的值。在第二个循环中,对所有的i=i~n-2计算m[i,i+2](长度为l=3的链的最小计算代价)的值。到最后,10~13行中计算代价m[i,j]的时候仅仅依赖于上面计算的表项m[i,k]和m[k+1,j]

    (5)给一个简单的例子

    ①给出一个n=6的矩阵如下图所示

    ddba85640792bada4558d25a098a0ded.png

    ②由上述表我们按照下面这样的计算方式来得到m[i,j]所对应的表,下图所示的表格中代表的m[i,j]的最小值

    1c3b8f329da77949ffdd24f6010eb8ee.png

    ③可以得到下面这样一张表

    首先将矩阵化为一张一维数组表

    504cbd67b1a46f1d6072de9e9ae8d41f.png

    ④简单结算其中的一些表项,给出一个m[1,3]的值的计算过程如下:

    3ad5344c01451ff7157333d5f423094e.png

    可以得出上面的比较小的分割点为1,所以s[1,3] = 1。

    1a622b2cc00d23b58a3fce7493fbf2c4.png

    可以得出分割点的位置为s[2,5] = 3。

    上面给出了一个简单的两个点的计算。下图是计算完成的矩阵m和s

    796ba5fd51559667563ae5d37267b93e.png

    039a0b287b4cc08759bdb15a46731196.png

    由上面表s可以得到,最优解为(A1(A2A3))((A4A5)A6)

    作者:风沙迷了眼

    展开全文
  • 动态规划-矩阵链乘法

    2019-01-14 17:25:00
    动态规划-矩阵链乘法 采用动态规划的方式求解矩阵链乘法问题 问题描述 给定一个n个矩阵的序列(矩阵链&amp;lt;A1,A2,...,AnA_{1},A_{2},...,A_{n}A1​,A2​,...,An​&amp;gt;),希望计算其乘积 A1A2...

    动态规划-矩阵链乘法

    采用动态规划的方式求解矩阵链乘法问题

    问题描述

    1. 给定一个n个矩阵的序列(矩阵链< A 1 , A 2 , . . . , A n A_{1},A_{2},...,A_{n} A1,A2,...,An>),希望计算其乘积
      A 1 A 2 . . . A n A_{1}A_{2}...A_{n} A1A2...An---------------------------------------------------------------(1)

    2. 使用括号明确计算次序,然后依据标准矩阵计算乘法计算其结果
      已知,任何加括号的方式都将得到相同的计算结果。所以为了减少计算的复杂程度(不同计算顺序,乘法次数也不同),引出如下定义:已知,任何加括号的方式都将得到相同的计算结果。所以为了减少计算的复杂程度(不同计算顺序,乘法次数也不同),引出如下定义:
      完全括号化的矩阵链:
      a. 它是单一矩阵;
      b. 或者是两个完全括号化的矩阵链乘积,且已加外括号。例如矩阵链为< A 1 , A 2 , A 3 , A 4 A_{1},A_{2},A_{3},A_{4} A1,A2,A3,A4>的一个完全括号化的矩阵链为 ( A 1 ( A 2 ( A 3 A 4 ) ) ) (A_{1}(A_{2}(A_{3}A_{4}))) (A1(A2(A3A4)))

    3. 寻找最少乘法次数
      由标准矩阵计算乘法方式可知,假设计算 A p ∗ q A q ∗ r A_{p*q}A_{q*r} ApqAqr则乘法次数一共 p ∗ q ∗ r p*q*r pqr次。(两个矩阵相乘的条件是必须相容,即前一个矩阵的列数等于后一个矩阵的行数)

    4. 矩阵乘法链问题的简化
      给定的n个矩阵的链< A 1 , A 2 , . . . , A n A_{1},A_{2},...,A_{n} A1,A2,...,An>,且由上一小节可知我们可以将数据链的规模简化为< A p 0 ∗ p 1 , A p 1 ∗ p 2 , . . . , A p n − 1 ∗ p n A_{p_{0}*p_{1}},A_{p_{1}*p_{2}},...,A_{p_{n-1}*p_{n}} Ap0p1,Ap1p2,...,Apn1pn>,进一步简化为 p 0 , p 1 , . . . , p n p_{0},p_{1},...,p_{n} p0,p1,...,pn,最终就是要求完全括号化方案,使得计算乘积 A 1 A 2 . . . A n A_{1}A_{2}...A_{n} A1A2...An所需标量乘法次数最少。

    计算括号化方案的数量

    1. 首先我们想到的是穷举所有的方案,然后找出最佳方案。然而这种方式显然不是一种高效的方法。假设对于一个长度为n的矩阵链,令 P ( n ) P(n) P(n)表示可供选择的括号化方案数量。可以得到如下递归公式:
      P ( n ) = { 1...................................... n = 1 ∑ k = 1 n − 1 P ( k ) P ( n − k ) . . . . . . . . . n ⩾ 2 P(n) = \left\{\begin{matrix} 1......................................n=1\\ \sum_{k=1}^{n-1}P(k)P(n-k).........n\geqslant 2 \end{matrix}\right. P(n)={1......................................n=1k=1n1P(k)P(nk).........n2
      当长度为1时,只有一个方案,当长度大于等于2时,我们可以在第一个到倒数最优一个任意之间加入括号,将其分成两个规模更小的子矩阵链,然后递归的计算更小规模子矩阵链的方案数。
      总体来说,该序列的方案的数量增长速度与n呈指数关系,所以显然暴力搜索是一个糟糕的方案。

    应用动态规划方法

    1. 四个步骤

      1. 刻画最优解的结构特征;
      2. 递归定义最优解的值;
      3. 计算最优解的值,通常采用自底向上的方法;
      4. 利用计算出的信息构造一个最优解。
        以下就根据以上顺序展示针对该问题每一步如何做。
    2. 最优括号化方案的结构特征

      1. 寻找最优子结构,然后就可以利用这种子结构从子问题的最优解构造出原问题的最优解。
      2. 假设 A i . . j ( i ≤ j ) A_{i..j}(i ≤ j) Ai..jij表示 A i A i + 1 . . . A j A_{i}A_{i+1}...A_{j} AiAi+1...Aj乘积的结果矩阵,且当 i &gt; j i &gt; j i>j时,该问题为不平凡的,此次要对矩阵链进行括号化则必须在 i i i j j j之间找到某值 k k k,将其分割为 A i . . k A_{i..k} Ai..k A k + 1.. j A_{k+1..j} Ak+1..j,然后计算两者的乘积,得到最终结果,此时 A i . . j A_{i..j} Ai..j的计算代价除了上述乘积之外还有计算 A i . . k A_{i..k} Ai..k A k + 1.. j A_{k+1..j} Ak+1..j的代价。
      3. 该问题的最优解寻找方式就是要找到最佳的 k k k
    3. 一个递归求解方案

      1. 首先给出一个定义:假设对于所有 1 ≤ i ≤ j ≤ n 1≤i≤j≤n 1ijn时, m [ i , j ] m[i,j] m[i,j]为计算 A i . . j A_{i..j} Ai..j的最小标量乘法次数,则原问题取得最优解时,最小标量乘法次数为 m [ 1 , n ] m[1,n] m[1,n]
      2. 为了求解 m [ i , j ] m[i,j] m[i,j],我们递归的定义它,并且当 i = j i=j i=j时的平凡问题,对所有的 i = 1 , 2 , . . . , n i=1,2,...,n i=1,2,...,n, m [ i , i ] = 0 m[i,i]=0 m[i,i]=0.当 i &lt; j i&lt;j i<j时,我们使用上一步骤所得的最优括号化方案的结构特征来定义,最终 A i A i + 1 . . . A j A_{i}A_{i+1}...A_{j} AiAi+1...Aj最小代价括号化方案的递归求解公式就变为:
        m [ i , j ] = { 0................................................................... i = j min ⁡ i ⩽ k &lt; j ( m [ i , k ] + m [ k + 1 , j ] + p i − 1 p k p j ) . . . . i &lt; j m[i,j] = \left\{\begin{matrix} 0...................................................................i=j\\ \min_{i\leqslant k&lt;j}(m[i,k]+m[k+1,j]+p_{i-1}p_{k}p_{j})....i&lt;j \end{matrix}\right. m[i,j]={0...................................................................i=jminik<j(m[i,k]+m[k+1,j]+pi1pkpj)....i<j
        其中, k k k的取值共 j − i j-i ji种,即 k = i , i + 1 , . . . , j − 1 k=i,i+1,...,j-1 k=i,i+1,...,j1,并且为了输出最佳方案,我们用 s [ i , j ] = k s[i,j]=k s[i,j]=k保存分割点 k k k
    4. 计算最优代价

      1. 上一小节的递归公式我们可以注意到 ,该递归算法时间是指数级的,并不好,所以我们要对其进行适当的简化,注意到每一对满足 1 ≤ i ≤ j ≤ n 1≤i≤j≤n 1ijn i i i j j j对应唯一一个子问题, i i i j j j的选取共 ( n 2 ) + n \binom{n}{2}+n (2n)+n种(其中,n表示i=j时的方案),即 n 2 n^{2} n2量级,然后每个子问题又对应 k k k的取值共 j − i j-i ji种,我们注意到,其中该递归算法对应的递归调用树的不同分支中可能多次遇到同一个子问题。因此,我们可以得到动态规划的另一个标识子问题重叠,另一个是最优子结构。根据之前在钢条切割问题中的方法,为了减少重复计算子问题,我们有两种方案:a.自顶向下的带备忘的方法;b.自底向上法;这里给出较为简单的自底向上法,关键在于将问题规模有小到大解决
      2. 在给出具体算法之前,必须要明确计算 m [ i , j ] m[i,j] m[i,j]需要访问哪些表项,由之前的递归公式可得,必须已知比之规模更小的问题的最优解。
      3. 给出算法伪代码:
      MATRIX-CHAIN-ORDER(p)//p数组表示矩阵链的规模
      	n = p.length-1 //矩阵链长度
      	let m[1..n,1..n] and s[1..n-1,2..n] be new tables //二维数组m[i,j]表示子矩阵链的最小代价,s[i,j]表示子矩阵链的分割点
      	for i =1 to n //申明m[i,i]为0
      		m[i,i] = 0
      	for l = 2 to n // 初始化所有长度从2到n的子矩阵链的最小代价为负值,
      		for i = 1 to n-l+1
      		m[i,j] = ∞
      		for k =i to j-1 // 在i到 j-1中寻找最佳k,使得s[i,j]最小
      			q = m[i,k] +m[k+1,j]+Pi-1PkPj
      			if q<m[i,j]  //保存最佳m[i,j]和分割点k
      				m[i,j] = q
      				s[i,j]=k
      return m and s
      
    5. 构造最优解

    6. 这一步需要指出具体的方案,主要使用 s [ i , j ] s[i,j] s[i,j]来给出具体方案,其中 k k k值指出 A i A i + 1 . . . A j A_{i}A_{i+1}...A_{j} AiAi+1...Aj的分割点在 A k A_{k} Ak A k + 1 A_{k+1} Ak+1之间,所以 A 1.. n A_{1..n} A1..n最优计算方案中最后一次矩阵乘法运算应该是 A 1.. s [ 1 , n ] A s [ n + 1 ] + 1.. n A_{1..s[1,n]}A_{s[n+1]+1..n} A1..s[1,n]As[n+1]+1..n,所以我们可以用相同的方法递归地求出更早的矩阵乘法的具体计算过程。如下给出了可以输出< A 1 , A 2 , . . . , A n A_{1},A_{2},...,A_{n} A1,A2,...,An>的最优括号化方案,其输出为MATRIX-CHAIN-ORDER得到的二维数组s及下标 i i i j j j,调用PRINT-OPTIMAL-PARENS(s,1,n)即可输出< A 1 , A 2 , . . . , A n A_{1},A_{2},...,A_{n} A1,A2,...,An>的最优括号化方案。

    PRINT-OPTIMAL-PARENS(s,i,j) //递归函数求具体方案
    	if i == j //平凡问题直接输出该矩阵
    		print "A"i
    	// 将其抽象为只有两个矩阵时的输出格式
    	else print "("   //否则对于非平凡问题,先给出左括号
    		PRINT-OPTIMAL-PARENS(s,i,s[i,j])   //递归输出左端的具体方案
    		PRINT-OPTIMAL-PARENS(s,s[i,j]+1,j) //递归输出右端的具体方案
    		print ")"  //再给出右括号
    
    1. 以下给出具体java实现代码:
      测试样例矩阵链程度为6时,矩阵规模具体如下表所示:
    矩阵A1A2A3A4A5A6
    规模30*3535*1515*55*1010*2020 *50

    代码:

    import java.util.Scanner;
    
    public class MATRIX_CHAIN_ORDER {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            System.out.println("请输入矩阵链长度n:");
            while(scanner.hasNext()){
    
                int n = scanner.nextInt();
                System.out.println("请输入矩阵链规模(必须位大于0的整型数),长度为"+(n+1)+":");
                int[] p =new int[n+1];
                for(int i = 0;i<=n;i++){//输入矩阵规模
                    p[i] = scanner.nextInt();
                }
                int[][] m = new int[n+1][n+1], s = new int[n+1][n+1];//m用于保存子矩阵链i-j的最小代价,s用于保存相应的分割点k
                for(int i = 1;i<=n;i++){//平凡问题的解为0
                    m[i][i]=0;
                }
                for(int l = 2;l<=n;l++){//求解非平凡问题链长度从2到n
                    for(int i =1;i<=n-l+1;i++){//依次初始化长度从2到n的所有子矩阵链对应的m的值
                        int j = i+l-1;
                        m[i][j] = 100000000;
                        for(int k = i;k<j;k++){//从i到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;//保存最佳切割点
                            }
                        }
                    }
                }
                System.out.println("具体方案为");
                PRINT_OPTIMAL_PARENS(s,1,n);
                System.out.println("最小代价为:"+m[1][n]);
                System.out.println("请输入矩阵链长度n:");
            }
        }
        public static void PRINT_OPTIMAL_PARENS(int[][] s,int i ,int j){
            if(i==j){
                System.out.print("A"+i);
            }
            else{
                System.out.print("(");
                PRINT_OPTIMAL_PARENS(s,i,s[i][j]);
                PRINT_OPTIMAL_PARENS(s,s[i][j]+1,j);
                System.out.print(")");
            }
        }
    }
    

    测试结果为:
    在这里插入图片描述

    以上为动态规划-矩阵链乘法的所有内容。

    展开全文
  • 矩阵链乘法动态规划算法,使用C#实现 50X10,10X40,40X30,30X5 这是示例用的测试数据,输入示例数据可以得到结果
  • 1.问题 在解析中一并给出 2.解析 3.设计 4.分析 5.源码 https://github.com/tangzhejia/algorithm

    1.问题

    在解析中一并给出

    2.解析

    在这里插入图片描述
    在这里插入图片描述

    3.设计

    在这里插入图片描述

    4.分析

    在这里插入图片描述

    5.源码

    https://github.com/tangzhejia/algorithm

    展开全文
  • /*动态规划矩阵链乘*/ typedef struct { int m[MAX][MAX]; int s[MAX][MAX]; }res; void InitP(int* p,int length) { int i; printf("\n初始化序列p,请输入p的维数\n"); for (i=0;i;i++) { printf("p[%d...
  • 矩阵链乘问题描述给定n个矩阵构成的一个链,其中i=1,2,...n,矩阵A的维数为pi-1pi,对乘积 A1A2...An以一种最小化标量乘法次数的方式进行加全部括号。注意:在矩阵链乘问题中,实际上并没有把矩阵相乘,目的是确定一...
  • 设A1, A2, …, An为n个矩阵的序列,其中Ai为Pi-1 * Pi阶矩阵,这个矩阵链的输入用向量P=<P0, P1, …, Pn>给出。给定向量P,确定一种乘法次序,使得基本运算的总次数达到最小。 解析 示例:n=6, P=<10, 5,...
  • 问题 有n个矩阵相乘(A1A2A3...An),任何一个矩阵 Ai的维度为Pi-1 *Pi ; 求如何拆分矩阵相乘使得矩阵乘法次数最小 自顶向下的递归方法 对于任何一个子集Ai...Aj ... 自底向上的动态规划 需要一个二维数组存储...
  • 简单直观理解 矩阵链乘法 带图讲解,动态规划算法
  • 这个例子是求解矩阵链相乘问题的动态规划算法。给定一个n个矩阵的序列(矩阵链)(A1.A2.⋯ ,An)(A_1. A_2. \cdots, A_n)(A1​.A2​.⋯,An​),我们希望计算它们的乘积A1A2⋯AnA_1A_2\cdots A_nA1​A2​⋯An​其中,...
  • //原问题是计算长度为n的矩阵链,子问题是计算长度为L的矩阵链,那么l从2开始扫描,因为l=1时候没有意义,l最长是n-1 for(int l=2;l;l++){ //计算子问题时候,设第一次将左边i个划分在一起是最优解 for(int i=1;i;i++...
  • 用括号的方法表示矩阵连乘的次序,不同的计算次序计算量(乘法次数)是不同,找出一种加括号的方法,使得矩阵连乘的计算量最小。 ​ 设两个矩阵Mixj、Mjxp相乘运算次数则为i x j x p。 示例: ​ A1是M5x10的矩阵...
  • 在分析最优解结构的基础上,用Java语言给出...全文分为四个部分,首先讨论 了动态规划时间效率优化的可行性和必要性,接着给出了动态规划时间复杂度的决定因素,然后分别阐述了对各个决定因 素的优化方法,最后总结全文。
  • 关于运用动态规划解决矩阵链乘法问题的具体步骤
  • 一、问题描述矩阵乘法规则如果A是a*b的矩阵,B是b*c的矩阵,那么AB就是a*c的矩阵,所做的乘法次数为a*b*c矩阵链乘法给定一个矩阵链A1A2A3A4,要计算乘积,给这个矩阵链加上括号,改变运算次序。如果矩阵链为(A1,A2...
  • # coding=utf-8# 算法导论课本 动态规划 矩阵链乘法# 矩阵链乘法的最优加括号方案 根据伪码 使用 python实现# 辅助表 m 保存代价 m[i,j]# 辅助表 s 记录最优值 m[i,j]对应的分割点 kdef maxChain(p):# n = len(p) - ...
  • 所谓矩阵链乘法是指当一些矩阵相乘时,如何加括号来改变乘法顺序从而来降低乘法次数。例如有三个矩阵连乘:A1*A2*A3,其维数分别为:10*100,100*5,5*50.如果按照((A1*A2)*A3)来计算的话,求(A1*A2)要10*100*...
  • 这个是算法作业,C#全套代码,环境是vs2010,矩阵链乘积问题,有界面,导入矩阵链的规模文件,自动给出括号的添加方案。
  • 问题给定一个n个矩阵的序列(即矩阵链,n = , A2A_{2}, …, AnA_{n}>),并计算n个矩阵序列的乘积(S = A1A_{1}A2...A_{2}...不同位置的括号对矩阵乘法的计算代价会产生巨大影响,以矩阵链n = , A2A_{2}, A3A_{3}>为例,其
  • 矩阵链乘法问题 描述: 输入: 输入共n+1行 第一行输入矩阵的总个数n[2,1000] 后n行分别输入矩阵的维数[1,100] 输出: 最后一行输出少乘法次数 输入样例 1: 6 30 35 35 15 15 5 5 10 10 20 20 25 输出...
  • 1、动态规划原理: 适合应用动态规划求解的最优化问题应具备的两个要素:最优子结构和子问题重叠。 1.1、最优子结构: 如果一个问题的最优解包含其子问题的最优解,则该问题具有最优子结构。例子,长度为n的钢条的...
  • 算法:动态规划矩阵链相乘

    万次阅读 多人点赞 2021-02-05 10:22:55
    问题描述 ...用动态规划算法解此问题,可依据其递归式以自底向上的方式进行计算。在计算过程中,保存已解决的子问题答案。每个子问题只计算一次,而在后面需要时只要简单查一下,从而避免大量的重复计
  • import java.util.Scanner; public class MatrixChainOrder { private static int n; private static int[][] m = new int[100][100]; private static int[][] s = new int[100][100];... private st...
  • 动态规划矩阵链乘法

    万次阅读 多人点赞 2015-12-27 14:35:39
    矩阵链乘法  求解矩阵链相乘问题时动态规划算法的另一个例子。给定一个n个矩阵的序列(矩阵链),我们希望计算它们的乘积 A1A2...An  为了计算表达式,我们可以先用括号明确计算次序,然后利用标准的矩阵相乘算法...
  • 动态规划 矩阵链乘法

    千次阅读 2012-05-27 13:40:11
    Description 给定n个矩阵{A1,A2,…,An},其中Ai与Ai+1是可乘...有N个矩阵连乘,用一行有n+1个数数组表示,表示是n个矩阵的行及第n个矩阵的列,它们之间用空格隔开.  Output 你的输出应该有C行,即每组测试数
  • 3、动态规划分析过程 1)最优加全部括号的结构 动态规划第一步是寻找一个最优的子结构。假设现在要计算AiAi+1....Aj的值,计算Ai...j过程当中肯定会存在某个k值(i有分析可以到最优子结构为:假设AiAi+1....Aj的一...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,506
精华内容 1,802
关键字:

动态规划矩阵链乘法