计算机算法的动态规划课件(PPT 59页)

1、1第3章 动态规划第1页，共59页。2 学习要点:理解动态规划算法的概念。掌握动态规划算法的基本要素（1）最优子结构性质（2）重叠子问题性质掌握设计动态规划算法的步骤。(1)找出最优解的性质，并刻划其结构特征。(2)递归地定义最优值。(3)以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息，构造最优解。第2页，共59页。第三章.动态规划(Dynamic Programming)适用问题: 具备最优子结构性质和子问题重叠性的最优化问题.将问题的求解过程化为多步选择或决策的结果,在每一步决策上,列出各种可能的选择(各子问题的可行解),舍去那些肯定不能成为最优解的局部解.最后一步得到的解

2、必是最优解.问题的整体的最优解中包含着它的子问题的最优解3.1 基本思想用以求解最优化问题算法设计与分析 动态规划与贪心算法比较:都是将问题的求解过程化为多步决策.区别是:贪心法每采用一次贪心策略便做出唯一决策,求解过程只产生一个决策序列;求解过程为自顶向下,不一定得到最优解.动态规划的求解过程产生多个决策序列, 下一步的选择总是依赖上一步的结果.求解过程多为自底向上.总能得到最优解.第i+1步问题的求解中包含第i步子问题的最优解,形成递归求解.串形与树形优化系列第3页，共59页。算法设计与分析 动态规划1).分析最优解的结构.2).给出计算局部最优解值的递归关系.3).自底向上计算局部最优解

3、的值.4).根据最优解的值构造最优解.常见应用:0-1背包问题,图像压缩,最短路径,矩阵连乘,作业调度等等.算法的步骤注意0-1背包问题不能用贪心算法求解.优化子问题最终不取作用的优化子问题贪心算法动态规划算法第4页，共59页。5动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题算法总体思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=第5页，共59页。6但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。算法总体思想nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/

4、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)第6页，共59页。7如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。算法总体思想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)第7页，共59页。8（1）单个矩阵是完全加括号的；（2）矩阵连乘积 是完全加括号的，则 可 表示为2个完全加括号的矩阵连乘积 和

5、的乘积并加括号，即 16000, 10500, 36000, 87500, 34500完全加括号的矩阵连乘积可递归地定义为：设有四个矩阵 ，它们的维数分别是：总共有五中完全加括号的方式完全加括号的矩阵连乘积第8页，共59页。9矩阵连乘问题给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1，2，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。 算法复杂度分析：对于n个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可

6、以分解为两个子矩阵的加括号问题：(A1.Ak)(Ak+1An)可以得到关于P(n)的递推式如下：第9页，共59页。10矩阵连乘问题穷举法动态规划将矩阵连乘积 简记为Ai:j ，这里ij 考察计算Ai:j的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，ikj，则其相应完全加括号方式为计算量：Ai:k的计算量加上Ak+1:j的计算量，再加上Ai:k和Ak+1:j相乘的计算量第10页，共59页。11特征：计算Ai:j的最优次序所包含的计算矩阵子链 Ai:k和Ak+1:j的次序也是最优的。矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结

7、构性质是该问题可用动态规划算法求解的显著特征。分析最优解的结构第11页，共59页。12建立递归关系设计算Ai:j，1ijn，所需要的最少数乘次数mi,j，则原问题的最优值为m1,n 当i=j时，Ai:j=Ai，因此，mi,i=0，i=1,2,n当ij时，可以递归地定义mi,j为：这里 的维数为 的位置只有 种可能第12页，共59页。13计算最优值对于1ijn不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算

8、过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法第13页，共59页。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+) /r子链长度 for (int i= 1; i= n-r+l; i+) /i子链开始位置 int j= i+r-1; /j子链结束位置 mij = mi+1j + pi-1 * pi* pj; /初始化 sij = i; /初始

