第8章组合算法与计算复杂性课件.ppt

《第8章组合算法与计算复杂性课件.ppt》由会员分享，可在线阅读，更多相关《第8章组合算法与计算复杂性课件.ppt（158页珍藏版）》请在三一办公上搜索。

1、第八章 组合算法与计算复杂性,8.1 回溯、剪枝与分治算法 8.2 动态规划技术 8.3 试探（启发式）算法 8.4 作业安排问题 8.5 图灵机与特殊语言类,8.1 回溯、 剪枝与分治算法,8.1.1 回溯法（Backtracking） 回溯法有“通用解题法”的美称。用回溯法可以求得问题的所有解或任意解。 回溯法按深度优先搜索策略搜索状态空间树， 从而改进了对解空间所有向量进行穷举，并检查约束条件搜索解的朴素做法， 减少了搜索工作量。 其基本思想如下：,设问题的解x所属的解空间为E=x=(x1, x2, , xn)|xiSi, i=1, 2, , n，构造一棵状态空间树T，解x所满足的约束条

2、件为Pn(x1, x2, , xn)。若k元组(x1, x2, , xn)使Pk(x1, x2, , xk)成立(kn)，则称(x1, x2, , xk)为部分解，即T中的一个状态节点，激活该点。对已有部分解(x1, x2, , xk)， 在Sk+1中按序选取xk+1；若 xk+1 Sk+1 ，均不能使Pk+1(x1, x2, , xk+1)成立，即把状态节点(x1, x2, , xk)删去（或杀死），回溯到(x1, x2, , xk-1)，在Skxk中选取新的xk，激活新的状态节点(x1, x2, , xk)，检查Pk(x1, x2, , xk)是否成立。按这种方法对T搜索求解，直至得到解，

3、或者问题无解。对应问题P的状态空间树T可动态构造，也可作为一棵实际中并不出现的虚拟树存在。,例1(Gauss 八后问题) 88国际象棋棋盘上放置8个皇后。 为使各个皇后不能互相攻击， 要求任两个皇后都不在同一行、同一列或同一对角线上。 已知共有92种放法， 用回溯法可求出全部92种方案。 为简化问题，将88棋盘上的八后问题缩小到44棋盘上的四后问题。 用向量(x1, x2, x3，x4) 表示问题的一个解，即要求第i行上皇后放在第xi列。为方便计，称第i行上皇后为第i个皇后。 先放第1个皇后， 再依次放第2、 第3、 第4个皇后。 由国际象棋棋子攻击规则可知，问题的约束条件为任意二后不能在同行

4、、 同列或同一对角线上。,首先已知四后问题有解。 （1） 第1个皇后最初置于第1列， 以后根据回溯要求依次取第2、 第3、 第4列。 （2） 第2个皇后考虑约束条件最初只能置于第3列，依次还可取第4列，以后根据回溯要求后移1列，或依第1个皇后回溯结果再确定满足约束条件的新位置。 （3） 因对1后与2后确定的位置，第3个皇后无论放在哪个位置都违反约束条件， 故回溯。 （4） 第3个皇后依1后居第1列， 2后居第4列而置于第2列。,（5） 对（4）中结果， 因第4个皇后无论放在哪个位置都违反约束条件。 又3后右移1个，2个方格都违反约束条件， 加之2后已居第4列， 故回溯。 （6） 回溯结果1后置

5、于第2列。 （7） 1后居第2列， 2后只能选第4列。 （8) 3后置于第1列， 4后因放于第1、 2列均违反约束条件， 故放到第3列； 从而得到四后问题的一个解（2， 4， 1， 3）。 接着第4个皇后右移一格继续求解， 又可得到另一解（3， 1， 4， 2）。,回溯法求解问题时，要求若Pk(x1,x2,xk)不成立，则一定有Pk+1(x1,x2,xk+1)不成立。从而，当断定(x1,x2,xk)已不满足Pi(x1,x2,xk)时，由部分解不可能搜索到问题的解。 因而没必要继续求余下的分支，从而可以减少计算的工作量。 设xiXi，(x1,x2,xk)是部分解，xk+1的可选范围是xk+1的子

6、集Sk+1。例如上述四后问题中取x1=1之后，S2=3, 4。,回溯算法 1 若Sk非空，选xk是Sk中还未选过的最小值；若kn，则 k k+1, 并重复1；若k=n，则(x1, x2, , xn) 为一解；若要求出所有的解，则kk-1, 并重复1； 2 若Sk为空，且k=1，停止；若Sk为空，且k1，则kk-1，转1。,例2 求如下不等式的正整数解：3x1+2x2+x38，i=1, 2, 3， 1xi3 解 对i=1, 2, 3，令Xi=1, 2, 3，则P1(x1):3x18, 1x13 P2(x1 ，x2):3x1+2x28, 1 x1, x23 P3(x1，x2,x3):3x1+2x2

