精华内容
下载资源
问答
  • 动态规划矩阵连乘问题
    千次阅读
    2018-06-18 20:47:05

    习要学的,博客是要写的,怪兽是要慢慢打的。

    给定n个人矩阵{A1,A2,·······,An},其中,Ai与Ai+1是可乘的,i=1,2,3,····n-1。考查矩阵的连乘积A1,A2,····An。由于矩阵乘法满足结合律,故计算矩阵的连乘积可以有多种不同的计算次序。  次序由加括号的方式来确定。

    m=[[0,0,0,0,0],#储存计算最优值
       [0,0,0,0,0],
       [0,0,0,0,0],
       [0,0,0,0,0],
       [0,0,0,0,0]
       ]
    s=[[0,0,0,0,0],#储存最佳分开位置
       [0,0,0,0,0],
       [0,0,0,0,0],
       [0,0,0,0,0],
       [0,0,0,0,0]
       ]
    p=[2,3,4,5,6]
    r=2
    n=4
    while(r<=n):#按列循环
        i=1
        while(i<=(n-r+1)):#按行循环
            j=i+(r-1)
            m[i][j]=m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j]
            s[i][j]=i
            k=i+1
            while(k<j):#行内找出最优解,并存入mzho
                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
                k+=1
            i+=1
        r+=1
    row=0
    
    
    while (row<=4):
        print(s[row])
       
        row+=1
    row=0
    while (row<=4):
        print(m[row])
       
        row+=1
    def traceback(i,j):
        if i==j:
            return
        traceback(i,s[i][j])
        traceback(s[i][j]+1,j)
        print("A %d, %d * A%d, %d" %(i,s[i][j],s[i][j]+1,j))
    traceback(1,4)

    更多相关内容
  • 本文实例讲述了动态规划矩阵连乘问题Python实现方法。分享给大家供大家参考,具体如下: 给定n个矩阵{A1,A2,…,An},其中Ai与Ai+1是可乘的,i=1,2 ,…,n-1。如何确定计算矩阵连乘积的计算次序,使得依此次序计算...
  • #include <iostream> using namespace std; #define N 7 int MatrixChain(int *p,int n,int m[][N],int s[][N]) { for(int i=1;i<=n;i++){ m[i][i]=0; } ... m[i][j]=m[i][i]+m
    #include <iostream>
    
    using namespace std;
    
    #define N 7
    int MatrixChain(int *p,int n,int m[][N],int s[][N])
    {
    	for(int i=1;i<=n;i++){
    		m[i][i]=0;
    		
    	}
    	for(int r=2;r<=n;r++){
    		for(int i=1;i<=n-r+1;i++){
    			int j=i+r-1;
    			m[i][j]=m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j];
    			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[][N]){
    	if(i==j){
    		cout<<"A"<<i;
    		
    	}
    	else{
    		cout<<"(";
    		Traceback(i,s[i][j],s);
    		Traceback(s[i][j]+1,j,s);
    		cout<<")"; 
    	}
    }
    int main()
    {
    	int p[N]={30,35,15,5,10,20,25};
    	int m[N][N],s[N][N];
    	MatrixChain(p,N-1,m,s);
    	Traceback(1,6,s);
    	return 0;
    	
        
    }
    
    展开全文
  • 主要介绍了C语言矩阵连乘 (动态规划)详解的相关资料,需要的朋友可以参考下
  • 动态规划问题,基本要素是最优子结构性质,子问题重叠性质,自底向上的求解方法。只要了解了基本要素,那么这种题型也会更好理解。本题有不少注释,便于读者阅读。
  • 动态规划算法中矩阵连乘的实现代码,主要是用C语言编写;
  • 记住两个矩阵相乘次数的计算方法 (虽然我自己不是很理解 但是时间紧急先记住 把算法理清) 这里看不明白的可以看下面的演算过程 X并不代表通常数字计算的那种意义

    在这里插入图片描述
    在这里插入图片描述
    记住两个矩阵相乘次数的计算方法 (虽然我自己不是很理解 但是时间紧急先记住 把算法理清)

    在这里插入图片描述在这里插入图片描述
    在这里插入图片描述
    这里看不明白的可以看下面的演算过程 X并不代表通常数字计算的那种意义
    在这里插入图片描述
    在这里插入图片描述

    #include<iostream>
    
    using namespace std;
    
    int main()
    {
    	int n,r[100];//矩阵个数 矩阵大小 r1 r2 r3 …rn r(n+1)
    	int m[100][100],com[100][100];
    	int i,j,t;//for循环变量 
        printf("How many matrixes:");
    	scanf("%d",&n);
        printf("How size every matrixe:");
        for(i=1;i<=n+1;i++)
    		scanf("%d",&r[i]);
    	//初始化数组com和m
    	for (i=1;i<=n;i++){
            for (j=1;j<=n;j++)    
    			com[i][j]=0;}
    	for (i=1;i<n;i++){    //因为需要保证i+1<=n  所以i<n 
    		m[i][i]=0;  //m(i)(i)=0
            m[i][i+1]= r[i]*r[i+1]*r[i+2];     // m(i)(i+1)
            com[i][i+1] = i;//
        }
    	m[n][n]= 0;//情况补足
    	//动态规划过程 j-i>=2时 例如m13 
    	for ( int s =2; s<=n-1; s++){//i+s<=n  min(i)=1 s<=n-1 
        	for (i=1;i<n-s+1;i++){  //mij i的范围 <=n+1-s 
    			j=i+s;//mij j=i+s
    			m[i][j] =m[i][i] +m[i+1][j] + r[i]*r[i+1]*r[j+1]; //通式代入 k=i时  
                com[i][j] = i;//记录最小次数时的k值 
                for (int k=i+1;k<j;k++){//k<j  若为j则出现 r[i]*r[j+1]*r[j+1]   
    				t=m[i][k]+m[k+1][j]+ r[i]*r[k+1]*r[j+1];//通式代入 
                    if (t <m[i][j]){ //所算次数小于当前记录的最小次数 
    					m[i][j] = t; //更新当前记录的最小次数 
    					com[i][j]= k;//记录此时的k值情况 
    				}     
    			}	
            }
    	
    	} 
    	printf("The least  calculate  quantity:%d",m[1][n]);//最终所要求的结果 
    	for (i=1;i<=n;i++){   
    		printf("\n");          
            for (j=1;j<=n;j++)
    			printf("%d",com[i][j]);//输出k值记录矩阵 
       }
    }
    
    
    
    展开全文
  • 动态规划自底向上分析图: 这里需要注意:题目要求的仅仅是结合律 而没有要求交换律。所以判断是否可,并不需要单独去判断。在递归的过程中如果出现前面一个矩阵的j和下一个矩阵的i不相同,则说明不可。 ...

     

    动态规划自底向上分析图:

    这里需要注意:题目要求的仅仅是结合律 而没有要求交换律。所以判断是否可乘,并不需要单独去判断。在递归的过程中如果出现前面一个矩阵的j和下一个矩阵的i不相同,则说明不可乘。

    经过分析以后,我们通过自底向上的方式完成算法的设计即可。

    参考算法1:(据说存在错误)

    #include<bits/stdc++.h>
    using namespace std;
    int N;
    int main(){
    	while(cin>>N){
    		N+=1;
    		int tempx,tempy;int p[N+1];int flag=1;
    		for(int i=1;i<N;i++){
    			cin>>tempx>>tempy;
    			if(i==1){
    				p[0]=tempx;p[1]=tempy;
    			}else{
    				if(tempx!=p[i-1]) {
    					cout<<"invalid argument"<<endl;
    					flag=0;break;
    				}
    			}
    			p[i]=tempy;
    		}
    	if(flag==0) continue;
    	int m[N][N],s[N][N];int length=N;
    	int n=length-1,l,i,j,k,q=0;
        //m[i][i]只有一个矩阵,所以相乘次数为0,即m[i][i]=0;
        for(i=1;i<length;i++)
        {
            m[i][i]=0;
        }
        //l表示矩阵链的长度
        // l=2时,计算 m[i,i+1],i=1,2,...,n-1 (长度l=2的链的最小代价)
        for(l=2;l<=n;l++)
        {
            for(i=1;i<=n-l+1;i++)
            {
                j=i+l-1; //以i为起始位置,j为长度为l的链的末位,
                m[i][j]=0x7fffffff;
                //k从i到j-1,以k为位置划分
                for(k=i;k<=j-1;k++)
                {
                    q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
                    if(q<m[i][j])
                    {
                        m[i][j]=q;
                        s[i][j]=k;
                    }
                }
            }
        }
        cout <<m[1][N-1]<< endl;	
    	}
    	return 0;
    }

    参考算法2:运行没问题 但是超时了 说明效率还不够快

    //3d1-1 重叠子问题的递归最优解
    //A1 30*35 A2 35*15 A3 15*5 A4 5*10 A5 10*20 A6 20*25
    //p[0-6]={30,35,15,5,10,20,25}
    #include<bits/stdc++.h>
    using namespace std; 
    int N;
    int RecurMatrixChain(int i,int j,int **s,int *p);//递归求最优解
    void Traceback(int i,int j,int **s);//构造最优解
    int RecurMatrixChain(int i,int j,int **s,int *p){
    	if(i==j) return 0;
    	int u = RecurMatrixChain(i,i,s,p)+RecurMatrixChain(i+1,j,s,p)+p[i-1]*p[i]*p[j];
    	s[i][j] = i;
     
    	for(int k=i+1; k<j; k++)
    	{
    		int t = RecurMatrixChain(i,k,s,p) + RecurMatrixChain(k+1,j,s,p) + p[i-1]*p[k]*p[j];
    		if(t<u)
    		{
    			u=t;
    			s[i][j]=k;
    		}
    	}
    	return u;
    }
     
    void Traceback(int i,int j,int **s)
    {
    	if(i==j) return;
    	Traceback(i,s[i][j],s);
    	Traceback(s[i][j]+1,j,s);
    	cout<<"Multiply A"<<i<<","<<s[i][j];
    	cout<<" and A"<<(s[i][j]+1)<<","<<j<<endl;
    }
    int main()
    {
    	while(cin>>N){
    			N+=1;
    			int tempx,tempy;int p[N+1];int flag=1;
    			for(int i=1;i<N;i++){
    				cin>>tempx>>tempy;
    				if(i==1){
    					p[0]=tempx;p[1]=tempy;
    				}else{
    					if(tempx!=p[i-1]) {
    						cout<<"invalid argument"<<endl;
    						flag=0;break;
    					}
    				}
    				p[i]=tempy;
    			}
    		if(flag==0) continue; 
        int **s = new int *[N];
    	for(int i=0;i<N;i++)  
        {  
    		s[i] = new int[N];  
        } 
        cout<<RecurMatrixChain(1,N-1,s,p)<<endl;
    	//cout<<"矩阵的最少计算次数为:"<<RecurMatrixChain(1,N-1,s,p)<<endl;
    	//cout<<"矩阵最优计算次序为:"<<endl;
    	//Traceback(1,N-1,s);
    	}
    	return 0;
    }

    参考算法3:备忘录法优化(据说也存在错误?)

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #define SIZE 1000
    #define INF 999999999
    using namespace std;
    
    int memo[SIZE][SIZE];
    //m数组内存放矩阵链的行列信息
    //m[i-1]和m[i]分别为第i个矩阵的行和列(i = 1、2、3...)
    int Best_Memo(int m[], int left, int right)
    {
    	//只有一个矩阵时,返回计算次数0
    	if (left == right)
    	{
    		return 0;
    	}
     
    	double min = INF;
    	int i;
    	//括号依次加在第1、2、3...n-1个矩阵后面
    	for (i = left; i < right; i++)
    	{
    		//计算出这种完全加括号方式的计算次数
    		double count;
    		if (memo[left][i] == 0)
    		{
    			memo[left][i] = Best_Memo(m, left, i);
    		}
    		count = memo[left][i];
    		if (memo[i+1][right] == 0)
    		{
    			memo[i+1][right] = Best_Memo(m, i+1, right);
    		}
    		count += memo[i+1][right];
    		count += m[left-1] * m[i] * m[right];
    		//选出最小的
    		if (count < min)
    		{
    			min = count;
    		}
    	}
    	return min;
    }
     
    int main(void)
    {
    	int m[SIZE];
    	int n;
    	while (cin>>n)
    	{
    		int i;n++;int tempx,tempy,flag=1;
    		for(i=1;i<n;i++){
    			cin>>tempx>>tempy;
    			if(i==1){
    				m[0]=tempx;m[1]=tempy;
    			}else{
    				if(tempx!=m[i-1]) {
    					cout<<"invalid argument"<<endl;
    					flag=0;break;
    				}
    			}
    				m[i]=tempy;
    		}
    		if(flag==0) continue;
    		memset(memo, 0, sizeof(memo));
    		printf("%d\n", Best_Memo(m, 1, n-1));
    	}
    	return 0;
    }

    参考算法4:

    #include<iostream>
    #include<vector>
    using namespace std;
    int N;
    int matrixMultiple(int n, vector< vector<int> > &m, vector< vector<int> > &s, int p[]){
    
        for(int i = 1; i < n; i++){  
            //对角线设为0,没有自己和自己乘
            m[i][i] = 0;
        }
    
        for(int r = 2; r <= n; r++){ //r为规模
    
            for(int i = 1; i <= n-r+1; i++){  //i:首矩阵编号
    
                int j = i + r - 1;  //尾矩阵编号
                m[i][j] = m[i+1][j] + p[i-1]*p[i]*p[j];    //将链ij划分为A(i) *(A[i+1 : j])
                s[i][j] = i;
                
                for(int k = i + 1; k < j; k++){  //k:断开的位置
                    //将链ij划分为(A[i:k] + A[k+1 : j])
                    int temp = m[i][k] + m[k + 1][j] + p[i-1]*p[k]*p[j];
                    if(temp < m[i][j]){
                        m[i][j] = temp;
                        s[i][j] = k;
                    }
                }
            }
        }
        return m[1][N-1];
    }
    
    int main(){
    	int x;
    	while (cin>>x)
    		{
    			int i;N=x+1;int tempx,tempy,flag=1;
    			int p[N];
    			for(i=1;i<N;i++){
    				cin>>tempx>>tempy;
    				if(i==1){
    					p[0]=tempx;p[1]=tempy;
    				}else{
    					if(tempx!=p[i-1]) {
    						cout<<"invalid argument"<<endl;
    						flag=0;break;
    					}
    				}
    					p[i]=tempy;
    			}
    			if(flag==0) continue;
        vector< vector<int> > m(N, vector<int>(N));
        vector< vector<int> > s(N, vector<int>(N));
     
     	cout<<matrixMultiple(N-1,m,s,p)<<endl;
    	//cout<<"矩阵的最少计算次数为:"<<matrixMultiple(N-1,m,s,p)<<endl;
    	
    }
    return 0;
    }

    参考文章:

    算法之矩阵连乘问题_伊二的博客-CSDN博客_矩阵连乘算法

    矩阵连乘问题——算法笔记——详解_越前浩波的博客-CSDN博客_矩阵连乘问题

    0010算法笔记——【动态规划】矩阵连乘问题_风仲达的博客-CSDN博客_矩阵连乘问题的动态规划算法

    矩阵连乘(动态规划算法)_何智鹏的博客-CSDN博客_矩阵连乘动态规划

    展开全文
  • 如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。 要求:给定由n个矩阵构成的序列{A1,A2,…,An},对乘积A1A2…An,找到最小化乘法次数的加括号方法。 二.问题的解决方案/...
  • 动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。 与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相...
  • 动态规划矩阵连乘

    2022-03-25 20:26:21
    动态规划算法之矩阵连乘问题思路_额di个神的博客-CSDN博客_矩阵连乘问题 问题描述: 给定n个矩阵,相连的两个是可乘的。如何确定计算矩阵连乘的计算次序,使得该次序计算矩阵连乘积需要的数乘次数最少。 分析: ...
  • 动态规划基本思想和学习目的 动态规划算法与分治法类似,其基本思想也就是将待求解的问题分解成若干个子问题,先求解... 动态规划的适用场合,一般适用于解最优化问题,例如矩阵连乘问题、最长公共子序列、背包问题等
  • 动态规划方法解决矩阵连乘问题,即寻求多个矩阵连乘时的最好的加括号方式使得总的乘法两最小; 可以设定矩阵个数,手动输入矩阵的阶,显示动态规划算法的表格,即乘法量和括号信息; 多文档,C++6.0
  • 3.7 矩阵连乘(Matrix chain multiplication) 3.7.1 问题描述 求多个矩阵连乘的最优次序,使得所需的乘法次数最少,并求出所需的乘法次数。 3.7.2 算法思路 跟以往的动态规划解题思路相同,要求A1~A5的连乘,就先求...
  • 如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。将矩阵连乘积简记为A[i:j] ,这里i≤j, 考察计算A[i:j]的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开,i≤k&...
  • 差异点:与分治法不同的是,适合用动态规划法求解的问题经分解得到的子问题往往不是相互独立的。有些问题分解后的子问题往往是重复的,此时若用分支法则会重复计算耗费时间内存。 总结:为了达到避免重复计算,可以...
  • 通过动态规划算法减少矩阵连乘所需的乘法次数。
  • 主要介绍了Java矩阵连乘问题(动态规划)算法,结合实例形式分析了java实现矩阵连乘的算法原理与相关实现技巧,需要的朋友可以参考下
  • 给定n个矩阵{A1,A2,…,An},其中,Ai与Ai+1是可乘的,(i=1,2 ,…,n-1)。用加括号的方法表示矩阵连乘的次序,不同的计算次序计算量(乘法次数)是不同的,找出一种加括号的方法,使得矩阵连乘的次数最小。 ......
  • 动态规划求解矩阵连乘问题

    千次阅读 2019-04-27 15:05:46
    填坑填坑,动态规划第二篇,想写矩阵连乘问题。 问题描述: 这个问题描述有点复杂,放张图解释: 也就是选择最优的计算次序,以求乘法次数最少。 问题分析: 这里也可以采用自底向上的思路。每个子问题的最后...
  • 差异点:与分治法不同的是,适合用动态规划法求解的问题经分解得到的子问题往往不是相互独立的。有些问题分解后的子问题往往是重复的,此时若用分支法则会重复计算耗费时间内存。 总结:为了达到避免重复计算,可以...
  • 超详细的动态规划解决矩阵连乘

    千次阅读 多人点赞 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+...
  • 一、实验目的 1、理解动态规划的基本思想 ...考察这n个矩阵连乘积A1A2……An,找出计算量最小的计算次序。 三、算法描述 核心:找到A[i:j]的最优计算次序。 1.利用m[i][j]数组记录A[i:j]的最少计...
  • 算法设计与分析实验报告,附已通过源码,...1.问题描述 2.实验目的 3.实验原理 4.实验设计 (包括输入格式、算法、输出格式) 5.实验结果与分析 (除了截图外,实验结果还用图表进行了分析) 6.结论 7.程序源码
  • 动态规划C语言矩阵连乘Acm acm 采用动态规划来解题

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,420
精华内容 2,168
热门标签
关键字:

动态规划矩阵连乘问题