第16章_贪心算法

1、Chapter16 贪心算法贪心算法1Ch16.贪心算法贪心算法 求最优解的问题可看作是通过一系列步骤，每求最优解的问题可看作是通过一系列步骤，每一步有一选择的集合，对于较简单的问题，动态规一步有一选择的集合，对于较简单的问题，动态规划显得过于复杂，可用较简单有效的算法求解之。划显得过于复杂，可用较简单有效的算法求解之。 贪心算法总是在当前步骤上选取最好的方案，贪心算法总是在当前步骤上选取最好的方案，即它是一种局部最优的选择，并希望它导致一个全即它是一种局部最优的选择，并希望它导致一个全局最优，但有时是不可能导致全局最优。局最优，但有时是不可能导致全局最优。 例：求例：求v到到w的一条最短路径

2、，若从的一条最短路径，若从v搜索到邻点搜索到邻点t最短，未必是最短，未必是v到到w最短。最短。 但是，仍有许多问题贪心法将产生全局最优解，如但是，仍有许多问题贪心法将产生全局最优解，如MST，单源最短路径等。，单源最短路径等。216.1 活动选择问题活动选择问题n 多个活动竞争资源的调度问题：尽可能多地选择互不多个活动竞争资源的调度问题：尽可能多地选择互不冲突的活动冲突的活动n 设有设有n个活动个活动S=a1, a2,an，均要使用某资源，均要使用某资源(如教如教室室)，该资源使用方式为独占式，一次只供一个活动，该资源使用方式为独占式，一次只供一个活动使用使用v每个活动每个活动ai发生的时间为

3、发生的时间为si,fi), 0sifi v两活动两活动ai, aj相容（不冲突）是指：相容（不冲突）是指： si,fi), sj,fj)不不重叠，满足重叠，满足si ffj j or or sj ffi i。即：。即：一活动的开始一活动的开始时间大于等于另一活动的完成时间。时间大于等于另一活动的完成时间。v活动选择问题：活动选择问题：选择最多的互不冲突的活动，使选择最多的互不冲突的活动，使相容活动集合最大。即：相容活动集合最大。即：ASS， ，A A中活中活动动互不冲突互不冲突且且|A|A|最大。最大。316.1 活动选择问题活动选择问题n 例例（按完成时间递增序排列）按完成时间递增序排列）v

4、问题的解：问题的解：A1=a3,a9,a11, A2=a1,a4, a8,a11 A3=a2,a4,a9a11v最优解：最优解： A2和和A3 此问题可用迭代方法直接给出贪心算法，但为比较此问题可用迭代方法直接给出贪心算法，但为比较和动态规划之关系，下面先考虑动态规划解法。和动态规划之关系，下面先考虑动态规划解法。4i1234567891011si130535688212fi456789101112131416.1 活动选择问题活动选择问题1、活动选择问题的最优子结构、活动选择问题的最优子结构v子问题空间可描述为：子问题空间可描述为：Sij是是S的子集，它包含那些（可在活动的子集，它包含那些（

5、可在活动ai完成之后开完成之后开始）始）and（可在活动（可在活动aj开始之前完成）的活动开始之前完成）的活动ak。 亦即：亦即：Sij中所有活动中所有活动ak与活动与活动ai、aj相容，不妨称相容，不妨称ai、aj和子集和子集Sij相容，因此相容，因此ak也与所有不迟于也与所有不迟于fi完成的完成的活动以及与所有不早于活动以及与所有不早于sj开始的活动相容。开始的活动相容。Note：Sij中可能有冲突的活动。中可能有冲突的活动。为方便处理，设有两个虚拟的活动为方便处理，设有两个虚拟的活动a0和和an+1，并且假，并且假定定 因此，因此，5:jkkikijsfsfSaS10, 0nsf1,0

6、,1, 0njiSSn16.1 活动选择问题活动选择问题为了更严格定义为了更严格定义i和和j的范围，假定所有活动已按完的范围，假定所有活动已按完成时间的单调增有序：成时间的单调增有序：6式1 .16.1210nnfffff,/ /,01ijijSijSiji jijn 若易于用反证法证明只考虑当。因此的范围是：16.1 活动选择问题活动选择问题v如何分解问题？如何分解问题？ 设子问题设子问题 。若。若Sij的解的解中选择了中选择了ak，使用，使用ak产生产生Sij的两个子问题：的两个子问题：Sij的解显然是的解显然是Sik和和Skj解的并，再加上解的并，再加上ak。 注意注意Sik和和Skj已