7、+x38, 1xi3, i=1, 2, 3 因若(x1，x2,x3)满足P3(x1，x2,x3)， 则(x1，x2,)一定满足P2(x1，x2)，且x1一定满足P1(x1)。 即问题的解对约束条件具有完备性或具有多米诺性质， 故适于用回溯法求解。,显见(x1=1)满足P1(1): 318, 即(1）为一部分解； 取(x1 =1, x2=1), P2(1， 1): 31+218, 11, 13 亦成立； 再取(x1 =1, x2 =1, x3=1), P3(1，1, 1):31+21+1=68 (1, 1, 1)为一解； (x1 =1, x2 =1, x3 =2), P3(1，1, 2):31+

8、21+2=78 (1, 1, 2)为一解； (x1 =1, x2 =1, x3 =3), P3(1，1, 3):31+21+3=88(1, 1, 3) 为一解； x3=4已违反约束条件。,取(x1=1,x2=2),P2(1，2)=3x1+2x2=31+22=78,1x1, x23亦成立； 再取(x1=1,x2=2,x3=1), P3(1，2, 1)=31+22+1=88(1, 2, 1)为一解，x3=2 已违反约束条件。 取 (x1=1, x2=3), P2(1，3)=31+23=98 已不满足原不等式。 不难验证，对(x1 =2)， (x1 =3)， 采用回溯法均已求不出问题的解。 故例2仅

9、有4个解： (1， 1， 1)， (1， 1， 2)， (1， 1， 3)，(1，2，1),注意1：回溯法能一个不漏地求出问题的解， 因为它只跳过对状态空间树中T不可能通向解的状态节点的搜索。 注意2：回溯法求解问题P的过程是系统地、 动态地搜索激活、 检查约束和回溯杀死状态空间树T的一个状态节点序列的过程。,注意3：可以采用回溯法求解的问题须满足完备性或多米诺性质。对如下问题求整数解：3x1+4x2-x310, i=1, 2, 3, 1xi3 因为3x1+4x2 10，但3x1+4x2-x310，即P2(x1, x2)不满足P3(x1, x2, x3)不满足，多米诺性质不成立，故不能采用回溯

10、法。这时可令x3 =3-x3，则原问题变为3x1+4x2+ x3 13,i=1, 2, 1xi3， 0 x32，时问题就满足了多米诺性质，可用回溯法求出解向量(x1, x2, x3 )，进而转为原问题的解(x1, x2, x3)。,注意4：改进回溯算法的途径。 （1） 回溯算法对于比较复杂的问题因执行时间太长而无法实现。但有些问题（如八后）所求状态，其位置从几何上看具有对称性， 从而可考虑改进算法， 减少工作量。 （2）把一个较大问题分解为几个子问题， 并利用子问题的解进行组合来求得原问题的解。 参见1.4节分治算法。,8.1.2 分支界限法（Branch and Bound） 分支界限方法是

11、从回溯法演变而来的，也是一种在状态空间树T上搜索解的过程。 二者的不同之处在于搜索目标。 回溯法旨在搜索T中满足约束的所有叶状态； 而分支界限法的求解目标则是找出T中满足约束且使某一目标函数达到极大（或极小）的叶状态，即问题在某种意义下的最优解。 回溯法只通过约束条件， 分支界限法除要通过约束条件， 还要通过目标函数的界限来减少无效搜索，提高搜索效率。,回溯法采用的是深度优先搜索策略，即先检查扩展节点的每个子节点，并把满足约束条件且不越过目标函数当前界限者都激活， 然后从中选出一个扩展节点继续搜索。 分支界限法中把满足约束条件的解称为可行解， 最后要求的最优解是指在最大（最小）化问题中， 求目

12、标函数值取最大（最小）的可行解。 因为最大、 最小是可以相互转化的， 如下仅讨论目标函数值取最小的情形。,状态空间树的每个分支点对应(x1, x2, , xk)，kn ，仍用(x1, x2, , xn)表示解。分支界限法求最小解时，对每个部分解，都有一相应的“代价”， 且“代价”函数应满足关系： C(x1, x2, , xk)C(x1, x2, , xk, xk+1)即父节点的代价不得超过子节点的代价。还要求代价函数和目标函数在叶状态的值相同。 当找到一个可行解Y时，设Y的代价为B。对状态空间树中搜索到的某个分支点X， 若X的代价大于B，则其子孙的代价会更大， 故不可能成为最优解，因此，没有必

13、要再搜索X的子孙。 可将X为根的子树剪去， 减少计算工作量。 一般将可行解的代价作为上界B， 当找到一个更优（代价更小）的解时，B就修改成这个解的代价。,求最大解可类似讨论。 对有些问题，代价函数C(x1, x2, , xk-1)往往不易求得，但可用一个容易计算的函数C*(x1, x2, , xk-1)代替C(x1, x2, , xk-1)。,例3(分配问题) 设有4个零件P1，P2，P3，P4，要在4台机器m1，m2，m3，m4 上加工。矩阵A=(aij)中，(aij) 表示Pj在mi上加工的时间。 规定每个零件只能在一台机器上加工，且每台机器只能加工一个零件， 这是约束条件。 求耗时最少的

14、加工安排方案。,用向量(x1, x2, x3, x4)表示Pi在mxi上加工，i=1, 2, 3, 4 。由问题的约束条件知x1, x2, x3, x4 是1, 2, 3, 4的一个排列。满足约束条件的解称为可行解，使目标函数ax1, 1+ax2, 2+ax3, 3+ax4, 4取最小值的可行解为最优解。 因m1加工P1耗时最少，可取C*(1)=4为下界，并取x1=1，其余xi值待定，部分解为（1），因P1在m1上加工，在矩阵A中不再考虑第1行、第1列。从A中删去第1行、第1列, 得子矩阵：,图 8.1.1 例3插图,例4 (背包问题) 设xj为放入背包内Pj类物件的件数，b为背包内允许装入物

15、件的最大重量，wj，vj(1jn)分别为Pj类物件的重量和价值, 则背包问题（在不超重前提下装入物件价值最大）可归结为如下整数规划问题：,即求满足约束条件并使目标函数值取最大的解(x1, x2, , xn)。,解背包问题之前先将物件按价值比重量进行排序并编号， 考虑把单位重量价值高的物件排在前边优先装包，使得对物件重新编号后有vi/wivi+1/wi+1。 背包问题的解由n元组(x1, x2, , xn)表示，属状态空间树T的叶节点。k元组(kn)(x1, x2 , , xk)为部分解，是树T的分支点。此时，对已装入背包内物件的重量 ，有如下2种情况：,（1） 存在jk，使得,这表明背包内还可

16、装入物件xj(jk)而不超重。其中，若全部放Pk+1类物件自然要比放其它物件价值高。从而，对部分解(x1, x2, , xk)，相应的函数值C*(x1, x2, , xk)就取为,由于vi/wivi+1/wi+1，上式给出的值就是前缀为(x1, x2, ,xk)的可行解的目标函数值的一个上界。且这样确定的C*值满足,C*(x1, x2, , xk)C*(x1, x2, , xk, xk+1),（2） 对所有jk，,这说明背包内已无法放入任一Pj(jk)类物件，否则就会超重。它对应的可行解为解空间中的向量(x1, x2, , xk, 0, 0, , 0)，故在树T的这个状态点上不必再生成子节点。

17、C*(x1, x2, , xk)就取,设背包内可放4种物件P1, P2, P3, P4，已知w1=8, w2=6, w3=5, w4=2；v1=10, v2=7, v3=5, v4=1。限制背包内总重不超过10。求把物件放入背包在不超重的前提下使装入物件价值最大的方案。,解 根据题意， 可得如下整数规划问题:约束条件： 8x1+6x2+5x3+2x410 目标函数： z=10 x1+7x2+5x3+x4 求4元组(x1, x2, x3, x4)， xi为非负整数(i=1,2, 3, 4)， 满足约束条件且使目标函数z取最大值。,一般情况下需要对物件先进行排序编码，因本例所给物件已满足v1/w1

18、v2/w2v3/w3v4/w4，即10/87/65/51/2，就按P1, P2, P3, P4先后排列的优先顺序向背包内放物件。背包容纳物件重量限制为10，已知w1=8， 放入背包的物件数只能是0个或1个。记X1=0, 1，同理可得X2=0, 1，X3=0, 1, 2，X4=0, 1, 2, 3, 4, 5。 在要生成的状态空间树T中，根节点只有2个子节点(1)及(0)。 第1层节点也有2个子节点，第2层节点有3个子节点，第3层节点有6个子节点。,由根生成子节点（0）和（1），有,图 8.1.2 例4插图,8.1.3 游戏树与-剪裁 在博弈游戏中，对弈双方需要根据当前弈局分析预见以后的格局，

19、选择自己的对策，希望能战胜对方，战平对方，或在最不利的情况下， 输得最少。 决策树是处理对弈乃至一般竞争的工具。 设有2个人F（First，先手）与S（Second，后手）玩棋子游戏，一共6枚棋子，2人轮流取，每次可取1枚、 2枚、3枚，但不能不取； 谁最后取完棋子算谁赢，且取到几枚赢几分。,图 8.1.3 6子游戏树,参见图8.1.3， 方框表示轮F取子， 圆圈表示轮S取子， 其中的数字表示剩余棋子数，边上的数字表示取走的棋子数，叶节点处标F表示F赢，标S表示S赢。叶节点中的数值表示F（或S）赢得的分值。 现从对策树中要选出估计可能是“最好”的一系列对策。这种估计是由树叶的估计函数值通过最大

20、最小过程进行的。树叶的估价函数值是静态的估价函数值，这是从现在的格局以及对将来的影响综合得到的。,由于游戏是F、 S双方轮流进行， 决策树以一方（如F）考虑每个分支的估价函数值。 图8.1.4是一棵假象对策树。 树叶上的值是事先对格局综合考虑后给出的。 其中方框节点表示由F作决策， 圆圈节点表示由S作决策。 如果以赢x分表示F赢x分， 当然F希望赢的分值越大越好，故称F为极大化者。 对S而言， 自然希望这个x越小越好， 甚至一直小到-x， 即F赢-x分或看作S赢|x|分，故称S为极小化者。,图 8.1.4 由叶节点导出的决策树,从而对F而言， 给每个方框节点都从子节点选最大值填入； 而对S而言

21、， 给每个圆圈节点都从子节点中选最小值填入。 对于一个比较复杂的游戏，如果采用上述分析方法，从树叶开始一步一步向回推， 直到树根为止， 这实际上几乎是不可能的。从而对某些问题考虑采用分支界限的方法，对决策树而言， 就称这种技术为-剪裁。,图 8.1.5 -剪裁,在图8.1.5（a）中， r为极大化点， u是r的子节点且u值为。 当v时， 在搜索中就可删去v及以它为根的子树。 亦即， 可把v为根的子树从决策树中剪掉， 常称其为CD*2剪裁。 值称为r的下剪裁值。对于r的后裔， 凡是小于r的下剪裁值者都要剪掉。 不难发现，如果r的下剪裁值为，则r的所有后裔的下剪裁值也是。 因为对r的后裔，比如v，

22、 它是极小化点， 只有当v的所有儿子都大于等于时， v的值才能大于等于。故对v的所有小于的子节点根本不必考虑。,类似地，可定义r的上剪裁值。 在图8.1.5(b)中， r是极小化点， u是r的一个子节点，且u值为。如果v值， 则可以把以v为根的树从决策树中剪裁掉, 常称其为-剪裁，并称为上剪裁值。不难看出，当r的上剪裁值为时，r的所有后裔的上剪裁值也是。 如图8.1.6所示的对策树， 采用-剪裁技术后变为图8.1.7。,图 8.1.6 剪裁树,图 8.1.7 -剪裁实例,8.1.4 分治算法 分治算法是一种重要的设计算法的方法。一般将一个规模大的问题分割成若干个子问题，解出这些子问题后，再把它

23、们组合成原问题的解。 往往子问题和原来问题的类型相同，这就可与递归过程结合使用。 分治算法中一个著名的例子是Strassen的矩阵相乘算法。 设A, B为两个nn矩阵，乘积C=AB也是nn矩阵,计算C(i, j)要n次乘法, n-1次加法。矩阵C一共有n2个元素，因此总共需要作n2(n-1)次加法, n3次乘法。分治算法提出了另一种计算矩阵的方法。为简单起见，假设n=2k，把矩阵分别划分为4个n/2n/2的子矩阵，矩阵A和B相乘为,通常矩阵乘法是,Strassen计算Cij的方法，仅需要7次矩阵乘法和18次矩阵加减法，公式如下：,设T(n)是两个nn矩阵乘积所需的元素运算（乘法，加减法）次数。

24、依上述Strassen方法，可得递推公式:,于是,其中，n=2k, k=lbn。因此Strassen矩阵相乘算法的时间复杂性是O(nlb7)O(n2.81) K.Glover证明恰有36种方法计算Cij，每种方法仅使用7次乘法。以下再介绍一种。,S1=A21+A22, S2=S1-A11, S3=A11-A21, S4=A12-S2S5=B12-B11, S6=B22-S5, S7=B22-B12, S8=S6-B21M1=S2S6, M2= A11B11, M3= B21, M4= S3 S7 ;M6=S4B22, M7= A22 S8, T1= M1 + M2,T2= M1 + M4 ;C

25、11=M2+M3, C12=T1+M5+M6, C21=T2-M7, C22=T2+M5,一共7次矩阵乘法和15次矩阵加减法。若能找到一个方法， 少于7次矩阵乘法，则时间复杂性O(n2.81)能进一步减少。但是， Hopcroft和Kerr证明7次乘法是必需的， 再也不能减少。Victor pan发现新方法，时间复杂性是O(n2.734)。,8.2 动态规划技术,所谓动态规划, 是相对于静态规划而言的。一般的线性或非线性规划问题，不涉及与时间有关的因素，故称之为静态规划。 在动态规划中，要处理的问题可以分成多个子问题，子问题互相关联，形成多个阶段，多阶段的决策策略只与有关阶段的因素有关，因此可

26、以独立处理，为随后的处理提供先决条件，连锁反应到下一个阶段，最终导致整个问题获解。从整体上看，连锁反应的各阶段间增添了一种伪时间因素，故称之为动态规划。许多静态规划问题若按照动态规划思想划分成阶段处理，也可用动态规划的方法予以解决， 效果会更好。,动态规划是设计组合算法的一个重要技术， 在求解最优化问题上非常有用。正是由于它是用于许多问题的一种普遍技术， 因而在求解某些具体问题上不如专门精心设计的算法效率高。 尽管如此， 动态规划仍不失为求解最优化问题的一种重要的方法。下面通过求最短路的例子来说明动态规划的思想。,例1(最短路问题) 图8.2.1(a)是一个街道的平面图。 直线表示街道， 顶点

27、表示街道的交叉口。 边上的权表示对应一段街道的长度。一个人要从S走到T，走向只能是向下、向右。求最短的行走路线。,图 8.2.1 街道平面图转换为多阶段图(a) 街道平面图； (b) 多阶段图,用d表示向下走，r表示向右走。从S到T的一条路对应3个d与3个r的排列。因此一共有C(6, 3)=20条从S到T的路。若列举出每一条路， 分别求出它们的长度，从中选出一条最短路， 这是一个朴素的方法。在街道数增长时，计算量与C(2n, n)成正比， 其中n为d(r)的个数。这样计算量是指数级。使用动态规划方法， 计算量可以降到多项式级。,在图8.2.1(a)中，L=SA1B2C3D3E2T是从S到T的最

28、短路，任取最短路l的一部分路，从这部分路的起点到它的终点，沿着这段路走一定是最短的。例如,l1=SA1B2C3是l的部分路，是从S到C3的最短路。若还有一条从S到C3的更短的路，在l中用它来代替l1， 将得到一条比l更短的路，这与l是最短路矛盾。因此，只有最短的部分路才能组合为从S到T的最短路。 在图8.2.1(a)中, 顶点集合划分为S, A1, A2, B1, B2, B3, C1, C2, C3, C4, E1, E2和T。图中每条弧都是由前一个集合中的1个顶点到后一个集合中1个顶点。这种有向图称为多阶段图。 从S到T分为若干个阶段，每个阶段都是前一个顶点集到后一个顶点集。 多阶段过程用

29、多阶段图表示，如图8.2.1（b）所示。,由最后一段开始计算，逐段由后向前计算, 直到出发点S。 最后一段是由E1, E2到T的路，在图8.2.1(b)中处于第6段。令fk(v)表示第k段中顶点v到T的最短距离。有f6(E1)=6, f6(E2)=7, 并在顶点E1上标“d”， 顶点E2上标“r”。 在第6段上，顶点D1和D3到T只有1条路，d5(D3)=12。分别标上“d”和“r”。从D2出发则有两种选择。从两条路中选择短的一条:f5(D2) =mind(D2, E1)+f6(E1), d(D2, E2)+f6(E2) =min4+6, 5+7=10,选择E1，在顶点D2上标“r”。D2E1

30、T2是从D2到T的最短路。在第4段上, C1和C2到T只有一条路，f4(C1)=14，在C1上标“d”。f4(C4)=15，在C4上标“r”。从C2出发则有两种选择，从中选择最短的路:,f4(C2) =mind(C2, D1)+f5(D1), d(C2, D2)+f5(D2) =min3+13, 5+10=15,选择D2，在顶点C2上标“d”，C2D2E1T是从C2到T的最短路。从C3出发也有两种选择， 从中选择最短的一条:,f4(C3) =mind(C3, D2)+f5(D2), d(C3, D3)+f5(D3) =min6+10, 5+10=15,选择D3，在顶点C3上标“d”，C3 D3

31、 E2T是从C3到T的最短路。 用同样的方法继续求第3段, 第2段, 第1段各顶点到T的最短路， 所得结论如下：f3(B1)=18, 顶点B1标“d”; f3(B2)=17，顶点B2标“d”; f3(B3)=19，顶点B3标“d”; f2(A1)=19，顶点A1标“d”; f2(A2)=21，顶点A2标“r”; f1(S)=21，顶点S标“r”。从S到T的最短路长度是21。 沿各顶点上的标号指出的方向走，SA1B2C3D3E2T是一条最短路。,由上述求解过程可见，fk和fk+1满足递推关系式:,上例中，k=5, 4, 3, 2, 1。hk(v)是第k阶段中所作的下一个顶点的选择。 称上式为函数

32、方程。 函数方程是根据动态规划的最优原理得出的。 动态规划的最优化原理， 作为整个过程的最优化策略具有性质： 对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。,对于最短路问题，假定l=v1v2vk是从v1到vk的最短路，开始于顶点v1，多了一个决策之后到顶点v2。现在的状态由顶点v2决定。l=v2v3vk应是一条从v2到vk的最短路， 因此，对于最短路问题， 最优原理成立。 使用动态规划求解多阶段决策问题时，首先要求对于该问题最优化原理成立， 然后列出函数方程，从后向前逐步计算，最后求出整个问题的最优解。,例2(投资分配问题) 假设有4万元资金，准备给4种产品投资。设第i种产品的投

33、资数为xi，年利润为fi(xi), i=1, 2, 3, 4, 如表8.2.1所示。 问如何将4万元投资给这4种产品使年利润综合最大？（以万元为单位),表8.2.1 资 金 分 配 表,解 首先投资分配问题可以化成下列数学问题： 约束条件：x1+x2+x3+x4=4 目标函数：z=f1(x1)+f2(x2)+f3(x3)+f4(x4) 使得目标函数z取最大值，其中xi为非负整数，i=1, 2, 3, 4。 设Fk(x)是x（万元）投资在前k个产品后所得的最大的年利润。显然F1(x)=f1(x)。 设xi(x)是取得最大年利润的第I个产品的投资数。F2(x)是x投资到第1, 2两个产品上所得的最

