《计算机算法设计与分析》PPT第三章-动态规划

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

2、ic programming）是运筹学的一个分支，20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(Multistep decision process)的优化问题时，提出了著名的最优性原理，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法动态规划。 多阶段决策问题：求解的问题可以划分为一系列相互联系的阶段，在每个阶段都需要做出决策，且一个阶段决策的选择会影响下一个阶段的决策，从而影响整个过程的活动路线，求解的目标是选择各个阶段的决策使整个过程达到最优。,5,动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静

3、态规划（如线性规划、非线性规划），可以人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。 动态规划是考察问题的一种途径，或是求解某类问题的一种方法。 动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比其它方法求解更为方便。,6,基本概念 状态：表示每个阶段开始时，问题或系统所处的客观状况。状态既是该阶段的某个起点，又是前一个阶段的某个终点。通常一个阶段有若干个状态。 状态无后效性：如果某个阶段状态给定后，则该阶段以后过程的发展不受该阶段以前各阶段状态的影响，也

4、就是说状态具有马尔科夫性。 适于动态规划法求解的问题具有状态的无后效性 策略：各个阶段决策确定后，就组成了一个决策序列，该序列称之为一个策略。由某个阶段开始到终止阶段的过程称为子过程，其对应的某个策略称为子策略。,7,最优性原理,Bellman最优性原理 求解问题的一个最优策略序列的子策略序列总是最优的，则称该问题满足最优性原理。 注：对具有最优性原理性质的问题而言，如果有一决策序列包含有非最优的决策子序列，则该决策序列一定不是最优的。,8,动态规划的思想实质是分治思想和解决冗余 动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题,算法总体思想,9,但是经分解得到的子问题往

5、往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。,算法总体思想,10,如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。,T(n),算法总体思想,11,动态规划基本步骤,找出最优解的性质，并刻划其结构特征。 递归地划分子问题，递归地定义最优值，给出最优解的递归式。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。,注： 步骤是动态规划算法的基本步骤。如果只需要求出最优值的情形，步骤可以省略； 若需要求出问题的一个最优解，则必须执行步骤，步骤中记录的信息是构

6、造最优解的基础；,12,给定n个矩阵 ，其中 与 是可乘的， 。考察这n个矩阵的连乘积 由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。 若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积,3.2矩阵连乘问题,13,完全加括号的矩阵连乘积,完全加括号的矩阵连乘积的递归定义： （1）单个矩阵是完全加括号的； （2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即,14,15,矩阵连乘问题,问题描述 给定n个矩阵A1,A2,

7、An，其中Ai与Ai+1是可乘的，矩阵Ai的维数为pi-1pi，i=1，2，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。 注意 设Apq, Aqr两矩阵相乘，普通乘法次数为pqr； 加括号对乘法次数的影响,16,17,穷举法 列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。,算法复杂度分析： 对于n个矩阵的连乘积，设其不同的计算次序为P(n)。 由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1.Ak)(Ak+1An)可以得到关于P(n)的递推式如下：,因此，穷举法不是一个有效算法。,

8、呈指数增长,18,计算量小的优先计算 n个矩阵的连乘积共有n-1次乘法计算。首先在n-1次乘法计算中选择乘法计算量最小的两个矩阵优先计算，然后再在剩下的n-2次乘法计算中选择计算量最小的两个矩阵进行计算，依此往下。 该解决策略在某些情况下可得到最优解，但在很多情况下得不到最优解。如上例的第(5)种完全加括号方式即采用该策略，但得到的显然不是最优解。,19,矩阵维数大的优先计算 在n个矩阵的n+1个维数序列p0 ,p1, p2, pn中选择维数的最大值（设为pi），并把相邻两个含有维数pi的矩阵优先进行计算，然后在剩下的n个维数序列中再次选择维数的最大值，进行相应矩阵的乘法运算，依此往下。 该策