7、去掉了那些与已去掉了那些与ak冲突的活动，而这些冲突的活动，而这些活动原来可能在活动原来可能在Sij中。中。7jkkiijkijsfsfSaS,相容的子集，这两子集与均是开始前完成的那些活动完成之后开始，在包括在开始前完成的那些活动完成之后开始，在包括在kijjkkjkiikaSaaSaaS:16.1 活动选择问题活动选择问题v最优子结构最优子结构v用子问题的最优解构造原问题的最优解用子问题的最优解构造原问题的最优解8,ijijkijikkjikkjikkjSAaASSAAAAcutandpaste设的最优解是，则两子问题和的解和也必须是最优的易用反证法证明：因为和是独立的，可用证明的一个最优

8、解整个问题的最优解是式1, 0)2 .16(nkjkikijSAaAA16.1 活动选择问题活动选择问题2、一个递归解、一个递归解 设设Ci,j表示表示Sij的最优解的值，即的最优解的值，即Sij中相容活动最大子中相容活动最大子集的集的size：Ci,j=|Aij|1)2)9ijijijijASAjijiCS,/0,，此时时，当16.2 , , , 1,11,/ /110 , max , , 1ijkijikkjijijikkkjikkjijiji kjSaASSSC i jC i kC k jikjkjiAAaAAASC i jC i kC k jS 当时，假设，则可用和两子问题的最优解来构

9、造的最优解，由式：有选择当当16.1 活动选择问题活动选择问题n作业：作业：Ex16.1-11016.1 活动选择问题活动选择问题3、动态规划到贪心法的转化、动态规划到贪心法的转化 到此可直接写出动态规划解，留作练习到此可直接写出动态规划解，留作练习 可通过下面的定理简化其解，该定理也说明贪心算法可通过下面的定理简化其解，该定理也说明贪心算法的正确性。的正确性。Th16.1 设设Sij是任一非空子问题，是任一非空子问题，am是是Sij中具有最早中具有最早完成时间的活动：完成时间的活动：fm=minfk: ak Sij ，则：，则： 活动活动am必定被包含在必定被包含在Sij的某个最优解中；的某

10、个最优解中；子问题子问题Sim是空集，使是空集，使Smj是唯一可能的非空集是唯一可能的非空集 /选选am的目的的目的1112:21imkimikkmkmkijmijijijijkpfSaSfsfsaaaSaSASAa先证第 部分：假定非空，则，使的完成时间先于且这与是 的最早完成活动矛盾！再证第 部分：设是 的某个最优解，并假设 中的活动已按完成时间单调增排过序，是其中第一个活动。13kmmkmijijkmijkijijmkkijmkijijijijijijijmaaaaaAAaaAaASffaAaaAASAAASa若，则问题已得证，即最优解包含若，则构造子集，只需证也是最优解即可又是 中最早

11、完成的任务，比更早完成中的活动互不冲突，也即是 的一个解亦是 的一个最优解，它包含16.1 活动选择问题活动选择问题u该定理的价值可简化问题的解该定理的价值可简化问题的解v在动态规划求解时，原问题在动态规划求解时，原问题Sij可分解为两个子问题可分解为两个子问题Sik和和Skj求解，且这种分解有求解，且这种分解有j-i-1中可能中可能v定理定理16.1将其简化为：将其简化为： 求求Sij的最优解时只用到一个子问题，另一个子问的最优解时只用到一个子问题，另一个子问题为空；题为空； 只须考虑一种选择：即选只须考虑一种选择：即选Sij中最早完成的活动中最早完成的活动vv该定理带来的另一个好处是：能以

12、自顶向下的方式该定理带来的另一个好处是：能以自顶向下的方式解每一个子问题：解每一个子问题：1416.1 活动选择问题活动选择问题对原问题对原问题S=S0,n+1，选其中最早完成的活动，选其中最早完成的活动am1 S中的活动已按完成时间单调增有序中的活动已按完成时间单调增有序 m1=1。下一子问题应是。下一子问题应是Sm1，n+1/已去掉与已去掉与am1冲突的冲突的活动活动选选Sm1,n+1中最早完成的活动中最早完成的活动am2一般形式，当选择一般形式，当选择ami到解集中之后，需解的子问题变到解集中之后，需解的子问题变为为Smi,n+1 显然，所选活动是按完成时间单调增有序的显然，所选活动是按