34、大年利润。投资在第2个产品上的资金是x2，则投资在第1个产品上的资金是x-x2，所以,同理可得,从F1(x)=f1(x)开始，逐步地求F2(x), F3(x), F4(x)。Fk(x)(k=1, 2, 3, 4)都是（部分）问题的最优解。对于投资问题，最优策略是确定对每个产品的投资，使4个产品的年利润之和最大。假如对4个产品的投资是x，第4个产品的投资是x4，还剩下x-x4要对其余3个产品投资。 若对3个产品分配的投资不能取得年利润最大值， 则这样对4个产品的投资也一定不是最优策略。所以只要求出部分问题的最优解， 就可将其组合成整个问题的最优解。,当x=1时，由 ， 有 x2=1, x1=x-

35、x2=0, f2(1)+f1(0)=0+0=0 x2=0, x1=x-x2 =1, f2(0)+ f1(0)=0+9=9 就取F2(1)=max0, 9)=9，相应于x1=1, x2=0。继续求F2(2), F2(3), F2(4)。然后求F3(x)和F4(x)。F1(x), F2(x), F3(x), F4(x)以及x1(x), x2(x), x3(x), x4(x)的值如表8.2.2所示。,表 8.2.2 Fi(x)和xi(x)值,从表8.2.2查得F4(4)=23，即4（万元）投资给4个产品， 年利润最大值是23（万元）。 相应地，x4(4)=1，可知第4个产品的投资为1万元，3（万元）