9、略与上一种策略相似，在某些情况下可得到最优解，但在有些情况下得不到最优解。如上例的第(3)种完全加括号方式就是采用该策略，显然它得到的是最优解。 当个矩阵的维数改为5010, 1040, 4030和305时，可验证采用该策略得到的不是最优解。,以上两种策略实质都是基于某种贪心选择的贪心算法，这种算法不一定能得到问题的全局最优解。在下一章我们将详细讨论此种策略。,20,分治法 将矩阵连乘积AiAi+1Aj简记为Ai:j。 设n个矩阵的连乘积A1A2An的计算次序在矩阵Ak和Ak+1之间将矩阵链断开，1kn，则其相应的完全加括号方式为(A1.Ak)(Ak+1An)。 完全加括号是一个递归定义，可递

10、归地计算A1：k和Ak+1:n ，然后将计算结果相乘得到A1：n。 可设计如下递归算法recurmatrixChain：,21,22,该递归算法的的计算时间T(n)可递归定义如下： 当n1时， 该算法的计算时间T(n)有指数下界。 分治法是该问题的一个可行方法，但不是一个有效算法。,23,为何分治法的效率如此低下？ recurmatrixChain(1,4)计算A1：4的递归树。 从图中可看出，许多子问题被重复计算。 这是分治法效率低下的根本原因。,24,该问题可用分治思想解决，并存在大量冗余，可用动态规划求解。,25,动态规划,矩阵连乘问题,将矩阵连乘积 简记为Ai:j ，i j。,考察计算

11、Ai:j的最优计算次序。设这个计算次序在矩阵 Ak和Ak+1之间将矩阵链断开，i kj，则其相应完全 加括号方式为,计算量为Ai:k的计算量加上Ak+1:j的计算量，再加上 Ai:k和Ak+1:j相乘的计算量,26,1、分析最优解的结构,特征 计算Ai:j的最优次序所包含的计算矩阵子链 Ai:k和Ak+1:j的次序也是最优的。（反证可得） 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。 问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。,27,28,假设计算Ai:j(1ijn)所需要的最少数乘次数为mi,j，则原问题的最优值为m1,n i=j时，Ai

12、:j=Ai，mi,i=0，i=1,2,n ij时，,的维数为,2、建立递归关系,29,递归地定义mi,j,k的位置只有j-i种可能,取得的k为Ai:j最优次序中的断开位置，并记录到表sij中，即sijk。 注：mij实际是子问题最优解的解值，保存下来避免重复计算。,30,对于1ijn不同的有序对(i，j)对应于不同的子问题。不同子问题的个数最多只有 由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。,3、计算最优值,31,用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。 在计算过程中，保存已解决的子问题答案。 每个子问题只计算一次

13、，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法。,32,s,void MatrixChain(int *p，int n，int *m，int *s) /n是连乘矩阵数目，A1A2An；p是矩阵维数，Ai的维数为pi-1pi(1in)； /m是n个矩阵连乘的数乘次数最小值；s存储矩阵连乘的最优计算次序 for(int i = 1; i = n; i+) mii = 0; /对角线置0,计算Ai.Ai的乘法次数,链长为1 for (int r = 2; r = n; r+) /分别计算r个矩阵连乘的最小数乘次数 for (int i = 1; i = n - r+

14、1; i+) int j=i+r-1; mij = mi+1j+ pi-1*pi*pj; /Ai.Aj在矩阵i处断开时的数乘次数 sij = i; /记录取得Ai.Aj当前数乘次数的断开位置 for (int k = i+1; k j; k+) /计算Ai.Aj的最小数乘次数 int t = mik + mk+1j + pi-1*pk*pj; if (t mij) mij = t; sij = k; ,33,34,算法复杂度分析： 算法MatrixChain的主要计算量取决于算法中对r，i和k的3重循环。循环体内的计算量为O(1)，而3重循环的总次数为O(n3)。因此算法的计算时间上界为O(n

15、3)。算法所占用的空间显然为O(n2)。,设要计算矩阵连乘积中各矩阵的维数分别为：,35,4、用动态规划法求最优解,MatrixChain已记录了构造最优解所需要的全部信息。 Sij 表明计算矩阵Ai,j的最佳方式应在矩阵Ak和Ak+1之间断开，即最优的加括号方式应为(Ai:k)(Ak+1:j)。 从s1n记录的信息可知A1:n的最优加括号方式为(Ai:s1n)(As1n +1:n)。 Ai:s1n的最优加括号方式为(Ai:s1s1n)(As1s1n+1:s1s1n) As1n +1:n的最优加括号方式在ss1n +1n处断开。 照此递推，最终可确定A1:n的最优完全加括号方式，即构造出问题的

