《{电子公司企业管理}计算机算法设计与分析王晓东2版第3章》由会员分享，可在线阅读，更多相关《{电子公司企业管理}计算机算法设计与分析王晓东2版第3章（89页珍藏版）》请在金锄头文库上搜索。
1、第3章 动态规划,1,上海金融学院信息管理系,学习要点: 理解动态规划算法的概念。 掌握动态规划算法的基本要素 （1）最优子结构性质 （2）重叠子问题性质 掌握设计动态规划算法的步骤。 (1)找出最优解的性质，并刻划其结构特征。 (2)递归地定义最优值。 (3)以自底向上的方式计算出最优值。 (4)根据计算最优值时得到的信息，构造最优解。,2,上海金融学院信息管理系,通过应用范例学习动态规划算法设计策略。 （1）矩阵连乘问题； （2）最长公共子序列； （3）最大子段和 （4）凸多边形最优三角剖分； （5）多边形游戏； （6）图像压缩； （7）电路布线； （8）流水作业调度； （9）背包问题；
2、（10）最优二叉搜索树。,3,上海金融学院信息管理系,动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题,算法总体思想,4,上海金融学院信息管理系,但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。,算法总体思想,5,上海金融学院信息管理系,如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。,算法总体思想,T(n),6,上海金融学院信息管理系,动态规划基本步骤,找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算
3、出最优值。 根据计算最优值时得到的信息，构造最优解。,7,上海金融学院信息管理系,（1）单个矩阵是完全加括号的； （2）矩阵连乘积 是完全加括号的，则 可 表示为2个完全加括号的矩阵连乘积 和 的乘积并加括号，即,16000, 10500, 36000, 87500, 34500,完全加括号的矩阵连乘积可递归地定义为： 设有四个矩阵 ，它们的维数分别是： 总共有五中完全加括号的方式,完全加括号的矩阵连乘积,8,上海金融学院信息管理系,3.1 矩阵连乘问题,给定n个矩阵 ， 其中 与 是可乘的， 。考察这n个矩阵的连乘积 由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计
4、算次序可以用加括号的方式来确定。 若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积,9,上海金融学院信息管理系,矩阵连乘问题,给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1，2，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。,穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。,算法复杂度分析： 对于n个矩阵的连乘积，设其不同的计算次序为P(n)。 由于每种加括号方式都可以分解为两个子矩阵的加括号问
5、题：(A1.Ak)(Ak+1An)可以得到关于P(n)的递推式如下：,10,上海金融学院信息管理系,矩阵连乘问题,穷举法 动态规划,将矩阵连乘积 简记为Ai:j ，这里ij,考察计算Ai:j的最优计算次序。设这个计算次序在矩阵 Ak和Ak+1之间将矩阵链断开，ikj，则其相应完全 加括号方式为,计算量：Ai:k的计算量加上Ak+1:j的计算量，再加上 Ai:k和Ak+1:j相乘的计算量,11,上海金融学院信息管理系,特征：计算Ai:j的最优次序所包含的计算矩阵子链 Ai:k和Ak+1:j的次序也是最优的。 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最
6、优子结构性质是该问题可用动态规划算法求解的显著特征。,分析最优解的结构,12,上海金融学院信息管理系,建立递归关系,设计算Ai:j，1ijn，所需要的最少数乘次数mi,j，则原问题的最优值为m1,n 当i=j时，Ai:j=Ai，因此，mi,i=0，i=1,2,n 当ij时， 可以递归地定义mi,j为：,这里 的维数为,的位置只有 种可能,13,上海金融学院信息管理系,计算最优值,对于1ijn不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有 由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。 用动态规划算法解此问题，可依据其
7、递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法,14,上海金融学院信息管理系,void MatrixChain(int *p，int n，int *m，int *s) for (int i = 1; i = n; i+) mii = 0; for (int r = 2; r = n; r+) for (int i = 1; i = n - r+1; i+) int j=i+r-1; mij = mi+1j+ pi-1*pi*pj; sij = i; for (int k
8、= i+1; k j; k+) int t = mik + mk+1j + pi-1*pk*pj; if (t mij) mij = t; sij = k; ,算法复杂度分析： 算法matrixChain的主要计算量取决于算法中对r，i和k的3重循环。循环体内的计算量为O(1)，而3重循环的总次数为O(n3)。因此算法的计算时间上界为O(n3)。算法所占用的空间显然为O(n2)。,15,上海金融学院信息管理系,用动态规划法求最优解,16,上海金融学院信息管理系,#include stdafx.h #include void MatrixChain(int* p,int n,int m7,int
9、 s7); void Traceback(int i,int j,int s7); int main(int argc, char* argv) int n=6; int m66; int s66; int p7; for (int i=0;ipi; MatrixChain(p,n,m,s); Traceback(1,n,s); return 0; ,17,上海金融学院信息管理系,void MatrixChain(int* p,int n,int m6,int s6) for (int i = 1; i = n; i+) mii = 0; for (int r = 2; r = n; r+)
10、for (int i = 1; i = n - r+1; i+) int j=i+r-1; mij = mi+1j+ pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = mik + mk+1j + pi-1*pk*pj; if (t mij) mij = t; sij = k; ,18,上海金融学院信息管理系,void Traceback(int i,int j,int s6) if(i=j)return; Traceback(i,sij,s); Traceback(sij+1,j,s); coutMultiply Ai,sij; c
11、outand Asij+1,jendl; ,19,上海金融学院信息管理系,#include stdafx.h #include void MatrixChain(int* p,int n,int m6,int s6); void Traceback(int i,int j,int s6); int main(int argc, char* argv) int n=6; int m66; int s66; int p7; for (int i=0;ipi; for (int ii=0;ii=n;ii+) coutpii ; coutendlendlendl; MatrixChain(p,n,m,
12、s); /coutnendl; Traceback(1,6,s); return 0; ,void MatrixChain(int* p,int n,int m6,int s6) for (int i = 1; i = n; i+) mii = 0; sii = 0; for (int r = 2; r = n; r+) for (int i = 1; i = n - r+1; i+) int j=i+r-1; mij = mi+1j+ pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = mik + mk+1j + pi-1*pk*p
13、j; if (t mij) mij = t; sij = k; for (int ii = 1; ii = n; ii+) for (int jj = ii; jj = n; jj+) cout.width(10); coutmiijj; coutendl; coutendlendl; for (int iii = 1; iii = n; iii+) for (int jjj = iii; jjj = n; jjj+) cout.width(10); coutsiiijjj; coutendl; coutendlendl; void Traceback(int i,int j,int s6)
14、if(i=j)return; Traceback(i,sij,s); Traceback(sij+1,j,s); coutMultiply Ai,sij; coutand Asij+1,jendl; ,20,上海金融学院信息管理系,3.2 动态规划算法的基本要素,一、最优子结构,矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。 在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。 利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优
15、解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。,同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）,21,上海金融学院信息管理系,动态规划算法的基本要素,二、重叠子问题,递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。 动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。 通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。,22,上海金融学院信息管理系,23,上海金融学院信息管理系,动态规划算法的基本要素,三、备忘录方法,备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。,24,上海金融学院信息管理系,int LookupChain(int i，int j) if (mij 0) return mij; if (i = j) retur