36、投资给了前3个产品，查表知F3(3)=13， 相应地，x3(3)=0, 2。即取最大的利润有以下两种方案。 （1） 在第3个产品上不投资，3（万元）投资在前2个产品上， 查表得F2(3)=13，相应地，x2(3)=2，第2个产品得到2（万元）投资。故知第1个产品得到1（万元）投资，因此有解(x1=1, x2=2, x3=0, x4=1)。,（2） 在第3个产品上投资2（万元）， 1（万元）投资在前两个产品中，查表得F2(1)=9，相应地，x2(1)=0，在第2个产品上不投资， 即第1个产品上投资1（万元）。因此，有解（x1=1,x2=0, x3=2, x4=1）。 现讨论对投资问题动态规划算法

37、的复杂性。 设有m（万元）对n个产品投资,xk取值：0, 1, 2, , x-1, x,此求Fk(x)需要作x+1次加法和x次比较。由于x取1至m，因此需要,次加法以及,次乘法。因k取1至n，因此求Fk(x)的所有值需要O(m2n)次运算。,8.3 试探（启发式）算法,对求最优解的问题，有些问题的求最优解算法是有效的。 但是，对有些问题，目前已知的求最优解算法的时间复杂性是指数的。 由于需要太长的时间, 以至在实际中无法使用。人们发现试探算法（Heuristic Algorithm），对有些问题也能得到最优解, 这一点在直观上似乎是明显的。但是，由于试探算法并不一定得到最优解，自然提出两个问题