16、一个最优解。,36,算法traceback：按照MatrixChain计算出的断点s指示加括号方式输出计算Ai:j的最优计算次序。,Void traceback(int i,int j,int *s)/按算法MatrixChain计算出的断点矩阵s指示的加括号方式输出计算Ai:j的最优计算次序 if(i=j) return; traceback(s,i,sij); traceback(s,sij+1,j); cout“Multiply A”i“,”sij; cout“and A”(sij+1)“,”jendl; ,37,一、最优子结构,矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性

17、质称为最优子结构性质。 在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。 利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。,同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）,3.2动态规划算法的基本要素,38,二、重叠子问题,递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。

18、动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。 通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。,39,三、备忘录方法,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

19、 t = LookupChain(i，k) + LookupChain(k+1，j) + pi-1*pk*pj; if (t u) u = t; sij = k; mij = u; return u; ,备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。,40,动态规划的设计技巧：阶段的划分、状态的表示和存储表的设计 在动态规划的设计过程中，阶段的划分和状态的表示是其中最重要的两步，这两步会直接影响该问题的计算复杂性和存储表设计，有时候阶段划分或状态表示的不合理还会使得动态规划法不适用。 问题的阶段划分

20、和状态表示，需要具体问题具体分析，没有一个清晰明朗的方法。 在实际应用中，许多问题的阶段划分并不明显，这时如果刻意地划分阶段法反而麻烦。一般来说，只要该问题可以划分成规模更小的子问题，并且原问题的最优解中包含了子问题的最优解（即满足最优性原理），则可以考虑用动态规划解决。,41,如何判断问题满足最优性原理？ 思路：利用反证法，通过假设每一个子问题的解都不是最优解，然后导出矛盾，即可做到这一点。,42,例1：设G是一个有向加权图，则G从顶点i到顶点j之间的最短路径问题满足最优性原理。,证明：（反证法） 设iipiqj是一条最短路径，但其中子路径ipiqj不是最优的。 假设最优的子路径为ipiqj

21、，则我们可以重新构造一条路径：iipiqj，显然该路径长度小于iipiqj，与iipiqj是顶点i到顶点j的最短路径相矛盾。 所以，原问题满足最优性原理。,43,例2：有向图的最长简单路径问题不满足最优性原理。,证明： 如右图所示，qrt是q到t的最长简单路径，而qr的最长简单路径是qstr，rt的最长简单路径是rqst，但qr和rt的最长简单路径合起来并不是q 到t的最长简单路径。 所以，原问题并不满足最优性原理。 注：因为qr 和rt的子问题都共享路径qst，组合成原问题解时，有重复的路径对原问题是不允许的。,44,45,46,47,48,49,50,51,52,53,实例二 花束摆放问题

22、,1、问题描述 现有F束不同品种的花束，同时有至少同样数量的花瓶被按顺序摆成一行，其位置固定于架子上，并从1至V按从左到右顺序编号，V是花瓶的数目(FV)。花束可以移动，并且每束花用1至F的整数唯一标识。标识花束的整数决定了花束在花瓶中排列的顺序，如果ij，花束i必须放在花束j左边的花瓶中。每个花瓶只能放一束花。如果花瓶的数目大于花束的数目，则多余的花瓶空置。,54,每一个花瓶都具有各自的特点。因此，当各个花瓶中放入不同的花束时，会产生不同的美学效果，并以一美学值(一个整数)来表示，空置花瓶的美学值为零。为取得最佳美学效果，必须在保持花束顺序的前提下，使花束的摆放取得最大的美学值。请求出具有最

