矩阵连乘

Posted on | In |

矩阵连乘问题描述

有n个矩阵连乘，如何找到最小的加括号方式以及最小的次数

疑问

A(35)A(57)A(7*2)的向乘次数和划分有关系吗？

(A(35)A(57))A(72) 相乘次数： (357)+(37)*2 = 147

A(35)(A(57)A(72)) 相乘次数： (572)+3(5*2) = 100

答案很明显是有关系的。

分析

求 A1A2A3…An

定义 AiAi+1…Ak…Aj-1Aj 子列， 可看成是Ai…Ak，Ak…Aj

确定k的位置，然后按照递归的思想来逐步解决

求得结果后，使i=1，j=n原问题即可求解。

建立递归关系（状态转移方程）

1
2
3
4
5
6
7
8
9
10
11
12
设
Ai…Aj相乘 的最小数乘次数存储于m[i][j]中。
S[i][j]存储最佳断开位置。
A1：P0*P1
A2：P1*P2
A3：P2*P3
…
Ai：Pi-1*Pi
Ai+1：Pi*Pi+1
…
An：Pn-1*Pn
P0*P1*P2…*Pn——n+1个

s[i][j]的确定方法：

对于Ai……Aj

k=i, (Ai)(…Aj)

k=i+1, (AiAi+1)(…Aj)

k=j-1, (AiAi+1…Aj-1)Aj

求出m[i][j]的最小k值，存入s[i][j]，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<iostream>
#define MAX 100
using namespace std;
int p[MAX];

int m[MAX][MAX],s[MAX][MAX];
void print(int i,int j){
	if(s[i][j]==0){
		cout<<i<<"";
		return;
	}
	cout<<"(";
	print(i,s[i][j]);
		
	print(s[i][j]+1,j);
	cout<<")";
}
int main(){
	
	int n;
	cin>>n;
	for(int i=0;i<n+1;i++)
	cin>>p[i]; 
	for(int i=0;i<n;i++){
		m[i][i]=0;
		s[i][i]=0;
	}
	
	for(int d=2;d<=n;d++){
		for(int i=1;i<=n+d-1;i++){
			int j=i+d-1;
			//直接从i i+1-->j 
			int min=m[i+1][j]+p[i-1]*p[i]*p[j];
			m[i][j]=i;
			s[i][j]=i;
			//枚举分割点 i-->k k-->j(i+1<=k<j)
			for(int k=i+1;k<j;k++){
				if(min>m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]){
					min=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
					s[i][j]=k;
				}	
			}
			m[i][j]=min;			
		}	
	}
		cout<<m[1][n]<<endl;
		print(1,n);
}

iamge
image
参考
https://www.jianshu.com/p/8f2e12d6e10b

动态规划思想：

将大问题划分为具有相同特征的小问题；
小问题之间往往相互联系；
从小问题一步步求解大问题。
适合求解最优解问题