38、： (1) 试探算法在什么条件下得到最优解？,(2) 若试探算法不能够得到最优解， 最大的相对误差是多少？希望得到充要条件以保证算法求得最优解。 在不能得到最优解时， 若一个试探算法对问题的大部分实例求解所需时间比较合适， 并且最大相对误差也在一定范围内， 则人们还是比较愿意用试探算法。 在试探算法中，贪心（Greedy）算法往往被列于首位。 这里把试探算法作为设计算法的技术进行讨论，在NP完全问题的近似算法中还可见到试探算法。,日常生活中，有的小孩吃东西总挑大个的，有的家长要求子女啥话都要听，有些独裁领导要求职工什么事情都要按他的意图办，有些人见啥便宜就想沾。 这些都属于贪心行为，其结果姑且

39、不论。在数学中也有依照一种最优度量法则每步都取局部最优最后求得解的方法，该法对某些问题也能取得最优解。 例如求连通无向图的最小生成树，但有些问题不能求得最优解。 设vs到v1, v2距离分别是1, 50, v1, v2到vt的距离分别是100, 50, v1到 v2的距离是200，求从vs到vt的最短路。按照贪心算法的思路， 先选定距离vs最近的顶点v1 ，然后再到vt，所得的一条路长101。 但从vs经v2到vt是一条更短的路。每次选一个最邻近的顶点不一定能够求得最短路。尽管如此，贪心算法仍不失为一种常用的试探算法。,例1(背包问题) 规定背包内物件的重量不超过b。有n类物件a1, a2,

