精华内容
下载资源
问答
  • 最优矩阵连乘

    2019-03-02 21:36:37
    一个N*M的矩阵乘以一个M*P的矩阵等于一个N*P的矩阵,运算量为nmp。 矩阵乘法满足结合律,A*B*C可以表示成(A*B)*C或者是A*(B*C),两者的运算量却不同。例如当A=2*3B=3*4C=4*5时,(A*B)*C=64而A*(B*C)=90。显然第一种...

    描述

       一个n*m矩阵由n行m列共n*m个数排列而成。两个矩阵A和B可以相乘当且仅当A的列数等于B的行数。一个N*M的矩阵乘以一个M*P的矩阵等于一个N*P的矩阵,运算量为nmp。
       矩阵乘法满足结合律,A*B*C可以表示成(A*B)*C或者是A*(B*C),两者的运算量却不同。例如当A=2*3 B=3*4 C=4*5时,(A*B)*C=64而A*(B*C)=90。显然第一种顺序节省运算量。
       现在给出N个矩阵,并输入N+1个数,第i个矩阵是a[i-1]*a[i]

    输入格式

    第一行n(n<=100)
    第二行n+1个数

    输出格式

    最优的运算量

    测试样例1

    输入


    2 3 4 5

    输出

    64

    思路:

    dp[i][j]表示i和j之间的最小代价。

    dp[i][j] = min(dp[i][k] + dp[k][j] + a[i] * a[k] * a[j]); i < k < j;

    先计算距离为2的,然后距离为3的,渐次增加。

    #include <iostream>  
    #include <cstdio>  
    #include <cstring>  
    using namespace std;  
      
    const int MAXN = 110;
    const int INF = 0x3f3f3f3f;
    int n, a[MAXN], dp[MAXN][MAXN];
    
    int main()  
    {  
    	scanf("%d", &n);
    	for (int i = 0; i <= n; i++)
    	{
    		scanf("%d", &a[i]);
    	}
    
    	memset(dp, 0, sizeof(dp));
    	for (int r = 2; r <= n; r++)
    	{
    		for (int i = 0; i  + r <= n; i++)
    		{
    			int j = i + r;
    			dp[i][j] = INF;
    			for (int k = i + 1; k < j; k++)
    			{
    				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + a[i] * a[k] * a[j]);
    			}
    		}
    	}
    
    	printf("%d\n", dp[0][n]);
    
        return 0;  
    } 
    

     

    展开全文
  • 最优矩阵连乘的递推写法,备忘录写法,及其用一个二维数组保存最优结果,然后递归打印。 #include <bits/stdc++.h> using namespace std; const int maxn = 100; const int inf = 0x3f3f3f3f; int s[maxn]...

    最优矩阵连乘的递推写法,备忘录写法,及其用一个二维数组保存最优结果,然后递归打印。

    #include <bits/stdc++.h>
    
    using namespace std;
    
    const int maxn = 100;
    const int inf = 0x3f3f3f3f;
    
    
    int s[maxn][maxn];
    struct Mart {
        int h, w;
    }mart[maxn];
    
    int get_ans(int n, int d[][maxn], int *p) {
        for(int i = 0; i <= n; i++) d[i][i] = 0;
        for(int len = 2; len <= n; len++) {
            for(int i = 1; i <= n; i++) {
                int j = i + len - 1;
                if(j > n) break;
                d[i][j] = inf;
    
                for(int k = i; k < j; k++) {
    //                d[i][j] = min(d[i][j], d[i][k] + d[k+1][j] + p[i-1]*p[k]*p[j]);
                    if(d[i][j] > d[i][k] + d[k+1][j] + p[i-1]*p[k]*p[j]) {
                        d[i][j] = d[i][k] + d[k+1][j] + p[i-1]*p[k]*p[j];
                        s[i][j] = k;
                    }
                }
            }
        }
        return d[1][n];
    }
    int get_Ans(int l, int r, int d[][maxn], int *p) {
        if(~d[l][r]) return d[l][r];
        if(l == r) return d[l][r] = 0;
        d[l][r] = inf;
        for(int k = l; k < r; k++) {
    //        d[l][r] = min(d[l][r], get_Ans(l, k, d, p) + get_Ans(k+1, r, d, p) + p[l-1] * p[k] * p[r]);
            if(d[l][r] > get_Ans(l, k, d, p) + get_Ans(k+1, r, d, p) + p[l-1] * p[k] * p[r]) {
                d[l][r] = get_Ans(l, k, d, p) + get_Ans(k+1, r, d, p) + p[l-1] * p[k] * p[r];
                s[l][r] = k;
            }
        }
        return d[l][r];
    }
    
    void print_ans(int l, int r) {
        if(l == r) {
            printf("A%d", l);
            return ;
        }
        int k = s[l][r];
        printf("(");
        print_ans(l, k);
        print_ans(k+1, r);
        printf(")");
    }
    
    int main()
    {
    //    freopen("i.txt", "r", stdin);
        int d[maxn][maxn],p[maxn];
        int n;
        scanf("%d", &n);  // 输入矩阵的个数
        for(int i = 1; i <= n; i++) {
            scanf("%d%d", &mart[i].h, &mart[i].w);  // 矩阵的高and宽
        }
        for(int i = 0; i <= n; i++) {
            if(i == 0) {
                p[i] = mart[i+1].h;
            }
            else p[i] = mart[i].w;
        }
        printf("动态规划方法 ans = %d\n", get_ans(n, d, p));
        print_ans(1, n);
        putchar('\n');
        memset(d, -1, sizeof(d));
        printf("-------------------------------------------\n");
        printf("备忘录方法   ans = %d\n", get_Ans(1, n, d, p));
        print_ans(1, n);
        putchar('\n');
        return 0;
    }
    
    
    展开全文
  • \noindent {\color{blue}动态规划最优矩阵连乘问题:} \hangafter=1\setlength{\hangindent}{0em}给定n个矩阵{A1,A2,…,An},其中Ai 与Ai+1是可乘的,i=1,2…,n-1。如何确定计算矩阵连乘积的计算次序,使得依此...
    
    \documentclass[a4paper]{ctexart}
    \usepackage{amssymb}%%导入数学包
    \usepackage{amsmath}
    \usepackage{indentfirst}
    \usepackage{listings}
    \usepackage{graphicx}
    \usepackage{geometry}
    \usepackage{color} %%设置字体的颜色
    \author{软工1班  163XXX  xxxx}
    \title{算法设计第二次作业}
    \begin{document}
    \maketitle
    \noindent {\color{blue}动态规划最优矩阵连乘问题:}
    
    \hangafter=1\setlength{\hangindent}{0em}给定n个矩阵{A1,A2,…,An},其中Ai 与Ai+1是可乘的,i=1,2…,n-1。如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少?
    
    (1)现在给定矩阵连乘是由7个矩阵构成:
    
    \begin{tabular}{|c|c|c|c|c|c|c|c|} %居中
      \hline
      % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
      矩阵 & A1 & A2 & A3 & A4 & A5 & A6 & A7 \\
      \hline
      行*列 & 30*35 & 35*15 & 15*5 & 5*10 & 10*20 & 20*25 & 25*10 \\
      \hline
    \end{tabular} \\
    
     (2)P是用来存放各个矩阵的行的维数,对P的处理情况如下:
    
    \begin{tabular}{|c|c|c|c|c|c|c|c|c|}
      \hline
      % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
      \hline
      P的下标 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\
      \hline
      P值 & 30 & 35 & 15 & 5 & 10 & 20 & 25 & 10 \\
      \hline
    \end{tabular} \\
    
    (3)m[i][j]表示第i个矩阵至第j个矩阵这段的最优解,对其用值的大小来刻画。
    
    (4)将矩阵连乘积 简记为A[i:j] ,这里i $\leqslant$ j.假设这个最优解在第k 处断开,i$\leqslant$k$<$j,则A[i:j]是最优的,那么A[i,k]和A[k+1:j] 也是相应矩阵连乘的最优解.
    
    设计算A[i:j],1≤i≤j≤n,所需要的最少数乘次数m[i,j],则原问题的最优值为m[1,n] 。
    
    当i=j时,A[i,j]=Ai, m[i,j]=0;(表示只有一个矩阵,如A1,没有和其他矩阵相乘,故乘的次数为0)
    
    当i$<$j时,m[i,j]=min$\{$m[i,k]+m[k+1,j] +pi-1*pk*pj$\}$ ,其中 i$\leqslant$k$<$j。故有:
    
    \begin{equation}
    m[i][j]=
    \begin{cases}
    0,&{i=j} \\
    \min
    $\{${m[i][k]+m[k+1][j]+pi-1*pk*pj}$\}$ &{i<k<j} \\
    \end{cases}
    \end{equation}
    
    (5)代码如下:
    
    \lstset{escapeinside=``}
    \begin{lstlisting}[language=java]
    /**
     *
     * @author Mouse
     *
     */
    
    public class Main {
    
    	static int MatriNum = 7; // `表示矩阵链中矩阵的数目`
    	// `存放各个矩阵的行的维数`
    	static int[] p = { 30, 35, 15, 5, 10, 20, 25, 10 };
    	// `下面是通过数组的形式来表示矩阵的`
    	// `由于数组是从0开始标记的,我们默认从1处开始存储,故下面的MatriNum需要加1`
    	static int[][][] A = new int[MatriNum][][];// `存放要进行连乘的多个矩阵`
    	// `用来存放Ai到Aj的最少乘次数`
    	static int[][] m = new int[MatriNum + 1][MatriNum + 1];
    	// `用来存放Ai到Aj的最后断开位置`
    	static int[][] s = new int[MatriNum + 1][MatriNum + 1];
    
    	// `创建矩阵a,维数为m*n 随机数填充数组内容`
    	public static void CreatMatrix(int[][] a, int m, int n) {
    		for (int i = 0; i < m; i++)
    			for (int j = 0; j < n; j++)
       a[i][j] = (int) Math.round(Math.random() * 50) - 10;
    	}
    // `输出连乘的所有矩阵`
    	public static void printAllM() {
    		for (int i = 0; i < MatriNum; i++) {
    			System.out.println("A" + (i + 1) + ": " 
           + A[i].length + "*"+ A[i][0].length);
    			printM(A[i]);
    		}
    
    	}
    // `输出单个矩阵的值`
    	public static void printM(int[][] a) {
    		for (int i = 0; i < a.length; i++) {
    			System.out.print("   ");
    			for (int j = 0; j < a[i].length; j++)
    				System.out.print("  " + a[i][j]);
    			System.out.println();
    		}
    	}
    public static void traceback(int[][] s, int i, int j, String[] c) {
    		if (i == j)//` Ai.....Aj,当i=j就结束了`
    			return;
    		traceback(s, i, s[i][j], c);
    		traceback(s, s[i][j] + 1, j, c);
    		c[i] = "(" + c[i];
    		c[j] = c[j] + ")";
    	}
    
    // `作用:计算矩阵连乘时,矩阵链的最少乘次数`
    	private static void matrixChain(int[] p, int[][] m, int[][] s) {
    		// `p存放各个矩阵的行的维数, n为题目所给的矩阵的个数`
    		int n = p.length - 1;
    		for (int i = 1; i <= n; i++)
    			m[i][i] = 0;// `矩阵链长度为1,不需要进行乘运算,即m[i][i]值为0`
    		for (int r = 2; r <= n; r++)
    			// `表示目前几个矩阵参与连乘`
    			// `r表示矩阵的长度(2,3…逐渐变长)`
    			for (int i = 1; i <= n - r + 1; i++) {
    				// `从第i个矩阵Ai开始,长度为r,则矩阵段为(Ai~Aj)`
    				int j = i + r - 1;// `当前矩阵段(Ai~Aj)的起始为Ai,尾为Aj`
    				// `求(Ai~Aj)中最小的,其实k应该从i开始,
                    但先记录第一个值,k从i+1开始,这样也可以。`
    				// `例如对(A2~A4),则i=2,j=4,下面一行的`
                    //  `m[2][4]=m[3][4]+p[1]*p[2]*p[4],即A2(A3A4)`
    				m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j];
    				s[i][j] = i;//` 记录断开点的索引`
    				// `循环求出(Ai~Aj)中的最小数乘次数`
    				for (int k = i + 1; k < j; k++) {
    			// `将矩阵段(Ai~Aj)分成左右2部分(左m[i][k],右m[k+1][j]),`
    			// `再加上左右2部分最后相乘的次数(p[i-1] *p[k]*p[j])`
    					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; // `保存最小的,即最优的结果`
    					}
    				}
    			}
    	}
      public static void main(String[] args) {
    		// `随机生成各个矩阵`
    		for (int i = 0; i < MatriNum; i++) {
    			A[i] = new int[p[i]][p[i + 1]];
    			CreatMatrix(A[i], p[i], p[i + 1]);
    		}
    		printAllM();
    		matrixChain(p, m, s);
    		System.out.print("`矩阵链所需的最少乘次数为:"` + m[1][MatriNum]);
    		System.out.println();
    		String[] c = new String[MatriNum + 1];
    		for (int i = 1; i <= MatriNum; i++) {
    			c[i] = "A" + i;
    		}
    
    		traceback(s, 1, MatriNum, c);
    		System.out.print(`"矩阵连乘最优连乘顺序:"`);
    		for (int i = 1; i <= MatriNum; i++) {
    			System.out.print(c[i]);
    		}
    	}
    }
    
    \end{lstlisting}
    
    运行结果为:
    
    \begin{figure}[H]
    \centering
    \scalebox{0.65}{\includegraphics{mouse.png}}
    \caption{测试截图}
    \end{figure}
    
    \noindent {\color{red}A1: 30*35}
    
         13  16  6  -3  31  -6  37  -10  -3  26  -2  -4  35  -5  28  -9  -6  35  23  -3  11  16  30  23  37  -7  21  29  17  1  37  14  -9  0  -7
         16  32  -4  9  10  1  -4  24  27  -1  1  25  5  32  5  13  22  4  35  8  11  1  29  25  29  13  13  38  -8  2  21  16  4  -7  19
         33  -9  29  39  17  -9  19  34  20  8  21  1  18  19  10  -9  -7  33  22  7  -1  13  21  -7  29  8  4  20  24  39  24  20  18  3  10
         13  35  -9  10  17  -3  4  -6  -10  14  -9  26  38  -6  25  4  2  1  18  21  28  17  15  36  9  38  -6  10  34  37  -5  -7  30  10  6
         29  8  29  26  12  -8  -7  -6  6  19  26  12  2  19  23  -5  -4  -1  39  21  29  26  6  -7  34  -10  27  -1  28  -7  34  -3  16  14  30
         26  9  15  5  25  9  22  34  38  33  15  1  30  6  32  6  16  33  -2  33  32  11  4  -9  -4  7  9  -9  16  -7  14  32  38  -3  2
         15  26  15  1  33  15  1  38  30  -7  10  -2  4  4  5  22  12  14  32  22  17  -5  17  7  10  29  22  6  16  -10  40  -10  20  -3  3
         2  8  35  28  29  2  -7  16  -8  9  10  11  10  22  -8  22  -9  12  23  3  18  30  0  30  2  11  -8  32  38  24  22  -9  11  21  36
         6  37  -2  -8  33  15  16  38  34  36  -6  30  15  23  -8  29  4  25  27  -4  -1  1  1  25  -7  8  36  11  35  5  -7  -8  3  39  -3
         34  38  16  30  -2  6  11  27  19  34  -10  40  -1  37  14  1  -8  11  9  -1  1  26  12  22  -3  -3  24  38  11  37  36  -4  -6  9  9
         18  -5  -7  5  31  16  36  22  23  35  6  -2  28  -3  13  35  30  28  34  28  20  6  21  1  10  37  14  1  -8  27  17  35  23  26  -4
         -7  20  35  25  14  27  -3  14  -2  25  -8  37  -9  27  -5  6  15  22  31  24  4  21  31  20  38  28  37  28  4  -4  -4  14  5  25  6
         17  7  -5  4  -2  39  25  24  40  6  -9  17  7  7  17  20  -5  -10  13  1  34  18  0  7  27  37  33  -10  18  0  16  -3  29  21  38
         1  11  5  17  24  2  6  14  37  40  4  -8  31  13  30  -6  -1  2  7  27  -8  -8  24  29  15  -6  37  -9  -4  22  6  1  38  34  9
         -3  22  38  3  12  -2  8  35  3  -7  24  31  -9  33  18  25  35  25  -7  -2  -6  -3  39  22  21  5  10  2  -5  9  40  29  32  -7  20
         -2  20  24  5  33  1  35  27  36  10  36  26  3  1  30  40  19  30  -7  25  8  11  2  29  17  39  10  19  -2  35  -4  17  -5  4  14
         3  17  27  25  30  25  10  3  27  16  10  7  8  18  23  20  27  16  25  8  25  10  19  -3  26  14  6  -6  -8  30  33  -2  13  -10  13
         21  14  39  -4  37  0  15  27  22  13  8  -7  40  8  13  20  23  -4  -5  5  22  27  7  34  19  12  9  11  6  0  3  5  36  10  2
         11  11  -6  33  30  11  7  2  15  9  22  -1  -4  17  2  -3  30  20  22  27  8  18  25  13  23  2  21  24  36  15  37  23  2  36  16
         -6  1  2  31  2  39  -6  25  20  6  -7  35  32  39  13  20  32  -5  -9  -3  12  -1  23  16  26  20  24  6  -2  -1  -3  0  -6  40  38
         34  -9  40  -5  4  24  30  5  5  -9  39  26  32  0  29  11  6  -8  29  -10  13  31  11  0  36  25  -7  4  22  35  28  25  5  -5  11
         33  11  1  8  -8  32  -8  23  15  24  -4  13  -7  12  -2  5  26  2  28  12  20  27  -10  -4  -3  -10  29  16  33  15  -1  37  2  17  16
         -7  23  8  37  -5  9  31  8  31  32  20  31  11  35  13  37  13  22  5  10  -5  17  -9  11  18  19  17  39  17  28  22  17  6  4  15
         -8  22  12  -8  35  27  1  29  19  34  -1  11  1  26  -2  18  33  32  -2  -3  12  16  0  25  -8  9  0  34  2  15  2  12  20  30  20
         33  2  -9  11  20  -9  39  33  5  30  -6  -3  6  13  -9  6  -8  2  35  1  32  36  29  2  6  -3  17  23  27  35  32  -2  30  25  13
         37  25  17  0  5  16  13  6  33  28  36  -7  3  6  -10  21  6  13  22  20  17  34  -1  39  12  19  7  3  23  16  -6  -3  4  -2  14
         -4  16  9  -8  28  21  -4  16  15  17  11  35  39  28  23  10  27  39  23  26  -4  10  -5  -6  25  35  16  20  33  33  1  8  23  -5  35
         -5  -7  7  35  -1  10  31  32  25  30  38  18  11  39  -4  14  -9  15  22  -2  23  -3  5  36  38  -8  5  6  10  15  5  -6  34  7  28
         -9  32  -1  22  19  11  31  8  37  0  -8  -8  18  23  23  5  -1  -6  -5  10  18  32  24  34  2  12  27  13  -2  20  17  19  14  -6  15
         30  35  15  9  15  -8  33  35  1  19  15  -7  7  8  38  14  30  4  12  21  1  24  33  32  20  6  28  37  -4  -9  39  18  22  -4  37
         
    {\color{red}A2: 35*15}
    
         3  9  23  35  5  38  37  25  5  31  -5  -5  1  -7  17
         15  -2  7  37  -10  31  8  18  39  -6  -10  5  0  24  32
         -8  37  35  -8  19  -4  22  26  4  -6  21  3  20  -3  20
         0  1  4  27  31  35  21  25  -10  32  37  31  5  -3  11
         35  8  -2  16  27  12  -6  24  39  39  0  24  18  3  33
         24  14  -5  26  -4  39  3  2  26  -3  38  12  14  22  24
         39  34  -6  15  18  24  37  18  34  25  8  2  8  19  39
         17  32  6  40  12  1  -9  -8  -6  39  22  13  8  22  2
         7  -4  33  3  -6  17  27  20  2  25  1  31  8  -1  22
         -7  3  38  31  9  11  26  9  13  -8  9  -3  5  25  33
         20  -1  26  15  3  33  8  4  35  0  -2  -4  -1  -3  35
         6  25  31  27  38  -4  12  4  17  -9  24  36  4  28  31
         0  37  12  23  31  29  17  33  21  -8  6  32  5  35  5
         13  7  21  29  23  12  6  40  12  24  3  6  40  12  7
         -3  2  -2  -5  26  21  0  2  11  40  30  34  -5  12  -4
         39  15  21  28  20  23  4  -6  39  31  35  -8  25  -9  12
         13  3  5  23  22  23  -9  -8  15  40  30  12  11  38  -6
         22  27  20  -6  3  14  15  36  6  2  -2  16  9  31  7
         -3  26  12  35  25  13  27  13  32  20  7  30  28  33  -9
         7  -6  12  0  30  -1  23  38  34  14  30  32  36  1  4
         28  15  24  3  3  14  3  34  40  -2  24  25  9  -4  36
         32  34  31  7  34  27  7  5  39  29  6  8  17  32  25
         -4  28  2  -9  28  25  3  -7  19  34  -4  17  19  22  22
         8  37  11  -8  -1  0  -6  17  27  1  25  40  10  24  -1
         2  1  28  -9  30  -9  36  15  11  2  9  -5  35  -7  19
         -5  -2  10  5  -6  19  22  -6  17  21  24  -7  2  23  -8
         38  -4  5  29  8  27  -4  39  27  30  -8  -1  4  0  9
         36  27  31  29  13  9  25  -6  17  20  21  36  21  25  35
         25  35  17  35  38  14  17  37  -3  -8  19  22  9  29  29
         12  6  -10  1  17  0  -7  29  -6  8  2  -1  8  30  17
         5  -7  33  1  13  31  19  -7  1  29  7  21  27  5  28
         0  13  12  33  9  22  4  12  4  27  12  17  9  18  11
         22  -4  1  21  -2  30  10  25  37  23  27  40  13  -1  28
         37  32  15  13  3  14  33  29  28  6  10  -5  5  -2  4
         37  14  27  -3  -4  21  6  1  37  -8  8  -5  9  3  6
         
    {\color{red}A3: 15*5}
    
         6  36  18  -4  27
         3  25  -4  38  12
         -8  6  22  1  24
         31  21  39  20  14
         38  3  1  23  10
         -4  4  4  1  37
         39  38  -7  1  -7
         26  -7  22  30  26
         36  18  20  28  -3
         6  9  34  11  13
         -3  27  10  0  33
         -5  5  -1  13  35
         19  25  1  39  13
         5  25  12  4  33
         27  30  -1  24  13
         
    {\color{red}A4: 5*10}
    
         39  5  -8  19  8  2  28  23  18  35
         19  23  17  39  16  38  0  6  19  -8
         1  10  34  26  -9  18  0  29  13  38
         12  25  -5  7  1  30  8  19  -9  5
         40  33  3  -3  5  30  -7  25  -4  10
         
    {\color{red}A5: 10*20}
    
         18  35  21  24  2  0  21  8  25  23  17  -1  21  -5  27  -8  34  35  11  18
         -1  0  5  -4  24  -5  -5  40  25  6  39  36  9  13  3  5  -4  6  24  25
         -4  -6  -7  17  -2  -3  -1  29  21  17  5  37  16  6  7  40  12  35  37  7
         -8  38  5  33  8  16  32  -9  28  22  37  22  -5  18  35  36  22  0  21  32
         -3  28  -9  3  7  15  3  0  -1  25  18  1  15  34  25  39  25  3  3  2
         3  27  22  37  29  13  27  -10  31  -8  36  37  38  29  -8  3  34  20  5  7
         23  7  34  33  15  25  -2  34  30  30  13  -10  -7  2  -5  -3  12  1  3  0
         23  14  2  -9  16  2  33  21  19  1  -6  8  -2  -4  36  34  38  25  9  19
         39  33  20  8  35  30  17  22  15  -6  16  27  4  7  6  3  16  13  22  34
         11  2  35  18  -6  -8  27  36  -3  6  22  -9  10  28  9  36  30  22  -9  8
         
    {\color{red}A6: 20*25}
    
         27  25  25  -9  17  24  24  10  6  -5  4  22  30  -8  11  19  27  3  33  32  20  -5  23  -5  -1
         26  25  20  10  -7  30  2  31  6  -9  4  17  4  6  2  37  -10  23  -10  5  23  20  28  16  23
         28  28  13  26  34  28  34  4  17  32  19  14  31  11  39  -8  36  16  17  5  13  14  34  8  -7
         3  40  8  30  29  3  36  24  27  36  6  33  10  -5  -8  40  29  2  12  13  8  -9  6  16  16
         -4  3  27  23  20  40  -7  30  34  8  1  14  29  17  28  13  -7  -6  -5  19  14  27  29  35  8
         -6  21  5  18  35  1  6  19  1  11  17  37  -8  9  9  17  34  18  38  33  11  1  0  29  -6
         33  35  31  9  26  30  10  31  -9  -8  12  24  28  30  18  5  -4  22  -9  29  2  17  -1  12  32
         37  -1  10  -8  -2  -3  10  15  -1  15  29  29  8  30  -5  21  33  21  1  4  19  33  6  18  36
         -2  28  28  1  26  6  25  9  31  4  25  35  30  8  36  32  -2  5  39  34  33  28  14  31  37
         -5  32  -5  26  32  25  35  3  -3  29  29  4  9  23  2  31  39  2  -2  32  2  0  19  20  33
         37  31  27  -1  31  -4  17  34  -4  -3  -7  2  -7  39  9  8  33  1  38  -8  34  25  39  35  22
         30  29  40  24  5  -9  -5  13  17  35  -2  -2  38  1  -8  2  1  2  6  5  33  9  38  14  17
         24  21  40  10  -6  24  5  -6  27  9  -5  4  5  38  7  8  18  21  -8  8  5  8  -7  27  34
         37  -5  12  -3  24  17  14  12  27  4  -4  -4  -4  34  0  -6  5  -6  16  30  9  17  35  19  33
         20  17  10  10  18  34  40  36  0  29  26  33  -2  11  28  1  -6  19  -10  5  6  -8  -5  9  31
         14  2  2  18  23  19  38  30  3  35  8  18  -2  10  8  30  13  -9  -6  22  22  8  -9  13  18
         9  -9  4  -6  -6  30  -3  37  33  26  -8  31  -3  8  16  23  1  -3  19  36  9  -8  -6  39  13
         36  23  26  -3  18  -7  2  27  16  16  30  13  7  19  -2  29  22  23  3  14  30  1  -4  27  17
         -4  7  14  -2  -4  27  -4  0  35  3  8  -2  7  30  26  11  32  -8  15  31  39  7  31  9  0
         38  5  11  23  18  20  38  -8  12  30  0  36  36  37  1  24  27  -4  37  33  5  31  30  -6  36
         
    {\color{red}A7: 25*10}
    
    36  17  -3  3  3  22  -9  18  28  3
         37  36  -6  -7  3  18  -1  4  29  32
         7  16  39  32  39  26  -7  24  1  24
         12  22  36  0  27  -4  -6  36  19  -6
         34  28  28  31  38  37  23  37  -7  14
         34  11  -8  21  25  29  -7  6  -7  3
         29  29  -6  36  17  -10  23  32  11  30
         8  -4  -8  30  39  20  9  7  6  21
         -2  23  -3  -5  37  -2  0  -8  -7  -2
         35  -1  18  4  34  10  -6  36  9  8
         -2  33  37  -7  38  25  10  14  24  2
         37  16  29  6  3  29  23  5  36  7
         31  34  34  10  6  -3  14  12  34  5
         23  5  35  16  14  26  18  28  27  -6
         28  23  14  37  -5  33  -4  -7  32  7
         18  30  -8  17  2  22  12  13  23  -6
         7  26  22  38  -5  8  -1  -4  14  30
         38  -1  13  24  -2  -9  30  -6  6  36
         -5  16  -4  9  -2  26  -9  34  37  -3
         33  8  0  -7  35  10  17  20  6  19
         16  -6  29  18  8  30  19  28  -7  28
         -5  10  -9  0  20  17  18  -1  6  34
         36  35  39  29  -7  31  -9  34  36  31
         1  -9  17  16  14  8  27  13  1  -5
         18  28  5  22  12  1  20  4  -5  16
         
         
    \end{document}

    展开全文
  • 最优矩阵连乘问题

    2015-03-31 19:12:34
    1.引言 多矩阵连乘 对于一般的矩阵乘法来说,如矩阵A(m,n)与矩阵B(n,p)相乘需要进行的加法次数为m*n*p次乘法。 由于矩阵乘法满足结合律,因此矩阵相乘的结合性,会影响整个计算表达式的乘法执行次数。 如...

    1.引言  多矩阵连乘

    对于一般的矩阵乘法来说,如矩阵A(m,n)与矩阵B(n,p)相乘需要进行的加法次数为m*n*p次乘法。

    由于矩阵乘法满足结合律,因此矩阵相乘的结合性,会影响整个计算表达式的乘法执行次数。

    如下面的例子,其中A(10,5)、B(5,20)、C(20,3):

        (1) ((AB)C) 执行乘法次数为1300次

        (2) (A(BC)) 执行乘法次数为450次

    2.求最优的矩阵结合表达式

    (1)设矩阵连乘积AiAi+1…Aj简记为A[i:j],设最优计算次序在Ak和Ak+1之间断开,则加括号方式为:

        ((AiAi+1…Ak) (Ak+1…Aj) )

    则依照这个次序,先计算A[i:k]和A[k+1:j]然后再将计算结果相乘,计算量是:

        A[i:k]的计算量+A[K+1:j]的计算量+它们两者相乘的计算量

    这里的关键是:计算A[i:j]的最优次序所包含的两个子过程(计算A[i:k]和A[K+1:j])也是最优次序

    (2)具体计算

      设计算A[i,j]需要的乘法次数记为m[i,j]。

        M[i,j] = 0;    (i == j,表示一个矩阵,当然不需要乘法运算)

        M[i,j] = min(M[i,k]+M[k+1,j]+pi*pk*pj);   (k在[i,j)之间取值,表示分割点的位置,求最适合的分割点使得乘法次数最少)

      下面是使用动态规划计算6个矩阵连乘的示意图。可以使用自底向上计算,这样矩阵的分割点好计算。如先计算01两个矩阵乘积,在计算02三个矩阵乘积,在计算03四个矩阵乘积:

           01 12 23 34 45

           02 13 24 35

           03 14 25

           04 15

           05

     3.程序实例

    程序可以根据给出的多个矩阵的行、列,生成最优结合的相乘表达式。

    展开全文
  • 如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。例如,给定三个连乘矩阵{A1,A2,A3}的维数分别是10100,1005和550,采用(A1A2)A3,乘法次数为101005+10550=7500次,而采用A1...
  • 题目大意:给出N个矩阵,要求所有矩阵相乘的值达到最小值
  • 算法提高 矩阵乘法 时间限制:**3.0s 内存限制:**256.0MB 问题描述  有n个矩阵,大小分别为a0*a1, a1*a2, a2*a3, …, a[n-1]*a[n],现要将它们依次相乘,只能使用结合率,求最少需要多少次运算。  两个大小...
  • tyvj1198 最优矩阵连乘

    2016-08-09 21:20:00
    一个N*M的矩阵乘以一个M*P的矩阵等于一个N*P的矩阵,运算量为nmp。矩阵乘法满足结合律,A*B*C可以表示成(A*B)*C或者是A*(B*C),两者的运算量却不同。例如当A=2*3B=3*4C=4*5时,(A*B)*C=64而A*(B*C)=90。显然第一种.....
  • 思路:这道题与最优矩阵连乘的思想一样,那就是分析最优子结构,再根据子结构来定义状态,首先我们假定第一次分割的最优方案是在k处分割,得到0~k与k~L两段木棍,那么如何最优分割0~k与0~L就是它的子问题,我们根据...
  • 题目链接 最优矩阵  一个n×m矩阵由n行m列共个数排列而成。两个矩阵A和B可以相乘当且仅当A的列数等于B的行数。一个n×m的矩阵乘以一个m×p的矩阵等于一个的矩阵,运算量为m*n*p。  矩阵乘法不满足分配律,但...
  • 题目大意:求那个矩阵连乘的最小运算量 思路是采用动态规划: 设a[n][m]为第n个矩阵到第m个矩阵连乘的最小乘法数(n, m >= 1),b[i], b[i -1]为第i个矩阵的行数和列数(i >= 1),那么: 1.a[n]
  • 传送门题目大意: 这是中文题, 自己看吧……解题思路: 1.首先项链是个环, 为了方便复制一份,变为长度乘以2, 这样就避免了计算环. 2.我们只需知道每一段能释放的最大能量,就可以知道总的最大释放能量 3....
  • 最优矩阵连乘积 Accepted: 10 Total Submit: 18 Time Limit: 1000ms Memony Limit: 32768KB Description 在科学计算中经常要计算矩阵的乘积。矩阵A和B可乘的条件是矩阵A的列数等于矩阵B的行数。若A是一个p×...
  • 矩阵连乘算法

    2016-01-04 19:50:34
    算法设计与分析课程 java算法实现矩阵连乘 输入输出都有
  • 矩阵连乘A1...An的最优计算次序。 【样例1输入】 30 35 15 5 10 20 25 【样例1输出】 [[ 0 15750 7875 9375 11875 15125] [ 0 0 2625 4375 7125 10500] [ 0 0 0 750 2500 5375] [ 0 0 0 0 1000 3500] [ ...
  • 动态规划,矩阵连乘最优值,对于矩阵连乘中矩阵发排序,应用动态规划计算
  • 超详细的动态规划解决矩阵连乘

    千次阅读 多人点赞 2020-03-21 21:23:15
    动态规划解决矩阵连乘 问题描述:  给定NNN个矩阵 {A1,A2,A3……An}\{A_1,A_2,A_3……A_n\}{A1​,A2​,A3​……An​},其中 AiA_{i}Ai​ 和 Ai+1A_{i+1}Ai+1​ 和可以相乘的,即: AiA_iAi​ 的行数等于 Ai+1A_{i+...
  • 基于动态规划的矩阵连乘最优方法

    万次阅读 多人点赞 2015-01-12 19:35:54
    问题描述: 在科学计算中经常要计算矩阵的乘积。矩阵A和B可乘的条件是... 为了说明在计算矩阵连乘积时加括号方式对整个计算量的影响,我们来看一个计算3个矩阵{A1,A2,A3}的连乘积的例子。设这3个矩阵的维数分别为10
  • 思路:最优矩阵问题,典型的动态规划题目。 该问题的子问题为“把Ai,Ai+1,……,Aj起来需要多少次乘法”,如果用dp(i,j)表示这个问题的子问题的值, 则状态转移方程:dp(i,j) = min{dp(i,k) + dp(k+1,j) +...
  • 如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。 1、按设计动态规划算法的步骤解题。 (1)找出最优解的性质,并刻划其结构特征。 (2)递归地定义最优值。 (3)以自底向上的方式...
  • 问题:如何得到n个矩阵连乘的最少计算次数的计算顺序?先计算,还是先计算?其中,为矩阵的维度。1、两个矩阵相乘两个矩阵相乘需要多少次运算呢?需要做次乘法。具体来说,它将得到矩阵大小的矩阵,该矩阵中每个元素...

空空如也

空空如也

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

最优矩阵连乘