23、大美学值的一种摆放方式。,55,2、解题思路 状态表示法一： 设A(i,j)表示第i种花束摆在第j个花瓶中获得的美学值。S(i,k)表示第i种花束摆在第k个花瓶中时(ki)，前i种花束能够获得的最大美学值(之和)。这样，原问题的最优值可通过计算maxS(F,k)|FkV获得。 下面分析这种状态表示法描述问题的方式是否具备了用动态规划求解的基本要素。,56,最优子结构性质：对满足FkV的k，设T(F,k)是达到最优值S(F,k)的一种最佳摆放方式，其中，第F-1种花束摆在第j个花瓶中(jk)，则T(F,k)中前F-1种花束的摆放方式获得的最大美学值为S(F-1,j)。故对每个满足FkV的k，计算

24、S(F,k)的问题具有最优子结构性质。 递归方程：,57,在计算S(i-1,k-1)时，已经计算出了S(i-1,j)，i-1 jk-2及其maxS(i-1,j)|i-1jk-2。 因此，计算S(i,k)时，只要将S(i-1,k-1)与maxS(i-1,j)|i-1jk-2进行比较即可求得，即子问题重叠性质。这样做可大大减少计算量。,58,状态表示法二： 设Si,k表示第i种花束摆在第k个之前(包括第k个)的任意某个花瓶中，前i种花束能够获得的最大美学值(之和)。这样，原问题的最优值即为SF,V。这比前一个表示法更直接。,59,容易验证，计算SF,V的问题具有最优子结构性质。 递归方程为： Si

25、,k=maxSi-1,k-1+A(i,k), Si,k-1,i1,ki 初始条件为： S1,1=A1,1 S1,k=maxA(1,k),S1,k-1,k1 Si,i=Si-1,i-1+A(i,i),i1,60,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。,61,例： 两个DNA序列 S1=ACCGGTCGAGTGCGC GGAAG

26、CCGGCCGAA S2=GTCGTTCGGAATGCC GTTGCTCTGTAAA LCS=GTCGTCGGAAGCCG GCCGAA,62,两个序列的公共子序列定义 给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。 问题 给定2个序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最长公共子序列。,63,定理：(一个LCS的最优子结构) 设序列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且

27、zkxm，则Z是xm-1和Y的最长公共子序列。 (3)若xmyn且zkyn，则Z是X和yn-1的最长公共子序列。,2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。,1、最长公共子序列的结构,64,65,66,2、子问题的递归结构,将X和Y的LCS分解为2种情况： 如xm=yn，找Xm-1和Yn-1的LCS； /解一个子问题 如xmyn，找Xm-1和Y的LCS； 找X和Yn-1的LCS； /解两个子问题 取两者中的最大的；,67,用cij记录序列Xi和Yj的最长公共子序列的长度。Xi=x1,x2,xi；Yj=y1,y2,yj。 cij的