13、完成时间单调增有序的(m1m2mi)15221, 11未必为到冲突的活动删除才能得中与须将mSaSnmm16.1 活动选择问题活动选择问题vv贪心选择贪心选择 当某个当某个ami加入解集合后，我们总是在剩余加入解集合后，我们总是在剩余的活动中选择第一个不与的活动中选择第一个不与ami冲突的活动加入解冲突的活动加入解集合，该活动是能够最早完成且与集合，该活动是能够最早完成且与ami相容。相容。 这种选择为剩余活动的调度留下了尽可能这种选择为剩余活动的调度留下了尽可能多的机会。即：留出尽可能多的时间给剩余的多的机会。即：留出尽可能多的时间给剩余的尚未调度的活动，以使解集合中包含的活动最尚未调度的活

14、动，以使解集合中包含的活动最多。多。 每次选一个最早完成并与刚加入解集元素每次选一个最早完成并与刚加入解集元素相容的活动相容的活动1616.1 活动选择问题活动选择问题4、递归的贪心算法、递归的贪心算法v输入：向量输入：向量s和和f，并假定已按，并假定已按f单调增有序单调增有序 子问题子问题Sij的下标的下标v输出：输出：Sij的最优解的最优解v算法：算法：17181121Re( , , )/ /0,11;/ /0()() / /1;/ /,.,1()/ /ijmiiijiijimcursiveActivitySelector s f i jijnmiiawhile mj and sfdoaS

15、mmaaaaaif mj then 求S 的最优解.原问题的解：当时，有 必加入解集将与 冲突的活动去掉，才能得到在中找第 个与 相容的活动,1Re( , );/ /;/ /mimijimmmjjisf aSareturnacursiveActivitySelector s f m jaSelsereturnaa是中的第 个活动， /即在 完成后开始且最早能完成的活动和最优解并开始前能够完成的活动均与 冲突16.1 活动选择问题活动选择问题n 时间时间v若要排序，则时间为若要排序，则时间为v若已排序，则若已排序，则RecursiveActivitySelector(s,f,0,n+1)的时间为

