计算机算法贪心算法

《计算机算法贪心算法》由会员分享，可在线阅读，更多相关《计算机算法贪心算法（57页珍藏版）》请在金锄头文库上搜索。

1、第第5 5讲讲 动态规划动态规划1学习要点:理解动态规划算法的概念。掌握动态规划算法的基本要素（1）最优子结构性质（2）重叠子问题性质掌握设计动态规划算法的步骤。(1)找出最优解的性质，并刻划其结构特征。(2)递归地定义最优值。(3)以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息，构造最优解。2通过应用范例学习动态规划算法设计策略。（1）矩阵连乘问题；（2）最长公共子序列；（3）最大子段和（4）凸多边形最优三角剖分；（5）多边形游戏； （6）图像压缩；（7）电路布线；（8）流水作业调度；（9）背包问题；（10）最优二叉搜索树。3n动态规划算法与分治法类似，其基本思想也是将待求

2、解问题分解成若干个子问题算法总体思想算法总体思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=4n但是经分解得到的子问题往往不是互相独立的。不同子问题的 数目常常只有多项式量级。在用分治法求解时，有些子问题被 重复计算了许多次。算法总体思想算法总体思想nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) 5n如果能够保存已解决的子问题的答案，而在需要时再找出已求 得的答案，就可以避免大量重复计算，从而得到多

3、项式时间算 法。算法总体思想算法总体思想n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n)6动态规划基本步骤动态规划基本步骤n找出最优解的性质，并刻划其结构特征。n递归地定义最优值。n以自底向上的方式计算出最优值。n根据计算最优值时得到的信息，构造最优解 。7u完全加括号的矩阵连乘积可递归地定义为：u设有四个矩阵 ，它们的维数分别是：u总共有五中完全加括号的方式（1）单个矩阵是完全加括号的； （2）矩阵连乘积 是完全加括号的，则 可表示为2个完全加括号的矩阵连乘积 和 的乘积

4、并加括号，即 16000, 10500, 36000, 87500, 34500完全加括号的矩阵连乘积完全加括号的矩阵连乘积8矩阵连乘问题矩阵连乘问题n给定n个矩阵 ， 其中 与 是可乘的， 。考察这n个矩阵的连乘积 n由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不 同的计算次序。这种计算次序可以用加括号的方式来确定。n若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已 完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算 法计算出矩阵连乘积9矩阵连乘问题矩阵连乘问题给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1 ，2，n-1。如何确定计算矩阵连乘积的计算次序，

5、使得依此 次序计算矩阵连乘积需要的数乘次数最少。 u穷举法：列举出所有可能的计算次序，并计算出每一种计 算次序相应需要的数乘次数，从中找出一种数乘次数最少的 计算次序。 算法复杂度分析： 对于n个矩阵的连乘积，设其不同的计算次序为P(n)。 由于每种加括号方式都可以分解为两个子矩阵的加括号问题： (A1.Ak)(Ak+1An)可以得到关于P(n)的递推式如下：10矩阵连乘问题矩阵连乘问题u穷举法 u动态规划将矩阵连乘积 简记为Ai:j ，这里ij 考察计算Ai:j的最优计算次序。设这个计算次序在矩阵 Ak和Ak+1之间将矩阵链断开，ik 0) return mij;if (i = j) ret

6、urn 0;int u = LookupChain(i，i) + LookupChain(i+1，j) + pi-1*pi*pj;sij = i;for (int k = i+1; k =cij-1) cij=ci-1j; bij=2;else cij=cij-1; bij=3; 构造最长公共子序列 void LCS(int i，int j，char *x，int *b)if (i =0 | j=0) return;if (bij= 1) LCS(i-1，j-1，x，b); cout(j)。 电路布线问题要确定将哪些连线安排在第一层上，使得该层上 有尽可能多的连线。换句话说，该问题要求确定导线

7、集 Nets=(i,(i),1in的最大不相交子集。 33记 。N(i,j)的最大不相交子 集为MNS(i,j)。Size(i,j)=|MNS(i,j)|。 (1)当i=1时，(2)当i1时， 2.1 j1时34一、问题描述：多段图是一个有向无环图： 2）对于图上任意一条弧，总有：uVi, 而 vVi+1(i=1, 2, , k-1)。弧上加“权”。“权”也称为弧 的成本（cost), 记为w(u, v)。求：从s到t的一条最短路径。多段图问题多段图问题1）n个顶点分为K2个不相交集合Vi(i=1,2,k)。其中V1 和Vk都是只有一个顶点，分别称为源点s和汇点t。35234567891011