40、, an，物件ai的重量与价值分别是wi, vi。背包问题如前所述，这里允许物件可部分放入，并设第i类物件放入背包， 部分占整个物件的比例为xi，则这种背包问题的数学描述为 约束条件：,目标函数：,求解(x1, x2, , xn)，使z取最大（0 xi1, vi, wi0）。显然， 当 时，则（1, 1, , 1）是最优解；当 时， xi不能全部为1。 对于具体例子，(v1, v2, v3)=(50, 48, 30), (w1, w2, w3)=(36, 30, 20), b=40，有以下四个可行解:,使用贪心算法首先要确定按照哪个量排序。对于背包问题有3种排序的方法： （1）依照物件的价值排

41、序。由于(v1,v2,v3)=(50,48,30)，先把第1个物件放入背包内，x1=1,w1b，b-w1=4，取x2=4/30=2/15，得到可行解(x1, x2,x3)=(1,2/15,0)， 装入背包物件价值56.4，不是最优解。 （2） 依物件重量轻者优先， 得解（0, 2/3, 1）。 装入背包物件价值为62， 仍非最优解。,（3） 依照vi/wi的大小把物件进行排序，v1/w1=50/36=1.39， v2/w2=48/30=1.6，v3/w3=30/20=1.5。物件的次序应排为2, 3, 1 。即先取第2个物件，x2=1，b-w2=40-30=10，再取x3=1/2，得到一个可行