9、化 for(int k = i+1; k j;k+) /循环搜索 int t = mik + mk+1j + pi- 1 * pk * pj; if ( t 动态规划 矩阵乘法链矩阵乘法链动态规划算法第14页，共59页。算法设计与分析 动态规划 矩阵乘法链s25=3第15页，共59页。16动态规划算法的基本要素一、最优子结构矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。 利用问题的最优子结

10、构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）第16页，共59页。17动态规划算法的基本要素二、重叠子问题递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。 通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得

11、较高的解题效率。 第17页，共59页。18动态规划算法的基本要素三、备忘录方法备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。int LookupChain(int i，int j) if (mij 0) return mij; if (i = j) return 0; int u = LookupChain(i，i) + LookupChain(i+1，j) + pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = LookupChain(i

12、，k) + LookupChain(k+1，j) + pi-1*pk*pj; if (t u) u = t; sij = k; mij = u; return u;第18页，共59页。19最长公共子序列若给定序列X=x1,x2,xm，则另一序列Z=z1,z2,zk，是X的子序列是指存在一个严格递增下标序列i1,i2,ik使得对于所有j=1,2,k有：zj=xij。例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相应的递增下标序列为2，3，5，7。给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。给定2个序列X=x1,x2,x

13、m和Y=y1,y2,yn，找出X和Y的最长公共子序列。 第19页，共59页。20最长公共子序列的结构设序列X=x1,x2,xm和Y=y1,y2,yn的最长公共子序列为Z=z1,z2,zk ，则(1)若xm=yn，则zk=xm=yn，且zk-1是xm-1和yn-1的最长公共子序列。(2)若xmyn且zkxm，则Z是xm-1和Y的最长公共子序列。(3)若xmyn且zkyn，则Z是X和yn-1的最长公共子序列。由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。 第20页，共59页。21子问题的递归结构由最长公共子序列问题的最优子结构

14、性质建立子问题最优值的递归关系。用cij记录序列和的最长公共子序列的长度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时Cij=0。其它情况下，由最优子结构性质可建立递归关系如下：第21页，共59页。22计算最优值由于在所考虑的子问题空间中，总共有(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。 void LCSLength(int m，int n，char *x，char *y，int *c，int *b) int i，j; for (i = 1; i = m; i+) ci0 = 0;

15、 for (i = 1; i = n; i+) c0i = 0; for (i = 1; i = m; i+) for (j = 1; j =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); coutxi; else if (bij= 2) LCS(i-1，j，x，b); else LCS(i，j-1，x，b);第22页，共59页。23算法的改进在算法

16、lcsLength和lcs中，可进一步将数组b省去。事实上，数组元素cij的值仅由ci-1j-1，ci-1j和cij-1这3个数组元素的值所确定。对于给定的数组元素cij，可以不借助于数组b而仅借助于c本身在时间内确定cij的值是由ci-1j-1，ci-1j和cij-1中哪一个值所确定的。如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。事实上，在计算cij时，只用到数组c的第i行和第i-1行。因此，用2行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至O(min(m,n)。第23页，共59页。24凸多边形最优三角剖分用多边形顶点的逆时针序列表示凸多边形

17、，即P=v0,v1,vn-1表示具有n条边的凸多边形。若vi与vj是多边形上不相邻的2个顶点，则线段vivj称为多边形的一条弦。弦将多边形分割成2个多边形vi,vi+1,vj和vj,vj+1,vi。多边形的三角剖分是将多边形分割成互不相交的三角形的弦的集合T。给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分，使得即该三角剖分中诸三角形上权之和为最小。 第24页，共59页。25三角剖分的结构及其相关问题一个表达式的完全加括号方式相应于一棵完全二叉树，称为表达式的语法树。例如，完全加括号的矩阵连乘积(A1(A2A3)(A4(A5A6)所相应的语法树如

18、图 (a)所示。凸多边形v0,v1,vn-1的三角剖分也可以用语法树表示。例如，图 (b)中凸多边形的三角剖分可用图 (a)所示的语法树表示。 矩阵连乘积中的每个矩阵Ai对应于凸(n+1)边形中的一条边vi-1vi。三角剖分中的一条弦vivj，ij，对应于矩阵连乘积Ai+1:j。第25页，共59页。26最优子结构性质凸多边形的最优三角剖分问题有最优子结构性质。事实上，若凸(n+1)边形P=v0,v1,vn的最优三角剖分T包含三角形v0vkvn，1kn-1，则T的权为3个部分权的和：三角形v0vkvn的权，子多边形v0,v1,vk和vk,vk+1,vn的权之和。可以断言，由T所确定的这2个子多边

19、形的三角剖分也是最优的。因为若有v0,v1,vk或vk,vk+1,vn的更小权的三角剖分将导致T不是最优三角剖分的矛盾。 第26页，共59页。27最优三角剖分的递归结构定义tij，1i动态规划问题陈述:数字化图像是nn的像素阵列. 假定每个像素有一个0255的灰度值, 因此存储一个像素至多需8位. 为了减少存储空间, 采用变长模式, 即不同像素用不同位数来存储, 步骤如下. 1) 图像线性化:将n n维图像转换为1 n2向量 p1,p2,.pn23.7 图像压缩 2) 分段: 将像素分成连续的m段s1,s2,.sm,使每段中的像素存储位数 相同. 每个段是相邻像素的集合且每段最多含256个像素

20、, 若相同 位数的像素超过 256个的话, 则用两个以上段表示。3) 创建三个表 l: li存放第i段长度, 表中各项均为8位长 B: bi存放第i段中像素的存储位数,表中各项均为3位长. P: p1,.p n2以变长格式存储的像素的二进制串。 设产生了m个段,则存储第i段像素所需要的空间为:li*bi+11 总存储空间为 11m+ li*bi ； 问题要求找到一个最优分段。使存储空间最少小灰度象素用短位数记录第30页，共59页。算法设计与分析 动态规划libili+1bi+18位3位bi+1位li+1个单元4311010101010101000111721100100101000110110

21、11011第31页，共59页。例 题算法设计与分析 动态规划分段: 10, 9, 12, 40, 50, 35, 15, 12, 8, 10, 9, 15, 11, 130, 160, 240 L=2，2， 6，2；B=3，5，3，7；/为了用3位能存8,少算一个.计算时加1 P包含16个灰度值，其中头三个各用4位存储，接下来三个各用6位再接下来的七个各用4位，最后三个各用8位存储。 1010 1001 1100 111000 110010 100011 .三个表需要存储空间分别为: L:32位 B:12位 P:82位 例: 考察44图像灰 度 值 10 9 12 40 50 35 15 12

22、 8 10 9 15 11 130 160 240像素位数 4 4 4 6 6 6 4 4 4 4 4 4 4 8 8 8 10912401215355081091524016013011共需126位。将段1,2合并，则l=5, 6, 2 ; b=5, 3, 7 ; 合并后P的第一段为001010 001001 001100 111000 110010 100011其余不变.三个表需要存储空间分别为: L:24位 B:9位 P:88位 (共121位。)12+18+28+24第32页，共59页。例 题算法设计与分析 动态规划si= si-k+ k*bmax(i-k+1,i) +111)最优解结构

23、 :设n个像素的最优分段是C, 若在C中,第n像素与 n-1,n-2,.n-k+1像素为一段, 则像素1, 2,.n-k的分段也必是最优的. 最优分段C所需要的空间消耗为: =像素1, 2,.n-k的最优分段空间+k*bmax(n-k+1,n)+11 其中 bmax(a, b)=max ba,., bb 算法思路: 化为多步决策, 先求有一个像素时的最优分段,再求有2个像素时的最优分段,有3个像素时的最优分段.3)构造最优解:记ki为si取得最小值时k的值, 可由k的值构造相应 的最优解.2) 递推关系:令si为前i个像素最优分段的存储位数,则第33页，共59页。算法设计与分析 动态规划#de

