第9章-动态规划与贪心策略.pptx

第九章 动态规划与贪心策略
动态规划思想
动态规划策略的应用
贪心策略的基本要
贪心策略的应用
动态规划策略通常用于求解具有某种最优性质的问题。贪心算法则是仅在当前状态下做出的最好选择，即局部最优选择；然后再求解做出该选择后所产生的相应子问题的解。
动态规划
适用于动态规划法求解的问题，经分解得到的子问题往往不是互相独立的；
基于动态规划法的算法设计通常按以下几个步骤进行：
(1) 找出最优解的性质，并描述其结构特征；
(2) 递归定义最优值；
(3) 以自底向上的方式计算最优值；
(4) 根据计算最优值时得到的信息构造一个最优解。
通常在步骤(3)计算最优值时，需要记录更多的信息，以便在步骤（4）中快速构造出一个最优解。
动态规划算法的两个基本要素——最优子结构性质和子问题重叠性质。
计算A[1:4]的递归树
(1) 最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。
(2) 重叠子问题：对每个子问题只解一次，然后将解保存在一个表格中，当再次需要解此问题时，只是简单地用常数时间查看所保存的结果即可。
动态规划算法的基本要素
是动态规划算法的一个变形。
备忘录方法的递归方式是自顶向下，动态规划算法则是自底向上。具体算法思想：
备忘录方法
每一个子问题建立一个记录项，初始化时将其赋值为特定值，表示该子问题尚未求解。
在求解过程中，对每个待求解的子问题首先查看其相应的记录项，若记录项中存储的值是初始化的值，则表示该子问题第一次遇到，就需要计算该子问题的解，并存入相应的记录项，否则表示该子问题已经求解，即不必再计算该子问题。
int MemorizedMatrixChain ( int n, int m[][n], int s[][n] ) {
for ( int i = 1; i <= n; i++)
for ( int j = 1; j <= n; j++) m[i][j] = 0;
return LookupChain (1, n );
}
int LookupChain ( int i, int j ) {
int u,t;
if ( m[i][j] > 0 ) return m[i][j];
if ( i == j ) return 0;
u=LookupChain(i, i)+LookupChain(i+1, j)+p[i-1]*p[i]*p[j];
s[i][j] = i;
for ( int k = i+1; k < j; k++) {
t=LookupChain(i, k)+LookupChain(k+1, j)+p[i-1]*p[k]*p[j];
if ( t < u ) {
u = t; s[i][j] = k;
}
}
m[i][j] = u;
return u;
}
备忘录算法
在调用LookupChain时，如果m[i][j]>0，那么m[i][j]中存储的值就是待求的值，直接返回此结果即可；否则通过递归算法自顶向下计算，并将计算结果存入m[i][j]后返回。
与动态规划算法一样，备忘录算法的复杂性是O(n3)。
当一个问题的所有子问题都至少需要求解一次时，则动态规划算法好于备忘录方法；当子问题空间中的部分子问题可以不必求解时，备忘录算法优于动态规划算法。
备忘录算法分析
矩阵连乘积的最优计算次序问题可用自顶向下的备忘录算法或自底向上的动态规划算法在O(n3)计算时间内求解。这两个算法都利用了子问题重叠性质。
问题：给定n个矩阵{A1, A2 , …, An}，其中Ai和Ai+1是可乘的，i = 1, 2, …,n-1，要求计算这n个矩阵的连乘积A1A2…An。
矩阵连乘问题
每一种完全加括号的方式对应于一种矩阵连乘积的计算次序，而这种计算次序与计算矩阵连乘积的计算量有着密切的关系。
解题思路：矩阵乘法满足结合律，如果矩阵连乘完全加了括号，则说明计算矩阵连乘的次序也完全确定。完全加括号的矩阵连乘积可以递归定义为：
(1) 单个矩阵是完全加括号的；
(2) 矩阵连乘积A是完全加括号的，则A可以表示为两个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC)。
若按第一种括号方式计算，则计算三个矩阵连乘积需要的数乘次数为：100*5*50+10*100*50=75,000。若按第二种括号方式计算，则计算三个矩阵连乘积需要的数乘次数为：10*100*5+10