42、解（0, 1, 1/2）， 。 以下证明（0，1，1/2）是最优解。 为了方便起见，设有n个物件，它们的次序已经满足下列不等式:,使用贪心算法，按照1, 2, , n次序把物件放入背包内。 若全部n个物件都能够放入，当然是最优解。若第j个物件放不下整个，只能部分放入背包。背包的重量刚达到b， 以后的物件不再考虑。设X=(x1, x2, , xn)是由贪心算法得到的解。 若所有的xi都等于1，这是最优解。否则，设j是xi1的最小下标，有xi=1, ij; xi=0, jin。,若X不是最优解，则必存在另一可行解Y=(y1, y2, , ym)，使得viyivixi。不失一般性，假设wiyi=b,

43、 k是使xiyi的最小下标。因为XY，这样的k一定存在。往证yk xk ， 也有yjxj,这与Y是可行解矛盾。,（3） 若kj， 则,现在把yk增加到xk，同时减少yk+1, , yn中的一些值，得到新的可行解Z=(z1, z2, , zn)， zi=xi, 1ik因背包内的物件重量仍为b， 有,且有,因Y是最优解， 且有,故Z也是最优解。但Z比Y多1个与X相同的分量。继续上述过程， 可推出X是最优解。 一般情况得证。上例（0, 1, 1/2）是最优解。,例2(Huffman最优树) 设T是一棵有t片树叶的二叉树，分配给树叶的权分别是w1, w2, , wt。设l(wi)是权为wi的树叶到根的

44、路长。定义树T的权,在树叶的权为w1, w2, , wt的所有二叉树中，权最小的一个二叉树称为最优二叉树。 例如给定权5, 6, 7, 8， 图8.3.1（a）是最优二叉树， 图8.3.1（b）不是最优二叉树。,图 8.3.1 两种二叉树的比较,Huffman提出了一个求最优二叉树的方法，并且这个方法可推广到求最优6元树上。设有t个权w1, w2, , wt。先把权按照从小到大次序排好。不妨假设w1 w2 w3 wt 先构造t个顶点， 每一个顶点是树，分别带权w1, w2 , , wt 。其中找出2个最小的权w1, w2 ，构造一棵二叉树，它的权为w1+w2。现有t-1棵二叉树， 权分别为w1

