第3章 动态规划1.ppt

1、1,第3章 动态规划,2,学习要点: 理解动态规划算法的概念 掌握动态规划算法的基本要素 （1）最优子结构性质 （2）重叠子问题性质 掌握设计动态规划算法的步骤 (1)找出最优解的性质，并刻划其结构特征。 (2)递归地定义最优值 (3)以自底向上的方式计算出最优值 (4)根据计算最优值时得到的信息，构造最优解。,3,动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。,20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时

2、，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法动态规划。,1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作，标志着运筹学的一个新分支的创立。,4,生活中的实例,( 1) 汽车加油问题: 设有路程长度为L 公里的公路上，分布着m 个加油站，它们的位置分别为p( i = 1，2，m) ，而汽车油箱加满油后( 油箱最多可以加油k 升) ，可以行驶n 公里。设计一个方案，使汽车经过此公路的加油次数尽量少( 汽车出发时是加满油的) 。,5,( 2) 田忌与齐

3、王赛马各有n 匹马参赛( n100) ，每场比赛赌注为1 两黄金，现已知齐王与田忌的每匹马的速度，并且齐王肯定是按马的速度从快到慢出场，现要你写一个程序帮助田忌计算他最好的结果是赢多少两黄金( 输用负数表示) 。,6,( 3)有一个游戏室里有多个游戏室，并且这每个游戏室里还有多个游戏室，每个游戏室里面还有游戏室，依此类推。进入每个游戏室都可得到一定的快乐，每个游戏室的门票价格都大于0，都有一个快乐值，并且只有进入了一个游戏室，才可以进入它内部的游戏室，小明现在有n 元钱，问最大能得到多少的快乐。,7,通过应用范例学习动态规划算法设计策略 （1）矩阵连乘问题； （2）最长公共子序列； （3）最大

