动态规划解决矩阵连乘问题

动态规划的概念

与分治法相似,动态规划问题都是将问题分解为规模逐渐减小的同类型的子问题。

不同之处:

  • 分治法往往子问题之间相互独立,不包含公共子问题
  • 而动态规划分解得到的子问题很多都是重复的

所以应用动态规划的两个标识是:

  • 最优子结构,即最优化问题可以化为相应的最优化子问题
  • 重复子问题

动态规划问题的一般性解题步骤

  1. 找出最优解的性质,并刻画其最优解结构特征
  2. 递归地找出最优解(写出其动态规划方程)
  3. 计算出最优解的值,通常采用自底向上的方法
  4. 根据计算最优解时得到的信息,以递归的方式构造一个最优解

矩阵连乘问题(矩阵链乘法)

问题的描述

对于给定的n个矩阵,$M_1,M_2,\dots,M_n$,其中矩阵$M_i$ 和$M_j$是可乘的,要求确定计算矩阵连乘积($M_1 M_2 \dots M_n$)的计算次序,使得按照该次数计算矩阵连乘积时需要的乘法次数最少

示例如下:
矩阵连乘示例

问题分析

对于矩阵链的连乘问题,我们首先需要确定最优解的结构并从中推出递归动态规划方程,我们用$A_{i,j}$表示$A_i,A_{i+1},\dots,A_j$矩阵连乘的结果,对于最优化的最终结果,我们可以在最终连乘的上一步在$A_k$和$A_{k+1}$之间把矩阵链划开,则前缀$A_{i,k}$和后缀$A_{k+1,j}$是其子问题,同时也满足最优化问题,即是最优子结构。
我们令$m[i,j]$为计算矩阵链$A_{i,j}$乘法次数的最小值,矩阵$A_i$的大小为$p_{i-1}\times p_i$,可知$A_{i,k}$和$A_{k+1,j}$相乘的代价为$p_{i-1}p_k p_j$次标量乘法运算。则推导其递归求解方程为:

$$
m[i,j] =
\begin{cases}
0 & \text{如果 i = j} \\
\min_{i\leq k <j}\lbrace{m[i,k]+m[k+1,j]+p_{i-1}p_k p_j}\rbrace & \text{如果 i < j}
\end{cases}
$$

这时候我们就可以通过递归方程来计算出最优解的代价,这里我们可以采用自底向上的动态规划方法或改进的动态规划方法即备忘录法来计算所需的最小代价,最后一般通过递归的方式来构造最优解的处理,即矩阵链乘时括号化的步骤。

代码实现(Java)

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
package algorithms.dynamic_plan;
/**
* 动态规划法和备忘录法解决矩阵连乘问题
* @author jqy
*
*/
public class MatrixChain {
/*
* array[i][j]表示Ai...Aj相乘最少计算次数
* s[i][j]=k,表示Ai...Aj这(j-i+1)个矩阵中最优子结构为Ai...Ak和A(k+1)...Aj
* p[i]表示Ai的行数,p[i+1]表示Ai的列数
*/
private int array[][];
private int p[];
private int s[][];

public MatrixChain(){
p=new int[]{2,4,5,5,3};
array=new int[4][4];
s=new int[4][4];
}

public MatrixChain(int n,int []p){
this.p=new int[n+1];
this.array=new int[n][n];
this.s=new int[4][4];
for(int i=0;i<p.length;i++)
this.p[i]=p[i];
}
/*********************方法一,动态规划**********************************/
public void martixChain(){
int n=array.length;
for(int i=0;i<n;i++)
array[i][i]=0;
for(int r=2;r<=n;r++){
for(int i=0;i<=n-r;i++){
int j=i+r-1;
array[i][j]=array[i+1][j]+p[i]*p[i+1]*p[j+1];
s[i][j]=i;
for(int k=i+1;k<j;k++){
int t=array[i][k]+array[k+1][j]+p[i]*p[k+1]*p[j];
if(t<array[i][j]){
array[i][j]=t;
s[i][j]=k;
}
}
}
}
}
/*
* 如果待求矩阵为:Ap...Aq,then a=0,b=q-p
*/
public void traceBack(int a,int b){
if(a<b){
traceBack(a, s[a][b]);
traceBack(s[a][b]+1, b);
System.out.println("先把A"+a+"到A"+s[a][b]+"括起来,在把A"+(s[a][b]+1)+
"到A"+b+"括起来,然后把A"+a+"到A"+b+"括起来");
}
}

/*********************方法二:备忘录方法*****************************/
public int memorizedMatrixChain(){
int n=array.length;
for(int i=0;i<n;i++){
for(int j=i;j<n;j++)
array[i][j]=0;
}
return lookUpChain(0,n-1);
}

public int lookUpChain(int a,int b){
if(array[a][b]!=0)
return array[a][b];
if(a==b)
return 0;
array[a][b]=lookUpChain(a, a)+lookUpChain(a+1, b)+p[a]*p[a+1]*p[b+1];
s[a][b]=a;
for(int k=a+1;k<b;k++){
int t=lookUpChain(a, k)+lookUpChain(k+1, b)+p[a]*p[k+1]*p[b+1];
if(t<array[a][b]){
array[a][b]=t;
s[a][b]=k;
}
}
return array[a][b];
}
public static void main(String[] args) {
MatrixChain strassen=new MatrixChain();
//strassen.martixChain();
strassen.memorizedMatrixChain();
strassen.traceBack(0, 3);
}
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×