24、fine HEADER=11void Compress(int p, int s, int l, int b) int n=p.length-1; s0=0; for(int i=1; i=n; i+) bi=length(pi); int bmax=bi; si=si-1+bmax; li=1; for(int j=2; j=i & j=256; j+) if(bmaxsi-j+j*bmax) si=si-j+j*bmax; li=j; si+=HEADER; ij最后一段:ln,bn倒数第二段:ln-ln,bn-ln计算复杂性 O(n)/固定循环长度第34页，共59页。算法设计与分析 动态

25、规划 38 电路布线 问题陈述:在一块电路板的上、下两端分别有n个接线柱, 要求用导线(i, (i)将上端接线柱i与下端接线柱(i)相连. 对于任何1i(j)在制作电路板时，要求将这n条连线分布到若干个绝缘层上。在同一层上的连线不相交.电路布线问题就是要确定将哪些连线安排在第一层(优先层)上, 使得该层上有尽可能多的连线。即确定导线集Nets=(i, (i), 1in 的最大不相交子集MNS.上图中 MNS=(3, 4), (5, 5), (7, 9), (9, 10) 第35页，共59页。算法设计与分析 动态规划1)最优解结构: 设nets(i, j) =(t, (t) | t i; (t)

26、 j nets, MNS(i, j)为nets(i, j)的最大不相交子集, 则所求即为MNS(n,n), 且 MNS(i, j) MNS(n,n).算法思路: 化为多步决策,自底向上,先求出只有一条连线的最大不相交子集,再求有2条连线的最大不相交子集. 例如MNS(7, 6) = (3, 4) ,(5, 5) , Size (7, 6) =2 MNS(10, 10)=MNS= (3, 4), (5, 5), (7, 9), (9, 10) nets(7, 6)= (3, 4), (4, 2), (5, 5), (6, 1) 第36页，共59页。算法设计与分析 动态规划 当i=1时, nets

27、(1, j)=(1, (1), MNS(1, j) = (1,(1) j (1) j l时, 若j(i), 则有(i, (i) MNS(i, j),此时MNS(i, j)=MNS(i-1, j), Size(i, j)=Size(i-1, j);(i)jSize(i,j)=Size(i-1,j)ii-1第37页，共59页。 若j(i),则(i,(i)可在也可不在MNS(i, j)中: 若(i, (i) MNS(i, j), 则对任意(t, (t)MNS(i, j), 有t动态规划Size(i, j)=01j (1)Size(i, j)=Size(i-1, j)max Size(i-1, j),

28、 Size(i-1, (i)-1)+1j (i) (2)当il时(1)当i=1时 当i=1时, nets(1, j)=(1, (1), MNS(1, j) = (1,(1) j (1) j l时 1)若j(i), 则有(i, (i) MNS(i, j), 此时MNS(i, j)=MNS(i-1, j), Size(i, j)=Size(i-1, j); 2)若j(i),则(i,(i)可在也可不在MNS(i, j)中: 若(i,(i) MNS(i, j), 对(t, (t)MNS(i, j) 有t i; (t) (i) 此时MNS(i, j)=MNS(i-1, j-1)(i,(i), Size(

29、i, j)= Size(i-1,(i)-1)+1; 若(i, (i) MNS(i, j), 则对任意(t, (t)MNS(i, j), 有t动态规划void MNS(int C，int n，int *size)/初始化size1*for(int j=0；jCl；j+) sizel j=0；for(j=C1；j=n ; j+) size1j=1；/计算sizei*，1infor(int i=2；in；i+) for(int j=0；jCi；j+) sizeij=sizei-1j； for(j=Ci；i1；i-) /i号net在MNS中? if (sizeij!=sizei-1j /在MNS中 N

30、etm+=i； j=Ci-1；/Ci已使用 /1号网组在MNS中? if (j=C1) Netm+=1；/在MNS中算法复杂性:(n2)求最大无交叉子集算法第41页，共59页。算法设计与分析 动态规划9-107-95-53-4MNS包含4条边,按i, j 的倒序搜索,在数字增加处即是边号.第42页，共59页。43流水作业调度n个作业1，2，n要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi。流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在

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

32、(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)a(1)+T。这与是N的最优调度矛盾。故TT(S,b(1)。从而T=T(S,b(1)。这就证明了流水作业调度问题具有最优子结构的性质。由流水作业调度问题的最优子结构性质可知，第44页，共59页。45Johnson不等式对递归式的深入分析表明，算法可进一步得到简化。设是作业集S在机器M2的等待时间为t时的任一最优调度。若(1)=i, (2)=j。则由动态规划递归式可得:T(S,t)=ai+T(S-i,bi+maxt-ai,0)=ai+aj+T(S-i,j,tij)其中，如果作业i和j满足minbi,ajminbj,ai，则称作业i和j满足Johnson不等式。第45页，共59页。46流水作业调度的Johnson法则交换作业i和作业j的加工顺序，得到作业集S的另一调度，它所需的加工时间为T(