矩阵连乘

超、凢脫俗 2023-06-23 05:53 117阅读 0赞

给定n个矩阵:A1,A2,…,An,其中Ai与Ai+1是可乘的,i=1,2…,n-1。确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。输入数据为矩阵个数和每个矩阵规模,输出结果为计算矩阵连乘积的计算次序和最少数乘次数。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定,也就是说该连乘积已完全加括号,则可以依此次序反复调用 2 个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为:

( 1 )单个矩阵是完全加括号的;

( 2 )矩阵连乘积 A 是完全加括号的,则 A 可表示为 2 个完全加括号的矩阵连乘积 B 和 C 的乘积并加括号,即 A= ( BC )。

分析:

  1. 矩阵连乘的条件:第一个矩阵的列等于第二个矩阵的行,此时两个矩阵是可乘的;

  2. 多个矩阵连乘的结果矩阵,其行等于第一个矩阵的行和其列等于最后一个矩阵的列。

3.两个矩阵相乘的计算量:

例如:A(4*2),B(2*5) 可知总执行次数为:4×2×5=40

所以矩阵A m*n和B n*k的乘法运算次数为:m*n*k;

  1. 子问题的拆分,在(AiAi+1……Aj)中,先选择一个矩阵Ak,这样的话就将一个大矩阵拆分为两个小矩阵;假设在第k位置上找到最优解,则问题变成了两个子问题:(AiAi+1……Ak),(Ak+1……Aj);用m[i][j]表示矩阵连乘的最优值,那么两个子问题对应的最优值变成m[i][k],m[k+1][j];
  2. 矩阵连乘最优值递归式:

    include

    define N 100// 定义最大连乘的矩阵个数为 100 个

    void matrixChain (int p[],int m[N+1][N+1],int s[N+1][N+1])
    / 用 m[i][j] 二维数组来存储 Ai……Aj 的最小数乘次数,用 s[i][j] 来存储使 Ai……Aj 获得最小数乘次数对应的断开位置 k ,需要注意的是此处的 N+1 非常关键,虽然只用到的行列下标只从 1 到 N 但是下标 0 对应的元素默认也属于该数组,所以数组的长度就应该为 N+1/
    {
    int n=N;// 定义 m,s 数组的都是 n
    n 的,不用行列下标为 0 的元素,但包括在该数组中
    for (int i=1;i<=n;i++)
    m[i][i]=0; / 将矩阵 m 的对角线位置上元素全部置 0 ,此时应是 r=1 的情况,表示先计算第一层对角线上个元素的值 /
    for (int r=2;r<=n;r++)//r 表示斜对角线的层数,从 2 取到 n
    {
    for (int i=1;i<=n-r+1;i++)//i 表示计算第 r 层斜对角线上第 i 行元素的值
    {

    1. int j=i+r-1;//j 表示当斜对角线层数为 r ,行下标为 i 时的列下标
    2. m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];// 计算当断开位置为 i 时对应的数乘次数
    3. s[i][j]=i;// 断开位置为 i
    4. for (int k=i+1;k<j;k++)
    5. {
    6. int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];/* 计算当断开位置 k 为从 i 到 j (不包括 i 和 j )的所有取值对应的 (Ai*......*Ak)*(Ak+1*.......Aj) 的数乘次数 */
    7. if (t<m[i][j])
    8. {
    9. m[i][j]=t;// 将 Ai*......Aj 的最小数乘次数存入 m[i][j]
    10. s[i][j]=k;// 将对应的断开位置 k 存入 s[i][j]
    11. }
    12. }

    }
    }
    }
    void traceback (int i,int j,int s[][N+1])// 用递归来实现输出得到最小数乘次数的表达式
    {
    if (i==j)
    {
    printf (“A%d”,i);
    }
    else
    {
    printf (“(“);
    traceback (i,s[i][j],s);
    traceback(s[i][j]+1,j,s);
    printf (“)”);
    }
    }
    int main ()
    {
    int n;// 用来存储矩阵的个数
    int Q[2N];/ 用 Q 数组来存储最原始的输入(各矩阵的行和列),主要目的是为了检验这 N 个矩阵是否满足连乘的条件 /
    int p[N+1],flag=1;/
    用 p[i-1],p[i] 数组来存储 A 的阶数, flag 用来判断这 N 个矩阵是否满足连乘 /
    int m[N+1][N+1];// 用 m[i][j] 二维数组来存储 Ai
    ……Aj 的最小数乘次数
    int s[N+1][N+1];// 用 s[i][j] 来存储使 Ai……Aj 获得最小数乘次数对应的断开位置 k
    printf (“ 请输入矩阵的个数(小于 100 ) :”);
    scanf (“%d”,&n);
    for (int i=0;i<=2*n-1;i++)// 各矩阵的阶数的输入先存入数组 Q 中接受检验
    {
    if (i%2==0)
    {

    1. printf ("\n");
    2. printf (" 请输入A%d的 行 :",(i/2)+1);

    }
    else
    {

    1. printf (" 列:");

    }
    scanf (“%d”,&Q[i]);
    }
    for (int i=1;i<=2*n-2;i++)// 矩阵连乘条件的检验
    {
    if (i%2!=0&&Q[i]!=Q[i+1])
    {

    1. flag=0;
    2. break;

    }
    }
    for (int j=1;j<=n-1;j++)
    {

    1. p[j]=Q[2*j];

    }
    if (flag!=0)
    {
    p[0]=Q[0];
    p[n]=Q[2*n-1];
    matrixChain (p,m,s);
    printf (“ 式子如下 :\n”);
    traceback(1,n,s);
    printf (“\n”);
    printf (“ 最小数乘次数为 %d\n”,m[1][n]);
    }
    else
    {
    printf (“ 这 %d 个矩阵不能连乘 !\n”,n);
    }
    }

  • 实验结果与分析

(1)实验结果

1.输入正确结果的情况

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNzc3ODA0_size_16_color_FFFFFF_t_70

  1. 输入有误的情况:
  2. watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNzc3ODA0_size_16_color_FFFFFF_t_70 1

(2)分析与收获

经过这个对这个程序的了解和深入研究,渐渐理解了动态规划的基本思想。

发表评论

表情:
评论列表 (有 0 条评论,117人围观)

还没有评论,来说两句吧...

相关阅读

    相关 矩阵

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

    相关 矩阵问题

    问题描述:给定一组可以连乘的矩阵,求最佳相乘顺序,使得总的计算次数最少。 参考代码: 方法一:动态规划 include <stdio.h>