45、 + w2, w3, , wt 。再在这t-1 棵二叉树中找出2棵权最小的二叉树， 合并成 1 棵二叉树， 权为原2棵树权的和。原来的2棵二叉树成了合并后树的左子树、 右子树。 在每一步上选择2棵权最小的二叉树，合并成 1 棵二叉树， 权是原来2个权的和， 该过程进行到 1 棵二叉树为止。 若把权小的看成优， 由于每步都择优选取， 这样的方法属于贪心算法。,图 8.3.2 最优二叉树,假设w1 + w2, w3, w4, w5, w6分别是2, 3, 5, 7, 9, 11。使用Huffman方法的过程如下所示:,2 3 5 7 9 11 5 5 7 9 11 10 7 9 11 10 16

46、11 16 21 37,数字下带一划指出最小的权。 所得的最优二叉树如图8.3.2所示。,现在用数学归纳法证明Huffman方法求得的二叉树是最优二叉树。 设t=2，有两个权w1和w2，树叶上权分别为w1 、 w2 ，树高为1的二叉树是最优树。 根到树叶的路长为1。,归纳假设：有k个权，kt，用Huffman方法求得的二叉树是有k个权的最优二叉树。 现设有t个权，w1w2wt。设T是用Huffman方法求得的一棵二叉树，用W(T)表示该二叉树的权。设T1是树叶上带权w1, w2, , wt的一棵最优二叉树。要证明W(T) =W(T1)，从而，T也是一棵最优二叉树。,在二叉树T1中，设v0是离树

47、根最远的分支点。v0有两个儿子顶点（树叶）va和vb，若它们的权不是w1和w2， 就把这两片树叶与带权w1和w2的树叶交换。这样交换后，由于va和vb是长度最大的树叶，而w1和w2是最小的权，因而不会增加树的权。所得的二叉树依然是最优二叉树。该树记为T2，有W(T2)=W(T1)。在T2中删除v0的两个儿子节点va和vb ，v0成为一片树叶，带权w1 + w2 ， 新得到的二叉树记为T2 ，是带权w1 + w2, w3, , wt的最优二叉树。,用Huffman方法求w1 + w2, w3, , wt 的二叉树。 由归纳假设， 可以得到最优的二叉树T，在T中，把带权的w1 + w2的树叶改成分

48、支点，生成两个带w1和w2儿子的顶点（树叶）。这样的二叉树就是树T。有W(T)=W(T)+ w1 + w2 。由于T和T2都是最优二叉树，因而W(T2)=W(T)，故有,因此，T是一棵最优二叉树。,8.4 作业安排问题,本节中考虑在n个相同处理器的计算机系统上执行一批作业的安排问题。设P1, P2, , Pn是n个相同的处理器。设J=T1, T2, , Tm是作业的集合。有以下假设： （1） 一个作业可以在任一台处理器上执行。作业一旦在一台处理器上开始执行，直到作业完成，中间不得中断。 （2）在J上有一偏序关系 ，Ti Tj当且仅当作业Ti执行完毕后才能执行Tj。偏序集合用Hasse图表示，顶

49、点代表作业，圆圈旁注作业名， 圆圈内数字表示完成作业的时间。,（3）一旦有一台处理器空闲，并且有一个作业需要执行， 作业应在处理器上立即执行。用t(Ti)表示完成作业Ti的时间，1, 2, 表示处理器空闲时期，T(i)表示空闲时期i的时间。一台处理器有时因为没有可以执行的作业而处于空闲， 也可故意让它空闲。若让所有的处理器同时都空闲，这只能延长完成m个作业的时间。但有时故意让某些处理器空闲待命反而使完成全部作业的时间提前。由w表示完成全部作业的时间。,例1 由偏序图8.4.1（a）可知，系统只有完成了作业T1和T2后，才能执行T4和T5。也只有在完成了T4和T5之后才能执行T6。 在图8.4.

50、1（b）中，当t=9时，虽然可以执行T3，但P2在9与10之间故意空闲1个单位，这样整个完成时间w=24。在图8.4.1（c）中, P2没有故意空闲，在完成了T2后，因T1还没有完成，只能执行T3， 结果完成时间w=29。,图 8.4.1 例1图,例2 设有3台处理器p1, p2, p3，有9个作业T1, T2, , T9 。完成作业时间写在相应的圆圈内。执行先后的偏序关系如图8.4.2（a）所示。 一种安排如图8.4.2（b）所示。 完成时间是12。 若处理器数目由3增加到4， 其余条件不变， 完成时间反而增加到15， 如图8.4.3所示。 若减少先后次序的约束，也可能增加完成时间。如对图8