精华内容
下载资源
问答
  • 矩阵链相乘

    2017-12-02 17:25:28
    矩阵链相乘问题,输入n个矩阵的n+1个行列数,计算出最小相乘次数并输出结合方式。
    /*矩阵链相乘问题C++代码
    输入:矩阵数量 n
          这些矩阵的n+1个行列数
    输出:最小相乘次数
          矩阵链相乘结合方式
    */
    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    vector<vector<int>> m(10);
    vector<vector<int>> s(10);
    
    void Matrix_Chain(vector<int> p) {
        int length = p.size() - 1;
        for (int l = 2; l <= length; l++)//矩阵长度
        {
            for (int start = 1; start <= length - l + 1; start++) {
                int end = start + l - 1;
                m[start][end] = INT_MAX;
                for (int k = start; k <= end - 1; k++) {
                    int q = m[start][k] + m[k + 1][end] + p[start - 1] * p[k] * p[end];
                    if (q < m[start][end]) {
                        m[start][end] = q;
                        s[start][end] = k;
                    }
                }
            }
        }
    }
    
    void print(int i, int j) {
        if (i == j)
            cout << char(int('A') + i - 1);
        else {
            cout << "(";
            print(i, s[i][j]);
            print(s[i][j] + 1, j);
            cout << ")";
        }
    }
    
    int main() {
        int n, i, rc[20];
        cout << "请输入矩阵个数:";
        cin >> n;
        cout << "请依次输入这些矩阵的" << n + 1 << "个行列数:";
        for (i = 0; i <= n; i++)
            cin >> rc[i];
        vector<int> p;
        for (int i = 0; i <= n; i++)
            p.push_back(rc[i]);
        for (int i = 0; i < 10; i++) {
            m[i].resize(10);
            m[i][i] = 0;
        }
        for (int i = 0; i < 10; i++)
            s[i].resize(10);
        Matrix_Chain(p);
        int len = p.size() - 1;
        cout << "最少相乘次数:" << m[1][len] << endl;
        cout << "结合方式:";
        print(1, len);
        cout << endl;
        return 0;
    }


    
    
    展开全文
  • 矩阵链相乘算法

    2014-08-28 17:12:08
    用C++实现的矩阵链相乘算法,并包含大量的注释,对理解程序很有帮助
  • @TOC矩阵链相乘的python实现 矩阵链相乘的python实现 关于矩阵链相乘的问题,同样是使用动态规划的思想进行解决, 原理 原理见下图所示: python代码实现 import numpy as np def get_min_matrixchain_mul_num...

    @TOC矩阵链相乘的python实现

    矩阵链相乘的python实现

    关于矩阵链相乘的问题,同样是使用动态规划的思想进行解决,

    原理

    原理见下图所示:
    在这里插入图片描述
    在这里插入图片描述

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

    python代码实现

    import numpy as np
    def get_min_matrixchain_mul_num(matrix_rows):
        #对于一个长度为n的矩阵链相乘,list r 的长度为,n+1,r[0]至r[n-1]为n个矩阵的行数,
        #r[n]为最后一个矩阵的列数
        r = matrix_rows
        #矩阵链的个数n = len(r) -2
        n = len(r) - 1
        C = np.zeros((n, n), dtype=np.int)
        #有上面的初始化可以知道主对角线元素C[i,i]已经填充好,接下来依次填充主对角线上面各对角线的元素
        for d in range(1, n):
            for i in range(0, n-d):
                j = i + d
                sub_multiplition_nums = []
                for k in range(i+1, j+1):d
                    sub_multiplition_nums.append(C[i, k-1] + C[k, j]+r[i]*r[k]*r[j+1])
                C[i, j] = min(sub_multiplition_nums)
        return C[0, n-1]
    
    if __name__ == '__main__':
        M = [5, 10, 4, 6, 10, 2]
        print(get_min_matrixchain_mul_num(M))
        
    

    运行结果如下:

    在这里插入图片描述
    这与课本上所给出的解析答案一致

    展开全文
  • 矩阵链相乘问题

    2020-04-03 17:16:45
    矩阵链相乘问题   问题描述:考虑nnn个矩阵的乘积:A1A2…AnA_1A_2…A_nA1​A2​…An​,确定最优的乘法顺序(最优括号化方案),使得标量(数值)乘法次数最少。其中,AiA_iAi​为$ p_{i-1}⨯pi矩阵,矩阵,矩阵...

    矩阵链相乘问题

      问题描述:考虑nn个矩阵的乘积:A1A2AnA_1A_2…A_n,确定最优的乘法顺序(最优括号化方案),使得标量(数值)乘法次数最少。其中,AiA_ipi1pip_{i-1}⨯p_i矩阵,i=1,2,,ni=1,2,…,n

      对于两矩阵元素相乘,结果矩阵的每一个元素,由原先两矩阵的行列对应元素相乘。因此,假设假设A1m×nA_1为m\times n矩阵,A2n×kA_2为n\times k矩阵,A1A2=m×k×nA_1A_2=m\times k\times n,这么理解一共有m×km\times k个元素,每个元素进行了nn次乘法得到。

      例:假设A110×5A_1为10\times 5矩阵,A25×20A_2为5\times 20矩阵,A120×10A_1为20\times 10矩阵,则有
      (A1A2)A3=10×20×5+10×10×20=3000(A_1A_2)A_3=10\times20\times5+10\times10\times20=3000
      A1(A2A3)=5×10×20+10×10×5=1500A_1(A_2A_3)=5\times10\times20+10\times10\times5=1500

      对于A1A2AnA_1A_2…A_n的乘法顺序总数(P(n)P(n)表示乘法顺序总数)可以由以下递归公式确定:
    P(n)={1n=1,2i=1n1P(i)P(ni)n>2 P(n)=\begin{cases} 1&n=1,2\\ \sum_{i=1}^{n-1}P(i)P(n-i)&n>2 \end{cases}
    结果称为CatalanCatalan数,这个序列的增长速度为Ω(4n/33/2)\varOmega(4^n/3^{3/2})因此要想使用暴力搜索是不现实的。

      假设S(1,n)S(1,n)所需的最少乘法次数我们有可以得到
    S(1,n)=min1i<n(S(1,i)+S(i+1,n)+p1pnpi) S(1,n)=\underset{1\le i<n}{\min} (S(1,i)+S(i+1,n)+p_1p_np_i)
    可知,这个问题符合最优子结构特征,可以由子问题的解组合得到。

      由此我们考虑如何实现这个算法,为了自顶向上的求解这个问题,我们需要知道如何更新S[i,j]S[i,j],可得:
    S[i,j]={0i=jmini<k<j(S(i,k)+S(k+1,j)+pipjpk)i<j S[i,j]=\begin{cases} 0&i=j\\ \underset{i<k<j}{\min} (S(i,k)+S(k+1,j)+p_ip_jp_k)&i<j \end{cases}
    以上是最少次数的迭代公式,为了构造出最终的最优括号方案,我们用另外的K[i,j]K[i,j]记录S[i,j]S[i,j]时的kk值。
    K[i,j]={0i=jarg{k:mini<k<j(S(i,k)+S(k+1,j)+pipjpk)}i<j K[i,j]=\begin{cases} 0&i=j\\ \arg\{k:\underset{i<k<j}{\min} (S(i,k)+S(k+1,j)+p_ip_jp_k)\}&i<j \end{cases}
    代码下载

    #include <iostream>
    #include <vector>
    #include <string>
    using namespace std;
    
    //构造最优解 
    void ConstructBestAnswer(const vector<vector<int>> &k,int i,int j,string &str){
        if(i>j) return;
        if(i==j) str+=("A"+to_string(i));
        else
        {
            // cout<<i<<","<<j<<endl;
            str+="(";
            ConstructBestAnswer(k,i,k[i][j],str);
            ConstructBestAnswer(k,k[i][j]+1,j,str);
            str+=")";
        }
    }
    
    string MatrixChainMultiplication(const vector<int> &MC){
        if(MC.size()<=2) return "输入不正确";
        int n = MC.size()-1;
        //初始化两个二维数组
        vector<vector<int>> S(n,vector<int>(n,0)),K(n,vector<int>(n,0));
        for (int j = 0;j < n; j++)
        {
             
            //更新S[i][j],其中i<=j
            for (int i = j; i >= 0; i--)
            {
                if(i==j) {K[i][j] = i;continue;}
                //设置起始的S[i][j],K[i][j]
                S[i][j] = S[i][i]+S[i+1][j] + MC[i]*MC[i+1]*MC[j+1];
                K[i][j] = i;
                //因为已经计算过从i开始的顺序,所以以下从i+1开始
                for (int k = i+1; k < j; k++)
                {
                    int tmp = S[i][k] + S[k+1][j] + MC[i]*MC[j+1]*MC[k+1];
                    if(S[i][j]>tmp){
                        S[i][j] = tmp;
                        K[i][j] = k;
                    }
                }
                
            }
            
        }
    
        // for (size_t i = 0; i < n; i++)
        // {
        //     for (size_t j = 0; j < n; j++)
        //     {
        //         cout<<S[i][j]<<",";
        //     }
        //     cout<<endl;
        // }
        // for (size_t i = 0; i < n; i++)
        // {
        //     for (size_t j = 0; j < n; j++)
        //     {
        //         if(i<=j) cout<<K[i][j]<<",";
        //     }
        //     cout<<endl;
        // }
        cout<<"最优解:"<<S[0][n-1]<<endl;
        string ans;
        ConstructBestAnswer(K,0,n-1,ans);
        return ans;
        
    }
    
    
    int main(){
        //算法导论上的案例
        vector<int> input = {30,35,15,5,10,20,25};
        cout<<MatrixChainMultiplication(input)<<endl;
        system("pause");
        return 0;
    }
    

    运行截图;

    在这里插入图片描述

    Reference

    《算法导论》第十五章

    展开全文
  • 用动态规划策略求矩阵链相乘的最小乘法次数及乘法方式
  • 矩阵链相乘问题 矩阵的乘法定义如下:设A是m×p的矩阵,B是p×n的矩阵,则A与B的乘积为m×n的矩阵,记作C=AB,其中,矩阵C中的第i行第j列元素c​ij ​​ 可以表示为: 当多个矩阵相乘时,采用不同的计算顺序所需的...

    矩阵链相乘问题

    矩阵的乘法定义如下:设A是m×p的矩阵,B是p×n的矩阵,则A与B的乘积为m×n的矩阵,记作C=AB,其中,矩阵C中的第i行第j列元素c​ij
    ​​ 可以表示为:
    在这里插入图片描述
    当多个矩阵相乘时,采用不同的计算顺序所需的乘法次数不相同。例如,A是50×10的矩阵,B是10×20的矩阵,C是20×5的矩阵, 计算ABC有两种方式:(AB)C和A(BC),前一种需要15000次乘法计算,后一种则只需3500次。
    设A1 ,A2,…,An 为矩阵序列,Ai是阶为P​i−1 ∗Pi的矩阵(1≤i≤n)。试确定矩阵的乘法顺序,使得计算A1A2…A​n过程中元素相乘的总次数最少。
    输入格式:
    每个输入文件为一个测试用例,每个测试用例的第一行给出一个正整数n(1≤n≤100),表示一共有n个矩阵A1 ,A2,…,An ,第二行给出n+1个整数P0,P1,…,Pn,以空格分隔,其中1≤Pi≤100(0≤i≤n),第i个矩阵Ai是阶为Pi-1*Pi的矩阵。

    输出格式:
    获得上述矩阵的乘积,所需的最少乘法次数。

    输入样例:
    在这里给出一组输入。例如:

    5
    30 35 15 5 10 20
    

    输出样例:
    在这里给出相应的输出。例如:

    11875
    
    #include<iostream>
    using namespace std;
     
    const int size=1500;
    int p[size];
    int m[size][size];
    int n;
     
    void matrixchain(){
    	int i,r,j,k;
    
    	for(r=2;r<=n;r++){
    		for(i=1;i<=n-r+1;i++){
    			j=i+r-1;
    			m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];
    			for(k=i+1;k<j;k++){
    				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;
    				}
    			}
    		}
    	}
    }
    
     
    int main(){
    	cin>>n;
    
    	for(int i=0;i<=n;i++)
    		cin>>p[i];
    
    	matrixchain(); 
    
    	cout<<m[1][n]<<endl;
    	
    	return 0;
    }
    

    当size设为101时,段错误,需要把值设大,200也不行,不知道为什么。

    展开全文
  • C语言矩阵链相乘问题

    2009-03-31 21:13:17
    实现求矩阵链相乘最小次数的问题,输入矩阵个数,以及各个矩阵的行数和最后一个矩阵的列数;输出MATCHAIN算法的二维数组与最小相乘次数
  • PTA-矩阵链相乘问题

    2020-10-12 22:54:08
    PTA-矩阵链相乘问题问题描述递归法动态规划法 问题描述 递归法 #include <iostream> using namespace std; const int MAX = 1005; int p[MAX]; int m[MAX][MAX]; int LookupChain(int i, int j){ if(m[i]...
  • 3-5 矩阵链相乘问题

    2020-08-10 11:00:01
    3-5 矩阵链相乘问题 输入格式: 输出格式: 获得上述矩阵的乘积,所需的最少乘法次数。 输入样例: 5 30 35 15 5 10 20 输出样例: 11875 代码如下: 参考链接1 参考链接2 矩阵链乘法(Matrix Chain Multiplication...
  • 矩阵链相乘问题也是动态规划中十分经典的问题,与之前遇到的动态规划问题略有不同的地方是循环顺序的设置,在后面会提到。 输入 一个数n,表示有n个矩阵相乘 之后一行是n + 1个数,表示这n个矩阵的行列信息 如: 3 ...
  • (1)设计暴力法,产生所有矩阵链相乘以组合情况,写出代码,并调试成功; (2)设计动态规划算法,写出代码,寻找最小乘法次数和对应相乘的顺序,并调试成功;(3)随机产生由10个矩阵,测试(2)的代码,输出最小...
  • 算法课程的学习,有很多的帮助,算法设计与分析矩阵链相乘形象的描述
  • 矩阵链相乘 题目 输入 n表示矩阵的个数(<=100) n+1个数,表示矩阵(<=100) 输出 最小的乘法次数 Sample Input 5 5 10 4 6 10 2 Sample Output 348 解题思路 本题动态转移方程的关键点在于加上的值是a[j]*a[i+j...
  • 动态规划——矩阵链相乘问题引入矩阵连乘的开销加括号的方式总数 引入 矩阵连乘的开销 给出一个有n个矩阵(任何相邻的两个矩阵均相容)的矩阵序列(<A1,A2,…,An>)求它们的乘积(A1A2…An)。 一般的做法是按照从...
  • 矩阵链相乘{\color{Cyan} 矩阵链相乘 }矩阵链相乘 Description Input n表示矩阵的个数(&amp;amp;amp;amp;amp;lt;=100) n+1个数,表示矩阵(&amp;amp;amp;amp;amp;lt;=100) Output 最小的乘法次数 ...
  • 动态规划实例:矩阵链相乘 1.动态规划问题分析方法 1.通过建模,要把约束条件写出来。 2.一定要注意判定是否满足优化原则。 2.矩阵链相乘的描述 3.矩阵相乘的基础回顾 4.一个实例来理解这个计算...
  • SSL·矩阵链相乘【DP】

    2018-12-16 11:42:38
    矩阵链相乘【DP】Description--Input--Output--解题思路代码 Description– Input– 第一行,n表示矩阵的个数(n&amp;amp;amp;amp;lt;=100)。 第二行,n+1个数。 Output– 最小的乘法次数 解题思路 ...

空空如也

空空如也

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

矩阵链相乘