28、递归方程：,当i=0或j=0时，空序列是Xi和Yj的最长公共子序列，Cij=0。,68,69,3、计算最优值,void LCSLength(int m，int n，char *x，char *y，int *c，int *b) int i，j; for (i = 1; i =cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; ,0,70,过程LCSLength以两个序列x、y为输入，它把ci,j的值填入一个按行计算表项的表c0.m, 0.n中，并维护表b1.m, 1.n以简化最优解的构造。 c0.m, 0.n /存放最优解值，计算时行优先 b1.m,

29、1.n /解矩阵，存放构造最优解信息 bi,j指向一个表项，对应于在计算ci,j时所选择的最优子问题的解。 程序最后返回b和c。cm,n包含X和Y的一个LCS的长度。,71,由于在所考虑的子问题空间中，总共有(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。,72,4、构造最长公共子序列,构造最长公共子序列 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,

30、x,b); else LCS(i,j-1,x,b); ,说明 当bi,j=1时，即xi=yj是LCS的一个元素； 时间复杂度：(m+n),73,构造解时，从bm,n出发，上溯至i=0或j=0，上溯过程中，当bi,j1时打印出xi或yj,74,例：X=，Y= 最优解：BCAB或BCBA或BADB,75,5、算法的改进,在算法LCSLength和LCS中，可进一步将数组b省去。 cij的值仅由ci-1j-1，ci-1j和cij-1这3个数组元素的值所确定。 对于给定的数组元素cij，可以不借助于数组b而仅借助于c本身在O(1)时间内确定cij的值是由ci-1j-1，ci-1j和cij-1中哪一个值

31、所确定的。,76,如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。 计算cij时，只用到数组c的第i行和第i-1行。 只用2行的数组空间就可计算出最长公共子序列的长度。 进一步的分析还可将空间需求减至O(min(m,n)。,77,3.4最大子段和,问题 给定由n个整数(可能为负整数)组成的序列a1,a2,an，求该序列形如 的子段和的最大值。当所有整数均为负数时定义其最大子段和为0。 依此定义，所求的最优值为,78,例：整数序列(a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2) 最大子段和为：,79,1、最大子段和问题的简单算法,简单算法 数组a 存

32、储给定的n个整数 时间复杂度为O(n3),80,改进 对k循环可以省略 改进后的算法时间复杂度为O(n2),81,2、最大子段和问题的分治算法,将a1:n分为长度相等的两段a1:n/2和an/2+1:n，分别对两区段求最大子段和，则a1:n的最大子段和有三种情形： a1:n的最大子段和与a1:n/2的最大子段和相同 a1:n的最大子段和与an/2:n的最大子段和相同 a1:n的最大子段和为 对可递归求解 对可知an/2、 an/2+1一定在最大和子段中 在a1:n/2中计算， 在an/2+1:n中计算， s1+s2是该情况下的最大值。,int MaxSubSum(int *a,int left

33、,int right) /返回最大子段和 int sum=0; if(left=right) sum=aleft0?aleft:0; else int center=(left+right)/2; int leftsum=MaxSubSum(a,left,center); int rightsum=MaxSubSum(a, center+1, right); int s1=0; int lefts=0; for(int i=center;i=left;i-) lefts+=ai; if(leftss1) s1=lefts; /for,int MaxSum(int n,int *a) retur

34、n MaxSubSum(a,1,n); ,int s2=0; int rights=0; for(int i=center+1;is2) s2=rights; /for sum=s1+s2; if(sumleftsum) sum=leftsum; if(sumrightsum) sum=rightsum; /if return sum; /end,83,复杂度分析,84,3、最大子段和问题的动态规划算法,描述最优解的结构 子问题定义：考虑所有下标以j结束的最大子段和bj，即 原问题与子问题的关系：,85,递归定义最优解的值 bj=maxbj-1+aj,aj,1jn,86,求最大子段和的动态规划

35、算法 int MaxSum(int n,int *a) int sum=0,b=0; /sum存储当前最大的bj,b存储当前bj for(int i=1;i0) b+=ai; else b=ai; /b=0 if(bsum) sum=b; return sum; ,87,4、最大子段和问题与动态规划算法的推广,最大子矩阵和问题 给定一个m行n列的整数矩阵A，试求矩阵A的一个子矩阵，使其各元素之和为最大。 二维数组a1:m1:n表示给定m行n列的整数矩阵。 子数组ai1:i2j1:j2表示左上角和右下角行列坐标分别为(i1,j1)和(i2,j2)的子矩阵。 各元素之和 最大子矩阵和问题的最优值为

36、,88,最大m子段和问题 给定由n个整数（可能为负整数）组成的序列a1, a2, , an，以及一个正整数m，要求确定序列a1, a2, , an的m个不相交子段，使这m个子段的总和达到最大。 设b(i,j)表示数组a的前j项中i个子段和的最大值，且第i个子段含aj 。 所求的最优值为 。,89,计算b(i,j)的递归式为 初始时，,90,3.5多段图规划,问题描述 多段图G=(V,E)是一个有向图，且具有以下特征： 划分为k2个不相交的集合Vi, 1ik; V1和Vk分别只有一个结点s(源点)和t(汇点)； 若E(G)，uVi，则vVi+1,边上成本记c(u,v)；若不属于E(G)，边上成本

37、记c(u,v)=。 求由s到t的最小成本路径。,91,例：一个5-段图 求从s到t的最短路径。,92,多段图问题满足最优性原理 设s,vip,viq,t是一条由s到t的最短路径，则vip, viq,t也是由vip到t的最短路径。(反证即可) 递归式推导 设cost(i, j)是Vi中结点vj到汇点t的最小成本路径的成本，递归式为：,93,计算过程(以5-段图为例) cost(4, 9)=4, cost(4, 10)=2, cost(4, 11)= cost(3, 6)=7, cost(3, 7)=5, cost(3, 8)=7 cost(2, 2)=7, cost(2, 3)=9, cost(

38、2, 4)=18, cost(2, 5)=15 cost(1, 1)=min9+cost(2,2), 7+cost(2,3), 3+cost(2,4), 2+cost(2,5) = 16 构造解：解1(1, 2, 7, 10, 12)，解2(1, 3, 6, 10, 12),94,95,3.60-1背包问题,问题描述 给定n种物品和一个背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?,96,0-1背包问题是一个特殊的整数规划问题。 求(x1,x2,xn)使目标函数最大，其中c0, wi 0, vi 0, 1in 0-1背包问题

39、Knapsack(1,n,c),97,例：w = ( w1, w2, w3) = (2, 3, 4) v=(v1, v2, v3)=(2, 3, 4) 求Knapsack(1, 3, 6) 取x = (1, 0, 1)时，Knapsack(1,3,6) = (v1x1+v2x2+v3x3) = 1*1 + 2*0 + 5*1 = 6最大 用穷举法求解，时间复杂度为O(n2n),98,1、 最优子结构性质,证明：(反证法) 设(y1,y2,yn)是Knapsack(1,n,c)的一个最优解，则(y2,yn)是Knapsack(2,n,c-w1y1)子问题的一个最优解。若不然，设(z2,zn)是K

40、napsack(2,n,c-w1y1)的最优解，因此有 说明(y1,z2,zn)是Knap(1,n,c)的一个更优解，矛盾。,0-1背包问题Knapsack(1, n, c)满足最优性原理,99,2、 递归关系,设所给0-1背包问题的子问题记为Knapsack(i, n, j)， jc(假设c, wi取整数) Knapsack(i, n, j)的最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，n时0-1背包问题的最优值。 注：子问题的背包容量j在不断地发生变化,100,由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下： 临界条件,说明：当jwi

41、时，只有xi =0，则m(i,j)=m(i+1,j) 当jwi时，取xi =0时，为m(i+1,j) 取xi =1时，为m(i+1,j-wi)+ vi,3、 算法描述,void Knapsack (Type *v, int *w, int c, int n, Type *m) /m1c为最优值 int jMax=min(wn-1,c); /jjMax,即0jwn; jjMax,即jwn for(int j=0;i1;i-)/i1表示对i=1暂不处理 i=1时只需求m1c jMax=min(wi-1,c); for(int j=0;j=w1) m1c=max(m1c,m2c-w1+v1); ,102,void Traceback(Type *m, int *w, int c, int n, int *x) /输出解X for (int i=1;in;i+) if (mic=mi+1c) xi=0; else xi=1; c-=wi; xn=(mnc)?1:0; ,103,4、 计算复杂性分析,算法复杂度分析 从m(i，j)的递归式容易看出，算法需要O(nc)计算时间。当背包容量c很大时，算法需要的计算时间较多。 例：当c2n时，算法需要(n2n)计算时间。,10