16、的时间为 在所有的调用里，每个活动被检查一次，请注意每次在所有的调用里，每个活动被检查一次，请注意每次循环检查时，活动序号只增加不减少，从循环检查时，活动序号只增加不减少，从RAS(s,f,i,j)调用到调用到RAS(s,f,m,j)时，必有时，必有im。j始终为始终为n+119)lg(nn)(n16.1 活动选择问题活动选择问题5、迭代的贪心算法、迭代的贪心算法 上述递归很接近于尾递归，只是结束前多了一个上述递归很接近于尾递归，只是结束前多了一个Union操作，很易转换为迭代算法：操作，很易转换为迭代算法： j始终不变，始终不变，j=n+1当一个活动当一个活动ai加入解集合之后，我们只要从加

17、入解集合之后，我们只要从ai依次往后找到第一个不与依次往后找到第一个不与ai冲突的活动冲突的活动am，由，由于活动事先按完成时间单调增有序，故于活动事先按完成时间单调增有序，故am是最是最早完成且与早完成且与ai相容的活动，它也是相容的活动，它也是Sij中的第一中的第一个活动个活动20211,1( ,)/ / ; ;/ /1;/ /2/ /()/ /,;/ /;/ /ii nmimmimmiGreedyActivitySelector S ffnlength sAaAiiAaformtondoSaif fsthenim aaAAaaaimi单调增有序为解集合是最近加入解集合 的活动 的下标找中

18、最早完成的活动与 相容是与 相容且完成时间 /最早的活动仍记录最近加入/ /endif;iAareturnA的活动 的下标16.1 活动选择问题活动选择问题 注意，若直接给出迭代算法，一般要证注意，若直接给出迭代算法，一般要证A确实为最优解。确实为最优解。这一点由递归算法得以保证，亦可用归纳法直接证明：这一点由递归算法得以保证，亦可用归纳法直接证明：v 总是存在一个最优解，第一步是贪心的选择，即选择活总是存在一个最优解，第一步是贪心的选择，即选择活动动a1；v 在已做的选择数目上做归纳法证明在已做的选择数目上做归纳法证明 2216.1 活动选择问题活动选择问题 vv 算法要点算法要点vi始终表

19、示最近加入始终表示最近加入A的活动的下标的活动的下标v时间：时间：O(n) /已排序已排序23max:iikkmmimmfAffaAaAsfsAaA活动已按完成时间有序总是当前 中所有活动的最大完成时间： 当加入 时，也大于 中所有活动的完成时间，即与 中所有活动相容.活动选择问题活动选择问题n作业：作业：Ex16.1-32416.2贪心策略要点贪心策略要点 贪心算法是通过做一系列选择来获得最优解，在算贪心算法是通过做一系列选择来获得最优解，在算法里的每一个决策点上，都力图选择最好的方案，这种法里的每一个决策点上，都力图选择最好的方案，这种启发式策略并非总能产生最优解。启发式策略并非总能产生最

20、优解。n 上节介绍的贪心算法的步骤上节介绍的贪心算法的步骤v确定问题的最优子结构确定问题的最优子结构v给出递归解（指递归方程）给出递归解（指递归方程）v证明在递归的每一步，有一个最优的选择是贪心的证明在递归的每一步，有一个最优的选择是贪心的选择，因此做出这种选择是安全的。选择，因此做出这种选择是安全的。v证明除了贪心选择导出的子问题外，其余子问题都证明除了贪心选择导出的子问题外，其余子问题都是空集合是空集合v根据贪心策略写出递归算法根据贪心策略写出递归算法v将递归算法转换为迭代算法将递归算法转换为迭代算法2516.2 贪心策略要点贪心策略要点 上述步骤是以动态规划为基础的。实际上可改进它，重上

21、述步骤是以动态规划为基础的。实际上可改进它，重点关注贪心选择。例如，活动选择问题可改进为（直接点关注贪心选择。例如，活动选择问题可改进为（直接写出递归解）：写出递归解）：v首先定义子问题首先定义子问题Sij，i，j均可变均可变v如果我们总是做贪心选择，则如果我们总是做贪心选择，则n+1不变，可省略，子问题变为：不变，可省略，子问题变为：v证明一个贪心的选择（即选证明一个贪心的选择（即选Si中第一个完成的活动中第一个完成的活动am），和剩余子问题），和剩余子问题Sm（与（与am相容）的最优解结合，相容）的最优解结合，能产生能产生Si的最优解。的最优解。261, niijSS:/ /ikikiiS

22、aSfsSa表示 完成后开始的任务集16.2 贪心策略要点贪心策略要点n 贪心算法的一般设计步骤贪心算法的一般设计步骤v 将优化问题分解为做出一种选择及留下一个将优化问题分解为做出一种选择及留下一个待解的子问题待解的子问题v 证明对于原问题总是存在一个最优解会做出证明对于原问题总是存在一个最优解会做出贪心选择，从而保证贪心选择是安全的贪心选择，从而保证贪心选择是安全的v 验证当做出贪心选择之后，它和剩余的一个验证当做出贪心选择之后，它和剩余的一个子问题的最优解组合在一起，构成了原问题子问题的最优解组合在一起，构成了原问题的最优解的最优解n 没有一个一般的方法告诉我们一个贪心算法是否没有一个一般

23、的方法告诉我们一个贪心算法是否会解决一个特殊的最优问题，但是有两个要素有会解决一个特殊的最优问题，但是有两个要素有助于使用贪心算法：助于使用贪心算法： 贪心选择性质，贪心选择性质， 最优子结构最优子结构2716.2 贪心策略要点贪心策略要点1、贪心选择性质、贪心选择性质v 贪心选择性质：一个全局最优解能够通过局部最贪心选择性质：一个全局最优解能够通过局部最优（贪心）选择达到优（贪心）选择达到v 贪心法总是在当前步骤上选择最优决策，然后解贪心法总是在当前步骤上选择最优决策，然后解由此产生的子问题由此产生的子问题v 贪心选择只依赖了目前所做的选择，但不依赖于贪心选择只依赖了目前所做的选择，但不依赖

24、于将来的选择及子问题的解将来的选择及子问题的解v 自顶向下，每做一次贪心选择，就将子问题变得自顶向下，每做一次贪心选择，就将子问题变得更小更小v 贪心算法一般总存在相应的动态规划解，但贪心贪心算法一般总存在相应的动态规划解，但贪心法的效率更高，原因：法的效率更高，原因： 对输入做预处理对输入做预处理使用合适的数据结构（如优先队列）使用合适的数据结构（如优先队列）2816.2 贪心策略要点贪心策略要点2、最优子结构、最优子结构vv和动态规划一样，该性质也是贪心法的一个关键要素和动态规划一样，该性质也是贪心法的一个关键要素 例如，活动选择问题的动态规划解中：例如，活动选择问题的动态规划解中：vv对

25、贪心算法更直接对贪心算法更直接29的最优解和包含则若的最优解kjikijijkijijSSAAaAS,原问题的最优解贪心选择子问题的最优解通常可使用归纳法证明在每一步上做贪心选择可产生最优解，由此可导出最优子结构16.2 贪心策略要点贪心策略要点3、贪心法与动态规划的比较、贪心法与动态规划的比较v 相同点：两种方法都利用了最优子结构特征相同点：两种方法都利用了最优子结构特征v 易错误处：易错误处： 当贪心算法满足全局最优时，可能我们试图使当贪心算法满足全局最优时，可能我们试图使用动态规划求解，但前者更有效用动态规划求解，但前者更有效 当实事上只有动态规划才能求解时，错误地使当实事上只有动态规划

26、才能求解时，错误地使用了贪心法用了贪心法 为了说明两种技术的细微区别，请看一个古典优化问为了说明两种技术的细微区别，请看一个古典优化问题的两个变种：题的两个变种：背包问题：背包问题：n个物品重个物品重w1,w2,wn,背包可放入重量背包可放入重量W，问能否从，问能否从n件物品中选择若干件放入背包，使重量件物品中选择若干件放入背包，使重量和正好等于和正好等于W。3016.2 贪心策略要点贪心策略要点n 0-1背包问题和零头背包问题背包问题和零头背包问题v 0-1背包：某物品拿与不拿背包：某物品拿与不拿(1,0的选择的选择)v 零头背包：某物品可取部分装包零头背包：某物品可取部分装包想象：小偷偷东

27、西，包容量有限，想尽可能使偷走的想象：小偷偷东西，包容量有限，想尽可能使偷走的东西总价值最大，东西总价值最大，0-1背包偷走的是金条之类物品，背包偷走的是金条之类物品，零头背包偷走的是金粉之类物品。零头背包偷走的是金粉之类物品。31个物品互不相同，可理解为不允许一物品多次装包重量内含有价值最大，且总怎样选物品装包使得包磅（整数）为整数，背包载重量：和磅，重量件物品价值；第物品件数：nWWwvwviniiii$16.2 贪心策略要点贪心策略要点n 两个背包问题都具有最优子结构两个背包问题都具有最优子结构v0-1背包问题背包问题原问题的最优解：设背包中装有重量至多为原问题的最优解：设背包中装有重量

28、至多为W磅的磅的最有价值的若干物品；最有价值的若干物品；子问题的最优解：从原问题的最优解中去掉某物品子问题的最优解：从原问题的最优解中去掉某物品j，则包中剩余物品应是除，则包中剩余物品应是除j外，取自原外，取自原n-1件物品中件物品中最有价值，且总重不超过最有价值，且总重不超过W-wj的若干物品。的若干物品。显然，原问题分解为子问题时，原问题的最优解也显然，原问题分解为子问题时，原问题的最优解也要求子问题的解最优要求子问题的解最优3216.2 贪心策略要点贪心策略要点v零头背包零头背包子问题：从背包中去掉物品子问题：从背包中去掉物品j，重量为，重量为w(该物品该物品剩余剩余wj-w)，则包中剩

29、余物品应是除，则包中剩余物品应是除j之外，取自之外，取自原原n-1件物品以及物品件物品以及物品j的的wj-w部分中最有价值且部分中最有价值且总重至多为总重至多为W-w的若干物品的若干物品显然，原问题解最优亦要求子问题的解最优显然，原问题解最优亦要求子问题的解最优3316.2 贪心策略要点贪心策略要点n 两个背包问题的不同解法两个背包问题的不同解法v0-1背包只能用动态规划求解背包只能用动态规划求解按每磅价值按每磅价值(vi/wi)排序排序贪心选择策略：取单位价值最大者装包，若装不贪心选择策略：取单位价值最大者装包，若装不下，考虑下一单位价值最大的物品，直至包装满下，考虑下一单位价值最大的物品，

30、直至包装满或所有物品都考虑过为止或所有物品都考虑过为止实际上，装入当前每磅价值最大者只能保证当前实际上，装入当前每磅价值最大者只能保证当前最优（局部最优），然而放弃它可能使得后续选最优（局部最优），然而放弃它可能使得后续选择更优。所以在装包前，应将某物品装包的子问择更优。所以在装包前，应将某物品装包的子问题的解和放弃它的子问题的解进行比较，这将导题的解和放弃它的子问题的解进行比较，这将导致许多重叠子问题，这正是动态规划的特点。致许多重叠子问题，这正是动态规划的特点。343516.2 贪心策略要点贪心策略要点v零头背包：可用贪心算法求出最优解零头背包：可用贪心算法求出最优解3616.3 Huff

31、man编码编码n略略3716.4 贪心算法的理论基础贪心算法的理论基础 该理论可用来确定贪心法何时能产生最优解该理论可用来确定贪心法何时能产生最优解，它用到了一种组合结构：，它用到了一种组合结构：matroid（胚）。该（胚）。该结构是结构是Whitney于于1935年在研究矩阵中线性无关年在研究矩阵中线性无关结构时抽象出来的，有结构时抽象出来的，有Korte于于80年代初将该理年代初将该理论发展为贪心算法理论。该理论覆盖了许多贪心论发展为贪心算法理论。该理论覆盖了许多贪心法的应用实例，但并未覆盖所有情况（如活动选法的应用实例，但并未覆盖所有情况（如活动选择问题），但它仍在发展。择问题），但它

32、仍在发展。3816.4.1 胚胚n Def：一个胚是满足下列条件的有序对：一个胚是满足下列条件的有序对M=(S,I)v S是一有穷非空集是一有穷非空集v I是是S的一个非空子集（称为的一个非空子集（称为S的独立子集）的独立子集）簇，使得若簇，使得若BI且且AB，则，则A I。满足此性。满足此性质的质的I是遗传的，即是遗传的，即B独立（指独立（指BI ），则），则B的的子集也独立。注意子集也独立。注意I。 若若AI，BI且且|A|0w(x)0，若权最大的独立子集若权最大的独立子集A不是不是最大独立子集，可将其扩张至最大独立子集，后者最大独立子集，可将其扩张至最大独立子集，后者的权更大，使的权更大

33、，使A的权非最大的权非最大4616.4.2 加权胚上的贪心算法加权胚上的贪心算法v例例47000( ,)( )0( )( )( )0,:( )(1)( )GGGGV EMSTGww eMww eww ewMeEw eMAGMSTpfAw AVww AA ，求连通无向图的问题加权胚中求权最大的独立子集问题。即：求胚的最优子集设 的权函数 定义为边的长度，且加权胚的权定义为：，大于各边的最大长度。在中，故的每个最优子集 是 的一棵是胚的最大独立子集它是一棵生成树，它的权为也是权最大的独立子集( )( )MSTw Aw AAG，最大必有最小，即 是 的一棵16.4.2 加权胚上的贪心算法加权胚上的贪

34、心算法n 加权胚的贪心算法加权胚的贪心算法v适用于任何加权胚求最优子集适用于任何加权胚求最优子集Av贪心之处：尽可能选权值最大的元素扩充到贪心之处：尽可能选权值最大的元素扩充到A4849(,)/ /( , ); ( ) ( ) / / /;Greedy M wMS IwAwS MforxS Mw xdoifAxI MthenAAxxAxreturnA输入胚， 表示正的权函数按权 单调递减对排序每个，按单调递减 ； 扩充 未破坏 的独立性否则放弃50( lg ) ( ( ),( lg( )SnO nnfornAxO f nO nnnf n时间分析：设，排序循环 次，每次检验是否独立，设检查时间为

35、总时间为16.4.2 加权胚上的贪心算法加权胚上的贪心算法16.4.2 加权胚上的贪心算法加权胚上的贪心算法n Greedy算法返回算法返回1个最优子集个最优子集A是独立子集易从是独立子集易从独立开始用归纳法证明独立开始用归纳法证明vLemma16.7 （胚呈现贪心选择性质）（胚呈现贪心选择性质）设设M=(S,I)是加权胚，权函数为是加权胚，权函数为w，且，且S已按权值的已按权值的单调递减有序，设单调递减有序，设x是是S的第一个使的第一个使x独立的元素独立的元素（若这样的（若这样的x存在）。若存在）。若x存在，则存在存在，则存在S的一个最的一个最优子集优子集A包含包含x。（即说明第一步贪心选择

36、正确）。（即说明第一步贪心选择正确）51:(1)(2)pfxBSxBAB若无这样的 存在，则唯一的独立子集是否则，设 为 的任一非空最优子集 若，则令，证毕；16.4.2 加权胚上的贪心算法加权胚上的贪心算法52( )( ) ( )( ) ( )( )xBBAxw Aw BiyBw xw yyByBBSBIyxSSw xw y 若，则可从 构造一个最优子集 ， 使其包含 ，为此需证先证，有 由于 是 的最优子集，故 也是独立子集， 由 的遗传性知亦是独立子集是 的第一个独立子集， 而 中元素已按单调减有序,53) , )( )( )( )( )( )iiAxAAxABAAABAByxyiw A

37、w Bw yw xw BBAx构造集 ，使其包含 且 最优 开始令显然 是独立， 利用交换性质，重复地在 中找新的元素 扩充到 使 独立，直至。于是有： 对某个 成立 由 立即知道： 由 是最优子集即可知 亦是最优子集， 且它包括 。16.4.2 加权胚上的贪心算法加权胚上的贪心算法 下面的引理和推论说明：若一元素开始未被选中，下面的引理和推论说明：若一元素开始未被选中，则此后亦不可能被选中则此后亦不可能被选中vLemma16.8 设设M=(S,I)是任一胚，若是任一胚，若S的一个元素的一个元素x是是S的某个独立子集的某个独立子集A的一个扩张，则的一个扩张，则x亦是亦是的一个的一个扩张扩张54

38、的一个扩张是独立的，它是的遗传性知，由的扩张是:xIIxAAxpf16.4.2 加权胚上的贪心算法加权胚上的贪心算法v推论推论16.9 设设M=(S,I)是任一胚，若是任一胚，若S的一个元素的一个元素x不是不是的扩张，则的扩张，则x也不是也不是S的任何独立子集的任何独立子集A的一个扩张的一个扩张 pf：由引理：由引理16.8易证易证v该推论告诉我们，若一开始某元素没被选中，此后亦该推论告诉我们，若一开始某元素没被选中，此后亦不会选中，保证不会选中，保证Greedy算法开始的正确性算法开始的正确性5516.4.2 加权胚上的贪心算法加权胚上的贪心算法v引理引理16.10（胚具有最优子结构性质）（

39、胚具有最优子结构性质）对于加权胚对于加权胚M=(S,I)，设，设x是是Greedy算法选中的第一个算法选中的第一个元素，找一个包含元素，找一个包含x的权最大的独立子集的剩余问题可的权最大的独立子集的剩余问题可归结为找加权胚归结为找加权胚M=(S,I)的一个权值最大的独立子集的一个权值最大的独立子集，这里：，这里：且且M的权函数是的权函数是M的权函数，但只限于的权函数，但只限于S。我们称。我们称M是是由元素由元素x引起的引起的M的收缩，它是的收缩，它是M的子问题。的子问题。56: , / / : / /SySx yISSxIBSxBxIISx即由 中可扩张至中的元素构成即 是由 的不包含 的独立

40、子集构成57: ( )()(x)() pfAMxIAAxMMAMAAxw Aw AwxAMw AAMAMAMxA若 是的任一包含 的最优子集（即权最大的独立子集），则由 的定义可知： 是的一个独立子集，反之，的任一独立子集产生的一个独立子集：两种情况下，均有包含 的 是中权最大的独立子集，保证了须最大，即是的最优子集，反之亦然即： 是原问题的最优解要求是子问题的最优解；反之，A构成原问题的最优解16.4.2 加权胚上的贪心算法加权胚上的贪心算法vTh16.11 （胚的贪心算法的正确性）（胚的贪心算法的正确性） 若若 M = ( S , I ) 是 权 函 数 为是 权 函 数 为 w 的 加

41、权 胚 ， 则 调 用的 加 权 胚 ， 则 调 用Greedy(M,w)将返回一个最优子集将返回一个最优子集 pf:由推论由推论16.9知，一开始被忽略的元素可以放弃，因知，一开始被忽略的元素可以放弃，因为它们不是为它们不是的扩张意味着此后也不会是任何独立的扩张意味着此后也不会是任何独立子集的扩张。子集的扩张。一旦一个元素一旦一个元素x被选中，引理被选中，引理16.7保证了算法将其保证了算法将其扩充到扩充到A中是正确的，因为存在一个最优子集包含中是正确的，因为存在一个最优子集包含x。5816.4.2 加权胚上的贪心算法加权胚上的贪心算法引理引理16.10蕴含着剩余子问题是在蕴含着剩余子问题是

42、在M中找一最优子中找一最优子集。在集。在Greedy将将A置为置为x之后，剩下的各步骤可之后，剩下的各步骤可解释为是在胚解释为是在胚M中进行的，因为中进行的，因为 B BII ，B在在M中中独立等价于独立等价于Bx在在M中独立。因此，中独立。因此，Greedy的的后续操作将找出后续操作将找出M的一个最优子集（可用归纳的一个最优子集（可用归纳法），法），Greedy的全部操作可以找到的全部操作可以找到M的最优子集的最优子集n 若一应用问题能抽象为加权胚，则一定能用贪心法求若一应用问题能抽象为加权胚，则一定能用贪心法求出其最优解出其最优解5916.5 一个任务调度问题一个任务调度问题n 问题描述问

43、题描述在单处理器上对单位时间任务进行最优调度在单处理器上对单位时间任务进行最优调度v输入输入任务集：任务集：S=a1,a2,an，每个任务在单位时间内，每个任务在单位时间内完成，总时间为完成，总时间为n截止期：截止期： a ai iSS，a ai i的截止期的截止期di为整数，且为整数，且1din，即，即a ai i须在须在di或或di时刻之前完成时刻之前完成权（罚款）：权（罚款）： a ai iSS，ai的权的权wi0，表示，表示ai没有在没有在di或或di之前完成所导致的罚款，但提前完成或按时之前完成所导致的罚款，但提前完成或按时完成的任务没有罚款完成的任务没有罚款v输出：求出输出：求出S

44、的一个调度，使总罚款最小的一个调度，使总罚款最小 显然显然S的任意枚举都是一个调度方案，在总时间的任意枚举都是一个调度方案，在总时间n内肯定完成，内肯定完成，但我们力图使延期完成的任务权值和最小但我们力图使延期完成的任务权值和最小6016.5 一个任务调度问题一个任务调度问题n 将问题抽象为加权胚将问题抽象为加权胚v早任务：在给定的调度中，能按期或提前完成的任早任务：在给定的调度中，能按期或提前完成的任务（即在务（即在deadline之前完成任务）之前完成任务）v迟任务：在给定的调度中，在截止期之后完成的任迟任务：在给定的调度中，在截止期之后完成的任务务v早任务优先形式：将早任务排在迟任务之前

45、的调度早任务优先形式：将早任务排在迟任务之前的调度v任何调度均可安排成早任务优先形式任何调度均可安排成早任务优先形式例：例：ajaj aiaj 迟迟 早早 早早 迟迟交换位置不影响交换位置不影响ai和和aj的早迟特性，即总罚款不变的早迟特性，即总罚款不变6116.5 一个任务调度问题一个任务调度问题v调度的规范形式调度的规范形式 早任务在前、迟任务在后（即先将其按早任务优早任务在前、迟任务在后（即先将其按早任务优先形式调度）；并且将所有早任务按先形式调度）；并且将所有早任务按deadline单单调增次序调度（迟任务可按任意次序调度）。调增次序调度（迟任务可按任意次序调度）。v规范形式的调度不改

46、变任务的早迟特性，因此任规范形式的调度不改变任务的早迟特性，因此任何调度均可安排成该形式而保持总罚款不变何调度均可安排成该形式而保持总罚款不变 例：例：6216.5 一个任务调度问题一个任务调度问题 这里这里s1。在规范形势下，。在规范形势下，ai应和应和aj交换：交换：1.aj交换后，其完成时间由交换后，其完成时间由k+s提前至提前至k，仍是早，仍是早任务任务2.交换前交换前aj是早任务，即是早任务，即k+sdj，由，由djdi知知k+sdj16.5 一个任务调度问题一个任务调度问题v最优调度的规范次序最优调度的规范次序 因为任一调度都有一规范形式，所以最优调度因为任一调度都有一规范形式，所

47、以最优调度也存在规范形式也存在规范形式 在最优调度在最优调度S中找出早任务集中找出早任务集A 将将A中任务按中任务按deadlines递增序排列递增序排列 迟任务集迟任务集S-A可按任意序排列可按任意序排列注意：注意： 因为早任务不导致罚款，迟任务的次序也不因为早任务不导致罚款，迟任务的次序也不改变罚款的多少（权的大小），所以上述安改变罚款的多少（权的大小），所以上述安排不改变最优调度的权值排不改变最优调度的权值6416.5 一个任务调度问题一个任务调度问题v独立任务集独立任务集 若存在一个调度使得任务集若存在一个调度使得任务集A中没有迟任务，则称中没有迟任务，则称A是独立的。是独立的。 下面的引理可判定一给定任务集下面的引理可判定一给定任务集A是否独立，为此是否独立，为此先给出一个定义。先给出一个定义。Def：对：