精华内容
下载资源
问答
  • 这里用矩阵链乘法问题来说明动态规划算法的设计要素。\(A_1,A_2,..,A_n\)表示\(n\)个矩阵的序列,其中\(A_i\)为\(P_{i-1} \times P_i\)阶矩阵,\(i=1,2,...,n\)。向量\(P=\)表示矩阵链的输入,其中\(P_0\)是\(A_1\...

    这里用矩阵链的乘法问题来说明动态规划算法的设计要素。

    \(A_1,A_2,..,A_n\)表示\(n\)个矩阵的序列,其中\(A_i\)为\(P_{i-1} \times P_i\)阶矩阵,\(i=1,2,...,n\)。

    向量\(P=\)表示矩阵链的输入,其中\(P_0\)是\(A_1\)的行数,\(P_1\)是\(A_1\)的列数,\(P_1\)是\(A_2\)的行数,以此类推。

    计算这个矩阵需要做\(n-1\)次两个矩阵的相乘运算,可以用\(n-1\)对括号表示运算次序。

    因为矩阵乘法满足结合律,所以无论采用那种顺序,最后结果都一样,但是采用不同的顺序计算的工作量不同。如何定义两个矩阵相乘的工作量呢?

    所以假设\(A_1\)有\(i\)行\(k\)列,\(A_2\)有\(k\)行\(j\)列。所以\(A_1\)\(A_2\)相乘后的矩阵有\(i\)行\(j\)列,含\(ij\)个元素。

    以元素相乘作为基本运算,乘积中每个元素的计算都需要做j次乘法,于是计算\(A_1A_2\)总共需要\(ijk\)次乘法。

    1.1具体实例

    假设输入的是\(P=<10,100,5,50>\),说明有\(3\)个矩阵相乘。其中,

    \(A_1:10 \times 100\)

    \(A_2:100\times 50\)

    \(A_3:5 \times50\)

    有两种乘法次序:

    \((A_1A_2)A_3\)

    \(A_1(A_2A_3)\)

    执行第一种运算的基本运算次序:\(10 \times 100\times5 + 10 \times 5 \times 50=7500\)

    执行第二种运算的基本运算次序:\(10 \times 100\times50 + 100 \times 5 \times 50=75000\)

    工作量相差达10倍!

    所以我们的问题是:给定向量P,确定一种乘法次序,使得基本运算的总次数最少。

    蛮力算法时间复杂度太大,这里先不讨论。

    我们尝试用动态规划算法,从子问题的划分,递归方程的确定,递归和迭代的实现方法,复杂度分析等方面介绍动态规划算法。

    1.2子问题的划分和递推方程

    我们的优化目标是:基本运算次数的最小化。

    如何界定子问题的边界? 令\(A_i..n\)表示输入的矩阵链。

    如果从前向后划分,得\(A_{1..i}\),i=1,2,...,n,得到的子问题只有后边界。但是在计算子问题\(A_{1..j}\),j>i时,我们不仅需要知道子问题\(A_{1..i}\),也得知道\(A_{i+1..j}\)的信息。

    这说明子问题的划分需要前后两个边界。

    用\(A_i..j\)定义矩阵链\(A_i,A_{i+1},..,A_j\)相乘的子问题,\(m[i,j]\)表示得到乘积\(A_{i..j}\)所用到的最小基本运算次数。

    假定最后一次乘积发生在矩阵链\(A_{i..k}\)和\(A_k+1..j\)之间,即

    \(A_iA_{i+1}..A_j=(A_iA_{i+1}..A_k)(A_{k+1}A_{k+2}..A_j)\)

    \(k=i,i+1,...,j-1\)

    所以子问题\(A_i..j\)的计算依赖于子问题\(A_i..A_k\)和\(A_{k+1}..A_j\)的计算结果。

    即\(m[i,j]\)依赖于\(m[i,k]\)和\(m[k+1,j]\)的值。

    cf08c81590ec8ca780696098b3fb4719.gif

    k代表子问题的划分问题,考虑所有可能的划分,\(i<=k<=j\),从中比较出最小的值。

    \(P_{i-1}P_kP_j\)是最后把两个子矩阵链\(A_{i..k}\)和\(A_{k+1}..j\)的结果矩阵相乘所做的基本运算次数。

    当\(i=j\)时,矩阵链只有一个矩阵\(A_i\),这时乘法次数是\(0\),对应了递推式的初值。

    所以这个问题是满足优化原则的。因为当\(m[i,j]\)达到最小值时,子问题的优化函数值\(m[i,k]\)和\(m[k+1,j]\)也是最小的。

    2.动态规划算法的递归实现

    为了确定每次相乘时加括号的位置,需要设计表\(s[i,j]\)记录\(m[i,j]\)达到最小值时k的划分位置。

    算法RecurMatrixChain(P,i,j)

    输入:矩阵链\(A_i..j\)的输入为向量\(P=\),其中\(i<=k<=j\)

    输出:计算\(A_{i..j}\)的所需最小乘法次数\(m[i,j]\)和最后一次运算的位置\(s[i,j]\)

    if i=j

    then m[i,j]

    m[i,j]

    s[i,j]

    for k

    q

    if q < m[i,j]

    then m[i,j]

    s[i,j]

    return m[i,j]

    求解n个矩阵相乘,只需代入i=1,j=n。

    下面考虑时间复杂度

    cf08c81590ec8ca780696098b3fb4719.gif

    算法在行5执行for循环,k从1到n-1。

    每次进入循环体都在行6进行两个子问题的递归求解,其余工作量都是常数时间。

    化简得:

    cf08c81590ec8ca780696098b3fb4719.gif

    现在介绍一个定理:当\(n>1\)时,$T(n)= \Omega(2^{n-1}) \( 证明:\)n=2,T(2)>=C=C_12^{n-1},C_1=C/2\(为某个正数 假设对于任何小于n大于等于2的k,\)T(k)>=C_12{k-1}$,则存在某个常数$C’$,使得

    cf08c81590ec8ca780696098b3fb4719.gif

    可以看到,通过使用了动态规划的设计思想,相比于蛮力算法,时间复杂度有所改善,但是并没有得到多项式时间的高效算法。为什么?

    以矩阵链\(A_{1..5}\)为例:

    cf08c81590ec8ca780696098b3fb4719.gif

    时间复杂度高的原因:在递归调用中同一个子问题被多次重复计算。

    在整个递归计算中总计产生了\(1+8+24+32+16=81\)个子问题。

    规模为1的子问题有5个,以此类推,得到不同的子问题个数只有\(5+4+3+2+1=15\)个

    说明算法计算的81个子问题中有许多是重复的。

    3.动态规划算法的迭代实现

    迭代计算的关键

    每个子问题只计算一遍

    迭代过程

    从最小子问题开始

    考虑计算顺序,以保证后面用到的值前面已经计算好

    存储结构保存计算结果--备忘录(存储子问题的优化函数值和划分边界)

    解的追踪

    设计标记函数标记每步的决策

    考虑根据标记函数追踪解的算法

    cf08c81590ec8ca780696098b3fb4719.gif

    \(r\)为链长

    算法MatrixChain(P,n)

    输入:矩阵链\(A_{1..n}\)的输入向量\(P=\)

    输出:计算\(A_{i..j}\)的所需最小乘法次数\(m[i,j]\)和最后一次运算的位置\(s[i,j]\)

    令所有的m[i,j]得初值为0

    for r

    for i

    j

    m[i,j]

    s[i,j]

    for k

    t

    if t

    then m[i,j]

    s[i,j]

    时间复杂度:

    行2,3,7都是\(O(n)\),嵌套循环执行\(O(n^3)\)次,内部为\(O(1)\),\(W(n)=O(n^3)\)

    cf08c81590ec8ca780696098b3fb4719.gif

    cf08c81590ec8ca780696098b3fb4719.gif

    解的追踪:

    \(S[1,5]=3 => (A_1A_2A_3)(A_4A_5)\)

    \(S[1,3]=1 => A_1(A_2A_3)\)

    输出:

    计算顺序:\((A_1(A_2A_3))(A_4A_5)\)

    最少的乘法次序:\(m[1,5]=11875\)

    两种比较的实现:

    递归实现:时间复杂度高,空间少

    迭代实现:时间复杂度低,空间消耗多

    原因:递归实现子问题多次重复计算,子问题计算次数呈指数增长。迭代实现每个子问题只计算一遍。

    动态规划时间复杂度:

    备忘录各项计算量之和+追踪解的工作量

    通常追踪解的工作量不超过计算工作量,是问题规模的多项式函数

    4.动态规划算法的要素:

    划分子问题,确定子问题边界,将问题求解变成多步判断的过程。

    定义优化函数,以该函数极大(或极小)值作为依据,确定是否满足优化原则。

    列优化函数的递推方程和边界条件。

    自底向上计算,设计备忘录(表格)。

    考虑是否需要设立标记函数。cf08c81590ec8ca780696098b3fb4719.gif

    扫码关注我们

    微信号:SRE实战

    拒绝背锅 运筹帷幄

    ×

    选择打赏方式:

    微信

    QQ钱包

    支付宝

    打赏

    打赏

    打赏

    多少都是心意!谢谢大家!!!

    ×

    选择分享方式:

    微信扫一扫,分享朋友圈

    Or

    手机扫一扫,精彩随身带

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

    千次阅读 2012-05-27 13:40:11
    Description 给定n个矩阵{A1,A2,…,An},其中Ai与Ai+1是可乘...有N个矩阵连乘,用一行有n+1个数数组表示,表示是n个矩阵的行及第n个矩阵的列,它们之间用空格隔开.  Output 你的输出应该有C行,即每组测试数
     
    

    Description

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

    Input

    有N个矩阵连乘,用一行有n+1个数数组表示,表示是n个矩阵的行及第n个矩阵的列,它们之间用空格隔开. 

    Output

    你的输出应该有C行,即每组测试数据的输出占一行,它是计算出的矩阵最少连乘积次数,输出最优全括号结构

    Sample Input

    10 100 5 50

     

     

    Sample Output

     

    7500
    ((A1A2)A3)

     

     

    分析:

     

    矩阵链乘法问题描述:
     给定由n个矩阵构成的序列[A1,A2,...,An],对乘积A1A2...An,找到最小化乘法次数的加括号方法。
     1)寻找最优子结构
    此问题最难的地方在于找到最优子结构。对乘积A1A2...An的任意加括号方法都会将序列在某个地方分成两部分,也就是最后一次乘法计算的地方,我们将这个位置记为k,也就是说首先计算A1...Ak和Ak+1...An,然后再将这两部分的结果相乘。
    最优子结构如下:假设A1A2...An的一个最优加括号把乘积在Ak和Ak+1间分开,则前缀子链A1...Ak的加括号方式必定为A1...Ak的一个最优加括号,后缀子链同理。
    一开始并不知道k的确切位置,需要遍历所有位置以保证找到合适的k来分割乘积。
     
    2)构造递归解
    设m[i,j]为矩阵链Ai...Aj的最优解的代价,则
              ┌ 0    如果i = j
    m[i,j] = │
              └ min(i≤k<j) {m[i,k] + m[k+1,j] + Ai.row*Ak.col*Aj.col}  如果i < j
     
     3)构建辅助表,解决重叠子问题
    从第二步的递归式可以发现解的过程中会有很多重叠子问题,可以用一个nXn维的辅助表t[n][n]来保存子问题的解,表中每个元素包含2个信息,分别是最优乘积代价及其分割位置k 。
    辅助表t[n][n]可以由2种方法构造,一种是自底向上填表构建,该方法要求按照递增的方式逐步填写子问题的解,也就是先计算长度为2的所有矩阵链的解,然后计算长度3的矩阵链,直到长度n;另一种是自顶向下填表的备忘录法,该方法将表的每个元素初始化为某特殊值(本问题中可以将最优乘积代价设置为一极大值),以表示待计算,在递归的过程中逐个填入遇到的子问题的解。
    备忘录法会比自底向上法慢一个常数因子,因为前者有递归调用的代价,维护表格的开销也稍大。
    #include<stdlib.h>  
    #include<stdio.h>  
    #include <memory.h>  
    #define N 6  
    void Print_OPTIMAL_PARENS(int s[N+1][N+1],int i,int j) //定义函数打印最优全括号的结果  
    {  
        if(i==j)  
            printf("A%d",i);  
        else  
        {  
            printf("(");  
            Print_OPTIMAL_PARENS(s,i,s[i][j]);           //在分裂处进行递归调用  
            Print_OPTIMAL_PARENS(s,s[i][j]+1,j);  
            printf(")");  
        }  
    }  
    int main()  
    {  
        int matrix[N+1];                  //matrix中记录矩阵的维数  
        int i,j,k,q;  
        int m[N+1][N+1];                  //m中记录矩阵连乘的次数  
        int s[N+1][N+1];                  //s[i][j]中记录了对Ai...Aj进行分裂的最优的k值  
        for(i=0;i<=N;i++)  
            scanf("%d",&matrix[i]);  
        memset(m,0,(N+1)*(N+1)*sizeof(int));  
        for(j=1;j<=N;j++)                  
            for (i=j;i>=1;i--)          //当i=j时,m[i][j]=0,                             
            {                           //当i<j时,m[i][j]=min{m[i][k]+m[k+1][j]+p(i-1)p(k)p(j)} i=<k<j                    
                if (j==i)  
                    m[i][j]=0;  
                else  
                {  
                    m[i][j]=600000;   
                    for (k=i;k<j;k++)  
                    {  
                        q=m[i][k]+m[k+1][j]+matrix[i-1]*matrix[k]*matrix[j];  
                        if (q<m[i][j])  
                        {  
                            m[i][j]=q;  
                            s[i][j]=k;  
                        }  
                    }  
                }  
            }  
    printf("%d/n",m[1][N]);  
    Print_OPTIMAL_PARENS(s,1,N);  
    return 0;  
    }  

    另外一种实现最优矩阵链方式函数:

    该函数采用自底向上方法进行计算

    void MatrixChain()  
    {  
        int i, j, k, t;  
        此为初始化底层,即一个矩阵的情况///  
        for(i = 1; i <= n; i++)  
            m[i][i] = 0;//赋值为0,是因为1个矩阵需做0次相乘  
        for(int r = 2; r <= n; r++)  
        {//计算r个矩阵连乘的情况  
            for(i = 1; i <= n - r + 1; i++)  
            {//计算从i个矩阵开始的连续r个矩阵相乘的最少次数  
                j = i + r - 1;//A[i : j],连续r个矩阵  
                以下为其中一种情况,断开点i,即第一个矩阵独立/  
                m[i][j] = m[i + 1][j]  + p[i - 1] * p[i] * p[j];  
                开始寻找最优值///  
                for(k = i + 1; k < j; k++)  
                {  
                    t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];  
                    if( t < m[i][j])  
                        m[i][j] = t;  
                }  
            }  
        }  
    }  


    展开全文
  • 矩阵链乘问题描述给定n个矩阵构成的一个链,其中i=1,2,...n,矩阵A的维数为pi-1pi,对乘积 A1A2...An以一种最小化标量乘法次数的方式进行加全部括号。注意:在矩阵链乘问题中,实际上并没有把矩阵相乘,目的是确定一...

    矩阵链乘问题描述

    给定n个矩阵构成的一个链,其中i=1,2,...n,矩阵A的维数为pi-1pi,对乘积 A1A2...An以一种最小化标量乘法次数的方式进行加全部括号。

    注意:在矩阵链乘问题中,实际上并没有把矩阵相乘,目的是确定一个具有最小代价的矩阵相乘顺序。找出这样一个结合顺序使得相乘的代价最低。

    动态规划分析过程

    1)最优加全部括号的结构

    动态规划第一步是寻找一个最优的子结构。假设现在要计算AiAi+1....Aj的值,计算Ai...j过程当中肯定会存在某个k值(i<=k

    有分析可以到最优子结构为:假设AiAi+1....Aj的一个最优加全括号把乘积在Ak和Ak+1之间分开,则Ai..k和Ak+1..j也都是最优加全括号的。

    2)一个递归解

    设m[i,j]为计算机矩阵Ai...j所需的标量乘法运算次数的最小值,对此计算A1..n的最小代价就是m[1,n]。现在需要来递归定义m[i,j],分两种情况进行讨论如下:

    当i==j时:m[i,j] = 0,(此时只包含一个矩阵)

    当i

    3)计算最优代价

    虽然给出了递归解的过程,但是在实现的时候不采用递归实现,而是借助辅助空间,使用自底向上的表格进行实现。设矩阵Ai的维数为pi-1pi,i=1,2.....n。输入序列为:p=,length[p] = n+1。使用m[n][n]保存m[i,j]的代价,s[n][n]保存计算m[i,j]时取得最优代价处k的值,最后可以用s中的记录构造一个最优解。书中给出了计算过程的伪代码,摘录如下:

    MAXTRIX_CHAIN_ORDER(p)2 n = length[p]-1;3 for i=1to n4 do m[i][i] = 0;5 for t = 2 to n //t is the chain length

    6 do for i=1 to n-t+1

    7 j=i+t-1;8 m[i][j] =MAXLIMIT;9 for k=i to j-1

    10 q = m[i][k] + m[k+1][i] + qi-1qkqj;11 if q

    MATRIX_CHAIN_ORDER具有循环嵌套,深度为3层,运行时间为O(n3)。如果采用递归进行实现,则需要指数级时间Ω(2n),因为中间有些重复计算。

    4)构造一个最优解

    第三步中已经计算出来最小代价,并保存了相关的记录信息。因此只需对s表格进行递归调用展开既可以得到一个最优解。书中给出了伪代码,摘录如下:

    PRINT_OPTIMAL_PARENS(s,i,j) if i==j then print "Ai"

    else

    print "(";PRINT_OPTIMAL_PARENS(s,i,s[i][j]); PRINT_OPTIMAL_PARENS(s,s[i][j]+1,j); print")";

    5)编程实现

    写完传

    展开全文
  • 算法13---动态规划矩阵链乘法 矩阵链乘法是动态规划里面使用到的一个例子 1 两个矩阵的计算 那么对于一个矩阵的乘法,首先如果是两个矩阵的乘法,那么如何实现呢? 注意到我们使用二维数组表示矩阵,但是二...

    算法13---动态规划矩阵链乘法

    矩阵链乘法是动态规划里面使用到的一个例子
     
    1 两个矩阵的计算
     
    那么对于一个矩阵的乘法,首先如果是两个矩阵的乘法,那么如何实现呢?
    注意到我们使用二维数组表示矩阵,但是二维数组不能作为函数的返回值。具体实现如下
     
     1 #include <stdio.h>
     2 #include <stdlib.h>
     3 #include <math.h>
     4 
     5 #define a_rows  3
     6 #define a_columns 4
     7 #define b_rows  4
     8 #define b_columns 3
     9 
    10 void matrix_multiply(int a[a_rows][a_columns],int b[b_rows][b_columns],int c[a_rows][b_columns])
    11 {
    12     if (a_columns!=b_rows)
    13     {
    14         printf("error!can't figure the answer!\n");
    15     }
    16     for (int i = 0; i < a_rows; i++)
    17     {
    18         for (int j = 0; j < b_columns; j++)
    19         {
    20             c[i][j]=0;
    21             for (int k = 0; k< a_columns; k++)
    22             {
    23                 c[i][j]=c[i][j]+a[i][k]*b[k][j];
    24             }
    25         }
    26     }
    27 }
    28 
    29 int main()
    30 {
    31 
    32     printf("it is a easy matrix \n");
    33 
    34     int a[a_rows][a_columns]={{1,1,1,1},{2,2,2,2},{3,3,3,3}};
    35     int b[b_rows][b_columns]={{1,1,1},{2,2,2},{3,3,3},{4,4,4}};
    36     int c[a_rows][b_columns]={0};
    37     matrix_multiply(a,b,c);
    38     for (int i = 0; i < 3; i++)
    39     {
    40         for (int j = 0; j < 3; j++)
    41         {
    42             printf("%d  \n",c[i][j]);
    43             if (j==2)
    44             {
    45                 printf("\n");
    46             }
    47         }
    48     }
    49     return 0;
    50 }

     

    2 矩阵链问题
     
    问题描述
         给定n个矩阵构成的一个链<A 1,A 2,A 3,.......A n>,其中i=1,2,...n,矩阵A的维数为p i-1p i,对乘积 A 1A 2...A 以一种最小化标量乘法次数的方式进行加全部括号。
      换句话说,就是在矩阵链乘问题中,实际上并没有把矩阵相乘,目的是确定一个具有最小代价的矩阵相乘顺序。找出这样一个结合顺序使得相乘的代价最低。
     
    一般的过程如下
    (1)最优括号话方案的结构特征
      假设AiAi+1....Aj的一个最优加全括号把乘积在Ak和Ak+1之间分开,则Ai..k和Ak+1..j也都是最优加全括号的。
     
    (2)一个递归求解方案
         设m[i,j]为计算机矩阵Ai...j所需的标量乘法运算次数的最小值,对此计算A1..n的最小代价就是m[1,n]。现在需要来递归定义m[i,j],分两种情况进行讨论如下:
     
         当i==j时:m[i,j] = 0,(此时只包含一个矩阵)
         当i<j 时:从步骤1中需要寻找一个k(i≤k<j)值,使得m[i,j] =min{m[i,k]+m[k+1,j]+pi-1pkpj} (i≤k<j)。
     
    (3)计算最优代价
    我们不采用递归实现,而是自下向上的借助辅助空间保存中间量实现;
     
    (4)构造一个最优解
     
     
    具体的实现过程如下面所示
     
    还没有调好,主要是二维数组不能作为返回值

     

      1 #include <stdio.h>
      2 #include <stdlib.h>
      3 
      4 #define N 6
      5 #define MAXVALUE 999999
      6 
      7 void recursive_matrix_chain(int *p,int i,int j,int m[N+1][N+1],int s[N+1][N+1]);
      8 int memoized_matrix_chain(int *p,int m[N+1][N+1],int s[N+1][N+1]);
      9 int lookup_chain(int *p,int i,int j,int m[N+1][N+1],int s[N+1][N+1]);
     10 
     11 //我们首先采用递归来实现
     12 void recursive_matrix_chain(int *p,int i,int j,int m[N+1][N+1],int s[N+1][N+1])
     13 {
     14     if (i==j)
     15     {
     16         m[i][j]=0;
     17     }
     18     else
     19     {
     20         int k;
     21         m[i][j]=MAXVALUE;
     22         for (int k = i; k < j; k++)
     23         {
     24             int temp=recursive_matrix_chain(p,i,k,m,s)+recursive_matrix_chain(p,k+1,j,m,s)+p[i-1]*p[k]*p[j];
     25             if (temp<m[i][j])
     26             {
     27                 m[i][j]=temp;
     28                 s[i][j]=k;
     29             }
     30         }
     31 
     32     }
     33 }
     34 
     35 //因为递归的计算量太大,所以我们可以采用备忘录的方法,自顶向下实现
     36 
     37 int memoized_matrix_chain(int *p,int m[N+1][N+1],int s[N+1][N+1])
     38 {
     39 
     40     for (int i = 1; i <=N; ++i)
     41     {
     42         for (int j = 0; j <=N; ++j)
     43         {
     44             m[i][j]=MAXVALUE;
     45         }
     46     }
     47     return lookup_chain(p,1,N,m,s);
     48 }
     49 
     50 int lookup_chain(int *p,int i,int j,int m[N+1][N+1],int s[N+1][N+1])
     51 {
     52     if (m[i][j]<MAXVALUE)
     53     {
     54         return m[i][j];
     55     }
     56     if (i==j)
     57     {
     58         m[i][j]=0;
     59     }
     60     else
     61     {
     62         for (int k = i; i < j; ++k)
     63         {
     64             int temp=lookup_chain(p,i,k,m,s)+lookup_chain(p,k+1,j,m,s)+p[i-1]*p[k]*p[j];
     65             if (temp<m[i][j])
     66             {
     67                 s[i][j]=k;
     68             }
     69         }
     70     }
     71     return m[i][j];
     72 }
     73 
     74 
     75 void print_optimal_parens(int s[N+1][N+1],int i,int j)
     76 {
     77     if (i==j)
     78     {
     79         printf("A%d\n",i);
     80     }
     81     else
     82     {
     83         printf("(");
     84         print_optimal_parens(s,i,s[i][j]);
     85         print_optimal_parens(s,s[i][j]+1,j);
     86         printf(")");
     87     }
     88 }
     89 
     90 int main()
     91 {
     92     int p[N+1] = {30,35,15,5,10,20,25};
     93     int m[N+1][N+1]={0};
     94     int s[N+1][N+1]={0};
     95     int i,j;
     96     memoized_matrix_chain(p,N+1,m,s);
     97     printf("m value is: " );
     98 
     99     for(i=1;i<=N;++i)
    100     {
    101         for(j=1;j<=N;++j)
    102             printf("%d ",m[i][j]);
    103         printf("\n");
    104     printf("s value is: \n");
    105 
    106     for(i=1;i<=N;++i)
    107     {
    108         for(j=1;j<=N;++j)
    109             printf("%d ",s[i][j]);
    110         printf("\n");
    111     }
    112     printf("the result is:\n");
    113     print_optimal_parents(s,1,N);
    114     return 0;
    115 }

     

     

    现在再给出一个c++的版本,一个实现,我是看的别人的,自己可以修改

     

     1 #include <iostream>
     2 using namespace std;
     3 
     4 #define N 6
     5 #define MAXVALUE 1000000
     6 
     7 void matrix_chain_order(int *p,int len,int m[N+1][N+1],int s[N+1][N+1]);
     8 void print_optimal_parents(int s[N+1][N+1],int i,int j);
     9 
    10 int main()
    11 {
    12     int p[N+1] = {30,35,15,5,10,20,25};
    13     int m[N+1][N+1]={0};
    14     int s[N+1][N+1]={0};
    15     int i,j;
    16     matrix_chain_order(p,N+1,m,s);
    17     cout<<"m value is: "<<endl;
    18     for(i=1;i<=N;++i)
    19     {
    20         for(j=1;j<=N;++j)
    21             cout<<m[i][j]<<" ";
    22         cout<<endl;
    23     }
    24     cout<<"s value is: "<<endl;
    25     for(i=1;i<=N;++i)
    26     {
    27         for(j=1;j<=N;++j)
    28             cout<<s[i][j]<<" ";
    29         cout<<endl;
    30     }
    31     cout<<"The result is:"<<endl;
    32     print_optimal_parents(s,1,N);
    33     return 0;
    34 }
    35 
    36 void matrix_chain_order(int *p,int len,int m[N+1][N+1],int s[N+1][N+1])
    37 {
    38     int i,j,k,t;
    39     for(i=0;i<=N;++i)
    40         m[i][i] = 0;
    41     for(t=2;t<=N;t++)  //当前链乘矩阵的长度
    42     {
    43         for(i=1;i<=N-t+1;i++)  //从第一矩阵开始算起,计算长度为t的最少代价
    44         {
    45             j=i+t-1;//长度为t时候的最后一个元素
    46             m[i][j] = MAXVALUE;  //初始化为最大代价
    47             for(k=i;k<=j-1;k++)   //寻找最优的k值,使得分成两部分k在i与j-1之间
    48             {
    49                 int temp = m[i][k]+m[k+1][j] + p[i-1]*p[k]*p[j];
    50                 if(temp < m[i][j])
    51                 {
    52                     m[i][j] = temp;   //记录下当前的最小代价
    53                     s[i][j] = k;      //记录当前的括号位置,即矩阵的编号
    54                 }
    55             }
    56         }
    57     }
    58 }
    59 
    60 //s中存放着括号当前的位置
    61 void print_optimal_parents(int s[N+1][N+1],int i,int j)
    62 {
    63     if( i == j)
    64         cout<<"A"<<i;
    65     else
    66     {
    67         cout<<"(";
    68         print_optimal_parents(s,i,s[i][j]);
    69         print_optimal_parents(s,s[i][j]+1,j);
    70         cout<<")";
    71     }
    72 
    73 }

     

     

    转载于:https://www.cnblogs.com/tao-alex/p/5932555.html

    展开全文
  • 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...
  • 1.问题 在解析中一并给出 2.解析 3.设计 4.分析 5.源码 https://github.com/tangzhejia/algorithm
  • #include using namespace std; const int N=100; int p[N]={0}; int m[N][N]={0}; int s[N][N]={0}; void MATRIX_CHAIN_ORDER(int a) { int n=a; int i,j,k,q,l; for(i=1;i;i++) ...j
  • 关于运用动态规划解决矩阵链乘法问题的具体步骤
  • 动态规划-矩阵链乘法

    2017-07-20 20:40:31
    动态规划-矩阵链乘法
  • 10基于动态规划矩阵链乘法 目录10基于动态规划矩阵链乘法1.问题2.解析3.设计4.分析5.源码 1.问题 设 A1, A2, … , An 为 n 个矩阵的序列,其中 Ai 为 Pi-1 * Pi阶矩阵,这个矩阵链的输入用向量 P = < P0, P1,...
  • 问题描述: 给定一个矩阵求解问题,矩阵的维度为 如何通过改变矩阵乘法的求解顺序来提高计算效率 动态规划求解步骤 Step 1: 分析最优解的性质,刻画其结构特征 ...输入: n为矩阵链乘积的元素个数,p为矩阵链中每...
  • /*动态规划矩阵链乘*/ 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...
  • 关于本题的分析,动态规划矩阵链乘法理解 已经讲的很详细了,我在此仅简单总结一下: A1∗A2A_1*A_2A1​∗A2​生成一个维度是[p0,p2][p_0, p_2][p0​,p2​]的矩阵 (A1A_1A1​的维度为[p0,p1][p_0, p_1][p0​,p1​]...
  • # 算法导论课本 动态规划 矩阵链乘法 # 矩阵链乘法的最优加括号方案 根据伪码 使用 python实现 # 辅助表 m 保存代价 m[i,j] # 辅助表 s 记录最优值 m[i,j]对应的分割点 k def maxChain(p): ...
  • 动态规划矩阵链乘法

    万次阅读 多人点赞 2015-12-27 14:35:39
    矩阵链乘法  求解矩阵链相乘问题时动态规划算法的另一个例子。给定一个n个矩阵的序列(矩阵链),我们希望计算它们的乘积 A1A2...An  为了计算表达式,我们可以先用括号明确计算次序,然后利用标准的矩阵相乘算法...
  • 动态规划实现矩阵链乘法问题 矩阵链乘法问题( matrix-chain multiplication problem )  (1)问题描述  给定n个矩阵的链&lt;A 1 ,A 2 ,…,A n &gt;,其中i=1,2,…,n,矩阵A i的维数为p i-1...
  • 动态规划矩阵链乘法

    千次阅读 2013-08-10 12:54:27
    承接着上一篇的装配线调度问题,下一个要解决的问题是矩阵链乘法问题:给定n个要相乘的矩阵构成序列,
  • 第一行一个整数 n,表示矩阵链的长度(1<=n<=300) 接下来一行n+1个数表示这些矩阵的行数和列数 n+1个数中,每相邻的两个数表示一个矩阵的大小 输出 对于每组数据,输出两行,第一行为计算次数,第二行为计算...

空空如也

空空如也

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

动态规划矩阵链乘法