动态规划&矩阵连乘

动态规划&矩阵连乘

动态规划的概念

• 与分治方法类似

　　　　 分-治-合

•　　与分治方法不同

　　　　 子问题之间并非相互独立

• 基本思想

　　　　 用一个表记录所有子问题的解，不管子问题是否被用到，只要它被计算过，就将其结果备份至表中

动态规划的基本要素

• 最优子结构

　　　　利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。

• 重叠子问题

　　　　• 递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。

　　　　• 动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。

　　　　• 通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。

动态规划的步骤

• 找出最优解的性质

• 递归地定义最优值

• 以自底向上的方式计算出最优值

• 根据计算获得的最优值，构造最优解

矩阵连乘

• 问题

　　　　给定n个矩阵(A1,A2,…,An)，其中Ai和Ai+1是可乘的，求解这n个矩阵的连乘积A？

• 矩阵连乘积A=A1A2A3A4

• 计算次序

　　　　 (((A1A2)A3)A4))

　　　　 ((A1(A2A3))A4)

　　　　 (A1((A2A3)A4))

　　　　 (A1(A2(A3A4)))

　　　　 ((A1A2)(A3A4))

• 最优子结构性质

　　　　 原问题的最优解包含其子问题的最优解

　　　　 A[1:n]的最优计算次序所包含的计算矩阵子链A[1:k]和A[k+1:n]也是最优的

　　　　 数学归纳法可以证明

• 建立递归关系

　　　　令A[i:j]所需的最少数乘次数为m[i][j].

　　　　当i=j时，m[i][j]=0

　　　　当i<j时，m[i][j]=m[i][k]+m[k+1][j] +pi-1*pk*pj

　　　　 构造递归关系

　　　 将对应的m[i][j]的断开位置k记为s[i][j]，可递归的构造最优解

•　　 递归求解　　　　

 1 int matrixChainRecur(int i, int j){
 2     if (i == j) return 0;
 3     int u = matrixChainRecur(i, i) + matrixChainRecur(i+1, j) 
 4              + p[i-1] * p[i] * p[j];
 5     s[i][j] = i;
 6     for (int k = i + 1; k < j; k++) {
 7            int t = matrixChainRecur(i, k) + matrixChainRecur(k+1, j) 
 8                    + p[i-1] * p[k] * p[j];
 9      if (t < u){
10           u = t; 
11           s[i][j] = k;
12         }
13     }
14     return u;
15 }

• 在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。

• 用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法

• 计算最优值

A1	A2	A3	A4	A5	A6
30´35	35´15	15´5	5´10	10´20	20´25

 1 # include<stdio.h>
 2 # include<iostream>
 3 using namespace std;
 4 
 5 int m[20][20],s[20][20],n,p[20];
 6 void matrixChain()
 7 {
 8     int i,j,k,r;
 9     for(i=1; i<=n; i++)    m[i][i]=0;
10     for(r=2; r<=n; r++)                  //对角线
11         for( i=1; i<=n-r+1; i++)            //行
12         {
13             j = r+i-1;                               //列
14             m[i][j]=m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j];
15             s[i][j]=i;
16             for(k = i+1; k<j; k++)
17             {
18                 int temp=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
19                 if(temp<m[i][j])
20                 {
21                     m[i][j]=temp;
22                     s[i][j]=k;
23                 }
24             }
25         }
26 }
27 
29 void traceback(int i,int j)
30 {
31     if(i==j)return ;
32     traceback(i,s[i][j]);
33     traceback(s[i][j]+1,j);
34     cout<<"Multiply A"<<i<<","<<s[i][j]<<"and A"<<s[i][j]+1<<","<<j<<endl;
35 }
36 
38 int main()
39 {
40     cin>>n;
41     for(int i=0; i<=n; i++)
42         cin>>p[i];
43     //测试数据可以设为六个矩阵分别为
44     //A1[30*35],A2[35*15],A3[15*5],A4[5*10],A5[10*20],A6[20*25]
45     //则p[0-6]={30,35,15,5,10,20,25}
46     //输入：30 35 15 5 10 20 25
47     matrixChain();
48     traceback(1,n);
49     //最终解值为m[1][n];
50     cout<<m[1][n]<<endl;
51     return 0;
52 }