4、子段和 （4）凸多边形最优三角剖分； （5）多边形游戏； （6）图像压缩； （7）电路布线； （8）流水作业调度； （9）背包问题； （10）最优二叉搜索树。,8,动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题,算法总体思想,9,但是,分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。 在用分治法求解时，有些子问题被重复计算了许多次。,10,如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。,动态规划算法的总体思想,11,时间复杂度是O(p(n)的算法称为多项式时间算法，p(n)是关于n

5、的多项式。不能够这样限制时间复杂度的算法被称为指数时间算法。 例如：时间复杂度为O(nlog(n)、O(n3)的算法都是多项式时间算法，时间复杂度为O(nlog(n)、O(n!)、O(2n)的算法是指数时间算法。,12,动态规划基本步骤,找出最优解的性质，并刻画其结构特征。 递归地定义最优值。 以自底向上的方式计算最优值。 根据计算最优值时得到的信息，构造最优解。 13基本步骤。 动态规划算法常用于求解具有某种最优性质的问题. 可能有许多可行解, 希望找到具有最优值的那个解.,13,3.1 矩阵连乘问题,给定n个矩阵 ， 其中 与 是可乘的， 。考察这n个矩阵的连乘积 由于矩阵乘法满足结合律，

6、所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。 若一个矩阵连乘积的计算次序完全确定，即连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算矩阵连乘积.,14,（1）单个矩阵是完全加括号的； （2）矩阵连乘积A是完全加括号的，则A可 表示为2个完全加括号的矩阵连乘积B 和C 的乘积并加括号，即A=(BC),数乘次数:16000, 10500, 36000, 87500, 34500,完全加括号的矩阵连乘积,完全加括号的矩阵连乘递归定义:,15,3.1 矩阵连乘问题,给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1，2，n-1。如

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

8、算量：Ai:k的计算量加上Ak+1:j的计算量，再加上 Ai:k和Ak+1:j相乘的计算量. 动态规划法解矩阵连乘积最优计算次序问题的步骤如下:,17,动态规划算法的第一步:刻画问题的最优解结构特征. 特征：计算Ai:j的最优次序所包含的计算矩阵子链 Ai:k和Ak+1:j的次序也是最优的。 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。 问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。,步骤一: 分析最优解的结构,18,步骤二: 建立递归关系 定义最优值,设计算Ai:j所需要的最少数乘次数为mi,j， 1ijn，则原问题的最优值为m1,n 当i=

9、j时，Ai:j=Ai，因此，mi,i=0，i=1,2,n 当ij时， 可以递归地定义mi,j为：,这里 的维数为,的位置只有 种可能,注意: (1) mi,j给出了最优值,同时确定了最优次序中的断开位置k: mi,j=mi,k+mk+1,j+pi-1pkpj (2) 若将对应于mi,j的断开位置k记为si,j, 在计算最优值mi,j后, 可由si,j构造出相应的最优解.,19,步骤三: 计算最优值,对于1ijn不同的有序对(i,j), 对应于不同的子问题。因此，不同子问题的个数最多只有 由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。 用动态规

10、划算法解此问题，可依据其递归式以自底向上的方式进行计算。 保存已解决子问题答案,每个子问题只计算一次，而在后面需要时只要简单查一下. 避免重复计算，得到多项式时间的算法.,n个不同数中取2个的组合(i,j), ij,i=j时(i,j)的个数,20,算法与举例,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-

11、1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = mik + mk+1j + pi-1*pk*pj; if (t 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，k) + LookupChain(k+1，j) + pi-1*pk*pj; if (t u) u = t; sij = k

12、; mij = u; return u; ,27,动态规划算法的基本要素,最优子结构：问题的最优解是由其子问题的最优解所构成的。 重叠子问题：子问题之间并非相互独立的，而是彼此有重叠的。,最优子结构性质使我们能够以自底向上的方式递归地从子结构的最优解构造出问题的最优解。,因为子问题重叠，所以存在着重复计算。这样就可以用填表保存子问题解的方法来提高效率。,28,备忘录项,29,动态规划算法的基本方法,动态规划算法通常可以按以下几个步骤进行： (1)找出最优解的性质，并刻画其结构特征； (2)递归地定义最优值； (3)以自底向上的方式计算出各子结构的最优值并添入表格中保存； (4)根据计算最优值时

13、得到的信息，构造最优解。 步骤13是动态规划算法的基本步骤。 若需要最优解，则必须执行第4步，为此还需要在第3步中记录构造最优解所必需的信息。,30,3.3 最长公共子序列,若给定序列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。,31,给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。,最长公共子序列：例如，序列X=A，B，C，B

14、，D，A，B，Y=B，D，C，A，B，A的子序列，B，C，A是X与Y的公共子序列，但不是最长公共子序列；B，C，B，A也是X与Y的公共子序列，但它是X与Y的最长公共子序列，因为X与Y没有长度大于4的公共子序列。,32,求解的问题： 给定2个序列: X=x1,x2,xm和 Y=y1,y2,yn， 找出X和Y的最长公共子序列。,33,一、 最长公共子序列结构,设序列Xm=x1,x2,xm和Yn=y1,y2,yn的最长公共子序列为Zk=z1,z2,zk ，则 (1)若xm=yn，则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序列。 Xi=x1,x2,xi；Yj=y1,y2,yj,(2

15、)若xmyn且zkxm，则Z是Xm-1和Yn的最长公共子序列。,(3)若xmyn且zkyn，则Z是Xm和Yn-1的最长公共 子序列。证明见P57（二版P49）,2个序列的最长公共子序列包含了它们前缀的最长公共子序列。 最长公共子序列问题具有最优子结构性质,34,二、子问题的递归结构,由最优子结构性质建立子问题最优值的递归关系 用cij记录序列Xi和Yj的最长公共子序列的长度，其中， Xi=x1,x2,xi；Yj=y1,y2,yj。 当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故Cij=0。 其他情况下，由最优子结构性质可建立递归关系如下：,35,三、计算最优值,子问题空间中，共有(

16、mn)个不同的子问题. 因此，用动态规划算法自底向上地计算最优值能提高算法的效率。,void LCSLength(int m，int n，char *x，char *y，int *c，int *b) int i，j; for (i = 0; i =cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; outcmnendl; ,36,37,四、构造最长公共子序列,LCSLength只是计算出最优值，并未给出最优解，然而数组b可用于快速构造两个序列的最长公共子序列： bij=1时表示Xi和Yj的最长公共子序列是由Xi-1和Yj-1的最长公共子序列加上xi所

17、得到； bij=2时表示Xi和Yj的最长公共子序列与Xi-1和Yj的最长公共子序列相同； bij=3时表示Xi和Yj的最长公共子序列与Xi和Yj-1的最长公共子序列相同。 根据b的内容打印出最长公共子序列,38,构造最长公共子序列 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); coutT(S, b(1)，设是作业集S在机器M2的等待时间为b(1)情况下的一个最优调度, 则(1)， (2)， (n)是N的一个调度，且该调度所需的时间为a(1)+T(S,b(1)a

18、(1)+T。这与是N的最优调度矛盾。故TT(S,b(1)。从而T=T(S, b(1)。 这就证明了流水作业调度问题具有最优子结构的性质。,46,3.9.2 递归计算最优值,由流水作业调度问题的最优子结构性质可知:,一般情况下：,因M1完成作业i后，要完成作业i, 在M2上还需时间：,47,t,ai,bi,t- ai,48,3.9.3 流水作业调度的Johnson法则(1),设是作业集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) 其中：,如

19、果作业i和j满足minbi, ajminbj, ai，则称作业i和j满足Johnson不等式。,49,3.9.3 流水作业调度的Johnson法则(2),交换作业i和j的加工顺序，得到作业集S的另一调度，它所需的加工时间为: T(S, t)=ai+aj+T(S-i, j,tji) 其中: 当作业i和j满足Johnson不等式minbi, ajminbj,ai时，有,50,因此, tijtji, 故T(S, t) T(S, t). 由此可见:当作业i和j不满足Johnson不等式时，交换它们的加工顺序后，满足Johnson不等式, 且不增加加工时间。 对于流水作业调度问题，必存在最优调度 ，使得

20、作业(i)和(i+1)满足Johnson不等式, 此时称为满足Johnson法则的调度。 可证：调度满足Johnson法则iff对任意i2n，则算法的复杂性为(n2n)。 算法要求物品的重量wi是整数，而不能为实数。,61,0-1背包问题的阶跃性,函数m(i, j)是关于变量j的阶梯状单调不减函数： 由0-1背包问题的递归式,m(i, j) =,maxm(i+1, j), m(i+1, jwi)+vi jwi m(i+1, j) 0jwi,可知每当j增大超过一个物品的重量wi时，函数m(i, j)便有可能增加vi，因而形成了关于变量j的阶梯状单调不减函数。,对于j为连续，wi为实数时，m(i,

21、 j)依然是梯状单调不减函数。,62,阶跃函数m(i, j)的跳跃点,实际上在m(i, j)的计算中并不需要将j逐渐加1。因为m(i, j)有阶跃性，而阶梯的长度至少为某个wi，即当j增加了某个wi， m(i, j)值才会增加相应vi。这样的点称为函数m(i, j)的跳跃点。,m(i, j),j,0,xi,c,wi,vi,63,跳跃点决定了函数m(i, j),在m(i, j)的计算中，只需要计算它的跳跃点. 在变量j是连续的情况下，可以对每个确定的i (1in)，用一个表Pi来保存m(i, j)的全部跳跃点。 对于每一个确定的实数j，可以通过查表Pi来确定m(i, j)的值。 由于m(i, j

22、)是单调不减的阶梯函数，所以Pi中的全部跳跃点的值也是递增排列的。,64,跳跃点的递推关系,表Pi 可根据m(i, j)的递归式计算： 初始时，令Pn+1为(0, 0)。 由递归式,m(i, j) =,maxm(i+1, j), m(i+1, jwi)+vi jwi m(i+1, j) 0jwi,可知，m(i, j) 的跳跃点集包含于m(i+1,j)的跳跃点集与m(i+1, jwi)+vi 的跳跃点集的并集中.,若(a, b)是Pi+1中的跳跃点且a+wic，则(a+wi, b+vi)可能是Pi中的跳跃点。,65,受控跳跃点,前面产生的跳跃点中有些可能并不是真正的跳跃点，而是所谓的受控跳跃点。

23、 设(a, b)和(d, e)都是Pi中的跳跃点，若ad且eb，其情形如下图所示：,m(i, j),j,a,b,d,e,显然(d, e)不是真正的跳跃点。,(d, e)实际上受控于(a, b)，被称为受控跳跃点。,因此，将前面产生的跳跃点中的受控跳跃点删除，便可得到Pi中的跳跃点。,由此便可得到计算表Pi的算法。,66,跳跃点的计算,初始化：Pn+1 = (0, 0)； 若已知Pi+1，则有 Pi= Delete-controled(Pi+1(Pi+1(wi, vi) 其中： Pi+1(wi, vi) = (a+wi, b+vi) | (a, b)Pi+1 Delete-controled(S

24、)为删去S中的受控跳跃点。,67,计算跳跃点的算法,数组P 和Q 分别存放表Pi+1和表Pi。 初始化：P和Q的首行都为0，末行号为1。 从xn开始至x1，对每个物品xi，逐个执行： 从P的首行到最末行，对每行j逐行执行： w = Pj0 + wi； v = Pj1 + vi； 将Pj0和Pj1放入Q中； 若wc，则将w和v放入Q中。 将Q拷贝到P，并修改Q和P末行号。,68,pi=pi+1qi+1,qi+1=pi+1(wi ,vi ),删除受控点,69,跳跃点放入Q中,跳跃点(w, v)放入Q中时删去受控跳跃点： 从Q中的最后行往前对每行j进行： 若Qj0w且Qj1v，则返回；,此时跳跃点(

25、w, v)是受控的。,若Qj0w且Qj1v，则将(w, v)插入Q中第j行的后面，然后返回；,(w, v)的插入可能会引起Q中j行之后的行向后移动，并要修改Q的末行号。,若Qj0w且Qj1v，则 Qj0=w； Qj1 = v；,此时Qj0和Qj1是受控的。,若Qj0w且Qj1v，则行号j减一。,70,一个0-1背包问题的实例,n = 5, c = 10, w =2, 2, 6, 5, 4, v = 6, 3, 5, 4, 6,初始时：,P,Q,n = 5： (w5, v5) = (4, 6),w = P00 + 4 = 4 v = P01 + 6 = 6,将(0, 0)放入Q中，因是受控点被删

26、去。,将(4, 6)放入Q中，插在了(0, 0)之后。,将Q拷贝到P。 结束了P5的计算。,n = 4： (w4, v4) = (5, 4),w = P00 + 5 = 5 v = P01 + 4 = 4,将(0, 0)放入Q中，因是受控点被删去。,将(5, 4)放入Q中，插在了(0, 0)之后。,w = P10 + 5 = 9 v = P11 + 4 = 10,将(4, 6)放入Q中，删去受控点(5, 4)并取代了它的位置。,将(9, 10)放入Q中，放在(4, 6)之后。,将Q拷贝到P。 结束了P4的计算。,n = 3： (w3, v3) = (6, 5),w = P00 + 6 = 6

27、v = P01 + 5 = 5,将(0, 0)放入Q中，因是受控点被删去。,将(6, 5)放入Q中，放在了(0, 0)之后。,w = P10 + 6 = 10 v = P11 + 5 = 11,将(4, 6)放入Q中，删去受控点(6, 5)并取代了它的位置。,将(10, 11)放入Q中，放在(4, 6)之后。,w = P20 + 6 = 15 v = P21 + 5 = 15,将(9, 10)放入Q中，放在 (4, 6)之后 ，而(10, 11)挪动了一行 。,因为w = 15c，所以(15, 15)不再放入Q中 。,将Q拷贝到P。 结束了P3的计算。,n = 2： (w2, v2) = (2

28、, 3),w = P00 + 2 = 2 v = P01 + 3 = 3,将(0, 0)放入Q中，因是受控点被删去。,将(2, 3)放入Q中，放在了(0, 0)之后。,w = P10 + 2 = 6 v = P11 + 3 = 9,将(4, 6)放入Q中，放在了(2, 3)之后。,将(6, 9)放入Q中，放在了(4, 6)之后。,w = P20 + 2 = 11 v = P21 + 3 = 13,将(9, 10)放入Q中，放在(6, 9)之后。,因为w = 11c，所以(11, 13)不再Q中。,w = P30 + 2 = 12 v = P31 + 3 = 14,将(10, 11)放入Q中，放

29、在(9, 10)之后。,因为w = 12c，所以(12, 14)不再放入Q中。,将Q拷贝到P。 结束了P2的计算。,n = 1： (w1, v1) = (2, 6),w = P00 + 2 = 2 v = P01 + 6 = 6,将(0, 0)放入Q中，因是受控点被删去。,将(2, 6)放入Q中，插在了(0, 0)之后。,w = P10 + 2 = 4 v = P11 + 6 = 9,将(2, 3)放入Q中，因是受控点被删去。,将(4, 9)放入Q中，放在了(2, 6)之后。,w = P20 + 2 = 6 v = P21 + 6 = 12,将(4, 6)放入Q中，因是受控点被删去。,将(6, 12)放入Q中，放在了(4, 9)之后。,w = P30 + 2 = 8 v = P31 + 6 = 15,将(6, 9)放入Q中，因是受控点被删去。,将(8, 15)放入Q中，放在(6, 12)之后。,w = P40 + 2 = 11 v = P41 + 6 = 16,将(9, 10)放入Q中，因是受控点被删去。,因为w = 11c，所以(11, 16)不再放入Q中。,w = P50 + 2 = 12 v = P51 + 6 = 17,将(10, 11)放入Q中，因是受控点被删去。,因为w = 12c，所以(12, 17)不再放入Q中。,将Q拷贝到P，结束了P1的计算。,71