8、112st9732425653456811117212436二、多段图问题求解分析 2. 枚举法：O(2n)3. 多步决策：每次从一个顶点集中确定一个顶点，作为从s到t路径上的一个顶点三、最优性原理 1. 可以用单源点路径问题求解。时间复杂度：O(n2)( An optimal sequence of decisions has the property that whatever the initial state and decision are, the remaining decisions must constitute an optimal decision sequece wit

9、h regard to the state resulting from the first decision )过程的最优决策序列具有如下性质：无论过程的初始 状态和初始决策是什么，其余的决策都必须相对于初始决 策所产生的状态，构成一个最优决策序列。37四、动态规划法要点1. 论证：最优性原理对问题成立。2. 建立：从“小问题最优”到“大问题最优”的递推关系式 。3. 从小问题开始，实施上述递推关系式，求得大问题的 最优解。V2sWsm mcostmtcostslWslcostlnWsncostn38五、多段图问题的动态规划法求解1. “最优性原理”对多段图问题成立。2. 递推关系式向前递推

10、式：costj = min wj, m + costm 对于所有的 mV i+1其中：j Vi ， i = 1, 2, , k-1ViVi+1jcostj Wj, mmcostmt393. 用“向前递推式”求从s到t的最短路径234567891011112st9732425653456811117212440cost12 = 0 ( )cost11 = min0 + 5 = 5 (v12)cost10 = 2 (v12 ) ; cost9 = 4 (v12)cost8 = minw8, 10+cost10, w8, 11+cost11= 7 (v10)cost7 = 5 (v10) ; cos

11、t6 = 7 (v10)cost5 = 15 (v8) ; cost4 = 18 (v8)cost3 = 9 (v6) ; cost2 = 7 (v7)cost1 = 16 (v2 /v3 )从s到t的最短路径是：v1, v2, v7, v10, v12或者是：v1, v3, v6, v10, v1241流水作业调度流水作业调度n个作业1，2，n要在由2台机器M1和M2组成的流水线上 完成加工。每个作业加工的顺序都是先在M1上加工，然后在 M2上加工。M1和M2加工作业i所需的时间分别为ai和bi。 流水作业调度问题要求确定这n个作业的最优加工顺序，使得从 第一个作业在机器M1上开始加工，到最

12、后一个作业在机器M2上 加工完成所需的时间最少。分析： 直观上，一个最优调度应使机器M1没有空闲时间，且机器 M2的空闲时间最少。在一般情况下，机器M2上会有机器空闲 和作业积压2种情况。 设全部作业的集合为N=1，2，n。SN是N的作业子 集。在一般情况下，机器M1开始加工S中作业时，机器M2还 在加工其它作业，要等时间t后才可利用。将这种情况下完成 S中作业所需的最短时间记为T(S,t)。流水作业调度问题的最 优值为T(N,0)。42流水作业调度流水作业调度设是所给n个流水作业的一个最优调度，它所需的加工时间为 a(1)+T。其中T是在机器M2的等待时间为b(1)时，安排作业 (2)，(n

13、)所需的时间。 记S=N-(1)，则有T=T(S,b(1)。证明：事实上，由T的定义知TT(S,b(1)。若TT(S,b(1)， 设是作业集S在机器M2的等待时间为b(1)情况下的一个最优 调度。则(1)， (2)， (n)是N的一个调度，且该调度 所需的时间为a(1)+T(S,b(1)2n时，算法需要(n2n)计算时间。 48算法改进算法改进由m(i,j)的递归式容易证明，在一般情况下，对每一个确定的 i(1in)，函数m(i,j)是关于变量j的阶梯状单调不减函数。跳跃 点是这一类函数的描述特征。在一般情况下，函数m(i,j)由其全 部跳跃点唯一确定。如图所示。对每一个确定的i(1in)，用

14、一个表pi存储函数m(i，j)的全部 跳跃点。表pi可依计算m(i，j)的递归式递归地由表pi+1计算 ，初始时pn+1=(0，0)。 49一个例子一个例子 n=3，c=6，w=4，3，2，v=5，2，1。x(0,0)m(4,x)x(2,1)m(4,x-2)+1x(0,0)(2,1)m(3,x)(3,2) xm(3,x-3)+2(5,3)x(0,0)(2,1)m(2,x)(3,2)(5,3)xm(2,x-4)+5(4,5)(6,6)(7,7)(9,8)x(0, 0)(2, 1)m(1,x)(3,2)(5,3)(4,5)(6,6)(7,7)(9,8)x(0,0)(2,1)m(3,x)x(0,0)(2,1)m(2,x)(3,2)(5,3)50函数m(i,j)是由函数m(i+1,j)与函数m(i+1,j-wi)+vi作max运算得 到的。因此，函数m(i,j)的全部跳跃点包含于函数m(i+1，j)的跳 跃点集pi+1与函数m(i+1，j-wi)+vi的跳跃点集qi+1的并集中 。易知，(s,t)qi+1当且仅当wisc且(s-wi,t-vi)pi+1。因此 ，容易由pi+1确定跳跃点集qi+1如下 qi+1=pi+1(wi,vi)=(j+wi,m(i,