精华内容
下载资源
问答
  • 2022-05-05 23:30:37

    P1401 矩阵连乘问题

    注意k的分段枚举。(区间dp真是太好玩啦

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=1e3+6;
    struct sq{
        int r,c;
    }s[maxn];
    ll  a[maxn],dp[maxn][maxn];
    int main(int argc, char const *argv[]) {
        int n;
        while (scanf("%d",&n)!=EOF) {
            memset(dp,0,sizeof dp);
            int flag=0;
            for(int i=0;i<n;i++){
                scanf("%d %d",&s[i].r,&s[i].c);
            }
            a[0]=s[0].r;
            for(int i=1;i<n;i++){
                if(s[i].r!=s[i-1].c) {flag=1;break;}
                a[i]=s[i].r;
            }
            a[n]=s[n-1].c;
            if(flag) {std::cout << "invalid argument" << '\n';continue;}
            for(int cnt=2;cnt<=n;cnt++){
                for(int i=0;i+cnt<=n;i++){
                    int j=i+cnt;
                    dp[i][j]=dp[i][j-1]+a[i]*a[j-1]*a[j];
                    for(int k=i+1;k<j;k++){
                        dp[i][j]=min(a[i]*a[k]*a[j]+dp[i][k]+dp[k][j],
                            dp[i][j]);
                    }
                }
            }
            std::cout <<dp[0][n] << '\n';
        }
        return 0;
    }
    
    更多相关内容
  • 本文实例讲述了动态规划之矩阵连乘问题Python实现方法。分享给大家供大家参考,具体如下: 给定n个矩阵{A1,A2,…,An},其中Ai与Ai+1是可乘的,i=1,2 ,…,n-1。如何确定计算矩阵连乘积的计算次序,使得依此次序计算...
  • 主要介绍了Java矩阵连乘问题(动态规划)算法,结合实例形式分析了java实现矩阵连乘的算法原理与相关实现技巧,需要的朋友可以参考下
  • 矩阵连乘问题

    2019-01-28 11:06:46
    输入: 矩阵的个数n,后有n+1个维数 输出:最少的数次数
  • 算法设计与分析实验报告,附已通过源码,...1.问题描述 2.实验目的 3.实验原理 4.实验设计 (包括输入格式、算法、输出格式) 5.实验结果与分析 (除了截图外,实验结果还用图表进行了分析) 6.结论 7.程序源码
  • c/c++矩阵连乘问题

    2018-01-11 18:28:10
    c/c++语言解决矩阵连乘文题,几个矩阵相乘求最佳结合顺序
  • 矩阵连乘问题C++实现

    2022-05-12 09:05:37
    矩阵连乘——动态规划

    1.认真审阅题目,明确题目的已知条件和求解的目标;

    给定n个矩阵{A1,A2,A3……,An},其中Ai与Ai+1(i = 1,2 ,3,4……n-1)是可乘的,加括号的方法表示矩阵连乘的次序,不同加括号的方法所对应的计算次序是不同的。

    2.问题建模

    【例4-2】三个矩阵 A1 A2 A3 连乘,用加括号的方法表示其计算次序。

    3个矩阵相乘,其加括号的方法一共有两种,具体如下:

    【例4-3】4个矩阵连乘,用加括号的方法表示其计算次序。

    4个矩阵连乘,其加括号的方法共有5种,具体如下:
    在这里插入图片描述

    不同加括号的方法所对应的计算量也是不同的,甚至差别很大。由于在矩阵相乘的过程中,仅涉及加法和乘法两种基本运算,乘法耗时远远大于加法耗时,故采用矩阵连乘所需乘法的次数来对不同计算次序的计算量进行衡量。

    【例4-4】三个矩阵 A1 ,A2 ,A3 的行列分别为10×100、100×5、5×50,求例4-2中的两种加括号方法所需要乘法的次数。

    两种加括号方法所需要乘法的次数分别为

    那么,矩阵连乘问题就是对于给定n个连乘的矩阵,找出一种加括号的方法,使得矩阵连乘的计算量最小。

    容易想到的解决方法是穷举法,即对n个矩阵连乘的每一种加括号方法进行乘法次数的统计,从中找出最小的计算量所对应的加括号方法。这种方法的复杂性取决于加括号的方法的种数。对于n个矩阵连乘,其加括号的方法有多少种呢?

    考查矩阵连乘,不管哪种加括号的方法,最终都归结为两部分结果矩阵相乘,这两部分从n个连乘矩阵中的哪个矩阵处分开呢?设可能从A k 和A k+1 处将n个矩阵分成两部分,其中k=1,2,…,n-1。令P(n)代表n个矩阵连乘不同的计算次序,即不同加括号的方式,则n个矩阵连乘加括号的方式可通过两步操作来实现:①分别完成对两部分加括号;②对所得的结果加括号。由此

    解此递推方程可得P(n)实际上是Catalan数,即P(n)=C(n-1),其中 。故穷举法的复杂性非常高,是n的指数级函数,显然,该方法不可行。

    3.算法设计;

    采用自低向上的方法求解最优质的具体的求解步骤设计如下:
    步骤1:确定合适的数据结构,采用二维数组m来存放各个子问题的最优值,二维数组来存放来存放各个子问题的最优策略,(如果s[i][j]=k,则最优加括号的 方法为(Ai……Ak)(Ak+1……,Aj),一维数组P
    步骤2:初始化。令m[i][j] = 0 , s[i][j] = 0,其中 i = 1, 2, ……
    步骤3:循环阶段
    步骤3-1:按照递归关系式计算两个矩阵AiAi+1,相乘时的最优值,并将其存入m[i][i+1],同时将最优决策计入s[i][i+1],i = 1, 2, ……
    步骤3-2:按照递归关系式计算3个矩阵AiAi+1Ai+2相乘时的最优值并将其存入m[i][i+2],同时最优决策计入s[1][i+2],i = 1, 2, ……, n – 2
    以此类推
    步骤3-(n-1):按照递归关系式计算n个矩阵A1,A2,……An相乘时的最优质的并将其存入m[1][n],同时将最优决策计入s[1][n]
    至此,m[1][n]即为原问题的最优值
    步骤4:根据二维数组s记录的最优决策信息来构造最优解
    步骤4-1:递归构造A1,……,As[1][n]的最优解,直到包含一个矩阵结束
    步骤4-2:递归构造As[1][n]+1……An的最优解,直到包含一个矩阵结束
    步骤4-3:将步骤4-1和步骤4-2递归的结果加括号

    4.编码实现;

    
    ```cpp
    #include <iostream>
    using namespace std;
    void MatrixChain(int *p, int n, int  * * m, int * * s)//用于求最优值
    {
    	//初始化 
    	for(int i = 1; i <= n; i ++){
    		m[i][i] = 0;
    		s[i][i] = 0;
    	}
    	for(int r = 2; r <= n; r++){//不同规模的子问题 
    		for(int i = 1; i <= n - r + 1; i++){//每一个规模为r的矩阵连乘序列的首矩阵Ai 
    			int j = i + r - 1;//每个规模为r的矩阵连乘序列的尾矩阵为Aj
    			m[i][j] = m[i+1][j] + p[i-1] * p[i]*p[j];//决策为k=i的乘法次数
    			s[i][j] = i;
    			for(int 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;
    					s[i][j] = k;
    				}
    			} 
    		}
    		 
    	} 
    } 
    void Traceback(int i, int j, int ** s){
    	//s[i][j]记录了断开的位置,即计算A[i:j]的加括号方式为(A[i:s[i][j]]) * A [s[i][j] + 1: j])
    	if(i == j) return;
    	Traceback(i, s[i][j], s);//递归打印A[i:s[i][j]的加括号方式
    	Traceback(s[i][j] + 1, j, s);//递归打印A[s[i][j]+1:j ]的加括号的方式
    	cout << "A" << "[" << i << ":" << s[i][j] << "]" << "乘以" << "A""[" << (s[i][j] + 1) << ":" << j << "]"<< endl; 
    }
    int main(){
    	
    	
    	return 0;
    }
    
    
    ## 5.算法分析;
    
    显然,语句int t = m[i][k] + m[k+1][j] + p [i-1= * p[k]*p[j]为算法MatriChain的基本语句,最坏的情况下该语句的执行次数为O(n的三次方)故散发的最坏时间复杂度为O(n的三次方)
    9.总结。
    
    
    
    展开全文
  • 主要介绍了C语言矩阵连乘 (动态规划)详解的相关资料,需要的朋友可以参考下
  • java算法分析与设计之矩阵连乘问题源代码 算法作为计算机专业学生的必修课,同时也是软件开发过程中必备的编程思想,对学习研究计算机专业意义重大;正因为这门课程难,所以除了相关方面的书籍,网络资源少的可怜,...
  • 问题描述:给定n个矩阵(A1,A2,A3.....An},其中Ai与Ai+1是可乘的,i=1,2,...n-1。考察n个矩阵的连乘积A1A2A3,....An。...所以自然会提出矩阵连乘积的最优计算次序问题。自然,首先想到的是用枚举法,算出每一...

    问题描述:给定n个矩阵(A1,A2,A3.....An},其中Ai与Ai+1是可乘的,i=1,2,...n-1。考察n个矩阵的连乘积A1A2A3,....An。由于矩阵乘法满足结合律,故计算矩阵的连乘积可以有许多不同的计算次序,这种计算次序可以用加括号的方式来确定。加括号的方式决定了整个计算量(指的是乘法调用的次数)。所以自然会提出矩阵连乘积的最优计算次序问题。

    自然,首先想到的是用枚举法,算出每一种加括号情况下的计算量,取最小的情况。工程之庞大可想而知。溯其源,会发现,"枚举“的这种想法是不可避免的,只有所有情况都考虑比较后,才会出现那个最小量乘的结果。普通的枚举导致庞大工程的一个重要因素就是”子问题重复计算“。这里先要明确,什么是矩阵连乘的子问题。

    以A1A2A3A4为例,它的子问题为:A1    A2    A3    A4     A1A2    A2A3     A3A4  A1A2A3   A2A3A4   A1A2A3A4 。你要求A1A2A3A4的最优次序,势必要先求段长为3的子问题的最优次序,而段长为3的子问题是基于段长为2的子问题的基础之上的(这就是一种自底向上的递归)。以此推下去,你很容易会发现两个有意思的现象:第一,假如你已计算出段长为3的子问题的最优次序,那该最优次序下的子问题也是最优的(你可以通过反证法获知);第二,计算完段长为2的子问题,再计算段长为3的子问题时,你还会用到段长为2的子问题的计算结果,那何不把先前的计算结果进行保存,避免重复计算。

    以下就是动态规划算法解决矩阵连乘问题的相关代码,思想无非就两点:

    第一,自底向上的递归式:

    需要指出的是:m[i][j]表示Ai.....Aj的最少数乘次数,k表示求解Ai....Aj的子问题最优值时的断开位置,Pi-1PkPj表示AiAi+1.....Ak和Ak+1....Aj相乘时数乘数。

    第二,在计算过程中,保存已解决的子问题答案。

    #include

    using namespace std;

    void outPut(int i,int j,int **s)

    {

    if(i==j)

    return;

    outPut(i,s[i][j],s);

    outPut(s[i][j]+1,j,s);

    cout<

    cout<

    }

    void MartrixChain(int n,int *p,int **m,int **s)

    {

    for(int t=0;t

    {

    m[t][t]=0; //单一矩阵的情况 一个矩阵数乘次数为0

    s[t][t]=-1;

    }

    for(int l=2;l<=n;l++) //l为段长

    {

    for(int i=0;i<=n-l;i++)

    {

    int j=i+l-1; //j为每段的起点

    m[i][j]=m[i][i]+m[i+1][j]+p[i]*p[i+1]*p[j+1]; //类似于赋初值的功能,其可取i<=k

    s[i][j]=i;

    for(int k=i+1;k

    {

    if(m[i][k]+m[k+1][j]+p[i]*p[k+1]*p[j+1]

    {

    m[i][j]=m[i][k]+m[k+1][j]+p[i]*p[k+1]*p[j+1];

    s[i][j]=k; //记录断点位置

    }

    }

    }

    }

    cout<

    outPut(0,n-1,s);

    }

    int main()

    {

    int num;

    int *dimension;

    int **mm;

    int **ss;

    cin>>num;

    dimension=new int[num+1]; //矩阵维数

    mm=new int*[num];

    ss=new int*[num];

    for(int i=0;i

    {

    mm[i]=new int[num];

    ss[i]=new int[num];

    }

    for(int r=0;r<=num;r++)

    cin>>dimension[r];

    MartrixChain(num,dimension,mm,ss);

    }

    程序实现并不难,但是还是要交代几点容易犯错的细节:

    1.表示矩阵维数的数组大小:应该是矩阵个数+1,理由......呵呵;

    2.若Ai表示连乘矩阵中第i个矩阵,请你时刻记住,实际上的数组下标是从0开始的;(程序中,我是令i从0开始的)

    这两点都可以通过调试修正,只是如果一开始就能想明白,没必要花这种时间。

    运行结果如下:

    我来解释下运行结果  A  1 , 1  and  A  2 , 2     表示(A1A2)是一个分块的  依次为(A1A2)    (A0(A1A2))    (A3A4)    ((A3A4)A5)    (A0A1A2)(A3A4A5)   综合考虑后,最后加括号的方式为:(( A0 ( A1 A2 ) ) ( ( A3 A4 ) A5 ) )   。

    最后,来总结下动态规划算法的要素:1.最优子结构的性质     2.重叠子问题性质

    (在此不再赘述,从问题分析中已经体现)。

    特别想交代下的是,我在问题分析中提到”枚举“一词,个人觉得动态规划就是”变相的枚举“,只是它通过小规模的一步步枚举在缩小范围,进而减少重复枚举,能达到这个目的就是基于上述的两个要素,而动态规划能得到正确的答案,则是因为它已经考虑比较了所有可能的情况(这也是解决任何问题所不能避免的,只是有些是隐式比较而已)。

    还有一个非常欠缺的地方:怎么样直接输出加括号的表达式呢?如(( A0 ( A1 A2 ) ) ( ( A3 A4 ) A5 ) )   。如果无视空间的代价,多开几个数组,用上队列的思想,是可以实现,能不能有更简洁的方法呢?~~~communicating!!!!!!!!

    展开全文
  • 一、实验环境操作系统:Windows 10 64位内存:8GBCPU:i5-5200U 2.20~2.20GHzIDE:Code::Blocks 17.12二、实验内容1) 对于矩阵连乘问题,用递归程序穷举输出所有可能的加括号结果;2) 对1)确定导致宕机的矩阵个数n的...

    一、实验环境

    操作系统:Windows 10 64位

    内存:8GB

    CPU:i5-5200U 2.20~2.20GHz

    IDE:Code::Blocks 17.12

    二、实验内容

    1) 对于矩阵连乘问题,用递归程序穷举输出所有可能的加括号结果;

    2) 对1)确定导致宕机的矩阵个数n的临界值;

    3) 根据1)找出最优解,并把加括号的结果输出;

    4) 对于矩阵连乘问题,用动态规划求最优解,并把加括号的结果输出;

    三、代码实现

    1) 版本1:用递归方法,穷举并对比找出最优解:

    在main函数中的调用方法:

    // 定义新类型typedef pair mul;

    // 辅助函数bool Cmp(const mul m1, const mul m2);

    vector combine(vector v1, vector v2, int left_d, int mid_d, int right_d);

    vector allComb(int *dimensions, int left, int right);

    void allPrint(vector allResult);

    // 测试用的数据int n1 = 4, dimensions1[] = {50, 10, 40, 30, 5};

    int n2 = 5, dimensions2[] = {50, 10, 40, 30, 5, 35};

    int n3 = 6, dimensions3[] = {30, 35, 15, 5, 10, 20, 25};

    int main()

    {

    int n = n1;

    int *dimensions = dimensions1;

    // 递归输出所有可能结果 vector allResult = allComb(dimensions, 1, n);

    allPrint(allResult);

    return 0;

    }

    allComb(找出所有加括号的结果)实现:

    vector allComb(int *dimensions, int left, int right) {

    vector comb;

    if (left == right) comb.push_back(make_pair(to_string(left), 0));

    vector sub1, sub2, temp;

    for (int i = left; i < right; i++) {

    sub1 = allComb(dimensions, left, i);

    sub2 = allComb(dimensions, i + 1, right);

    temp = combine(sub1, sub2, dimensions[left - 1], dimensions[i], dimensions[right]);

    comb.insert(comb.begin(), temp.begin(), temp.end());

    // allPrint(comb);

    }

    return comb;

    }

    辅助函数combine(用于整合子问题的结果)实现:

    vector combine(vector v1, vector v2, int left_d, int mid_d, int right_d) {

    vector result;

    int s1 = v1.size(), s2 = v2.size(), temp_comp;

    string temp;

    for (int i = 0; i < s1; i++) {

    for (int j = 0; j < s2; j++) {

    temp = "(" + v1[i].first + v2[j].first + ")";

    temp_comp = v1[i].second + v2[j].second + left_d * mid_d * right_d;

    result.push_back(make_pair(temp, temp_comp));

    }

    }

    return result;

    }

    辅助函数allPrint(用于输出所有加括号的结果以及最优解)实现:

    void allPrint(vector allResult) {

    sort(allResult.begin(), allResult.end(), Cmp);

    int length = allResult.size();

    cout << "Total: " << length << endl;

    int prox = allResult[0].second, index = 0;

    for (int i = 0; i < length; i++) {

    if (allResult[i].second < prox) {

    prox = allResult[i].second;

    index = i;

    }

    cout << allResult[i].first << endl;

    }

    cout << endl << "Recursive method's result";

    cout << endl << "The proximal solution costs "

    << prox << " times of multiplication. As shown below: " << endl;

    cout << allResult[index].first << endl;

    }

    辅助函数Cmp(自定义排序方式)实现:

    bool Cmp(const mul m1, const mul m2) {

    return m1.first < m2.first;

    }

    2) 版本2:用动态规划找出最优解:

    用到的辅助变量与函数如下:

    // 动态规划求解

    const int Max = 100;

    int complexity[Max][Max], prox[Max][Max];

    void proxComb(int *dimensions, int n, int complexity[][Max], int prox[][Max]);

    void proxPrint(int n, int complexity[][Max], int prox[][Max]);

    string proxString(int prox[][Max], int left, int right);

    proxComb(找出最优的加括号结果)实现:

    void proxComb(int *dimensions, int n, int complexity[][Max], int prox[][Max]) {

    // complexity为记录乘法次数的矩阵,只用到上三角区域

    // 对角线上的元素表示单个矩阵,故而乘法次数为0

    for (int i = 1; i <= n; i++) complexity[i][i] = 0;

    // 外循环为列,内循环从下往上更新complexity

    for (int i = 2; i <= n; i++) {

    for (int j = i - 1; j > 0; j--) {

    // 初始化为从左数第一项

    complexity[j][i] = 0 + complexity[j + 1][i] +

    dimensions[j - 1] * dimensions[j] * dimensions[i];

    prox[j][i] = j;

    // 从左往右寻找更优的组合(如果有)

    for (int k = j + 1; k < i; k++) {

    int temp = complexity[j][k] + complexity[k + 1][i] +

    dimensions[j - 1] * dimensions[k] * dimensions[i];

    if (temp < complexity[j][i]) {

    complexity[j][i] = temp;

    prox[j][i] = k;

    }

    }

    }

    }

    }

    辅助函数proxPrint(用于输出最优解)实现:

    void proxPrint(int n, int complexity[][Max], int prox[][Max]) {

    string result = proxString(prox, 1, n);

    cout << endl << "Dynamic programming's result";

    cout << endl << "The proximal solution costs "

    << complexity[1][n] << " times of multiplication. As shown below: " << endl;

    cout << result << endl;

    }

    辅助函数proxString(递归输出最优解的字符串)实现:

    string proxString(int prox[][Max], int left, int right) {

    if (left == right) {

    return to_string(left);

    }

    int prox_point = prox[left][right];

    string sub1 = proxString(prox, left, prox_point);

    string sub2 = proxString(prox, prox_point + 1, right);

    return "(" + sub1 + sub2 + ")";

    }

    四、代码测试/实验结果

    1) 版本1:

    n = 4时:

    n = 6时:(部分截图)

    n = 15时:(将输出结果的代码注释掉、以及不传入实际矩阵大小,只考虑矩阵个数)

    而到了n = 20时,内存占用大致为85%~95%,应该是可以算出结果来的。但是等了45分钟后还没出结果,所以强制退出了。

    而根据问题规模随n的增长速度来看,估计21~25的时候在本机配置下就会成功死机了。。。

    2) 版本2:作为比较,使用两个版本的结果相互检验

    n = 4时:

    n = 6时:

    The END.

    展开全文
  • 第3章 动态规划;算法总体思想;但是经分解得到的子问题往往不是互相独立的不同子问题的数目常常...3.1 矩阵连乘问题;完全加括号的矩阵连乘积;完全加括号的矩阵连乘积;设有四个矩阵 它们的维数分别是;3.1 矩阵连乘问题;
  • 动态规划问题,基本要素是最优子结构性质,子问题重叠性质,自底向上的求解方法。只要了解了基本要素,那么这种题型也会更好理解。本题有不少注释,便于读者阅读。
  • 动态规划求解矩阵连乘问题

    千次阅读 2021-05-25 05:31:16
    题目给定n个矩阵{A1,A2,…,An}(其中,矩阵Ai的维数为pi-1*pi,i=1,2,3,…,n),如何确定计算矩阵的连乘积A1,A2,…,An的计算次序(完全加括号方式),使得此次序计算矩阵连乘积需要的数乘次数最少。步骤分析最优...
  • DP算法 —— 矩阵连乘问题
  • 参考王晓东《计算机算法设计与分析》(第3版)动态规划章节中的内容
  • 动态规划的理论性和实践性都比较强,一方面需要理解状态、状态转移、最优子结构、重叠子问题等概念,另一方面又需要根据题目的条件灵活设计算法。动态规划是一种用途很广的问题求解方法。它本身并不是一个特定的算法...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 21,834
精华内容 8,733
关键字:

矩阵连乘问题

友情链接: ttt.zip