第7章 贪心法

1、2021-8-13算法设计与分析-贪心法1 第第7章章 贪心法贪心法 分治法是把一个复杂的分治法是把一个复杂的 问题分解为若干个相互独问题分解为若干个相互独 立的子问题，通过求解子问题并将子问题的解合并立的子问题，通过求解子问题并将子问题的解合并 得到原问题的解；得到原问题的解； 动态规划方法是把一个复杂问题分解为若干相互重动态规划方法是把一个复杂问题分解为若干相互重 叠的子问题，通过求解子问题形成的一系列决策得叠的子问题，通过求解子问题形成的一系列决策得 到原问题的解；到原问题的解； 贪心法是把一个复杂问题分解为一系列较为简单贪心法是把一个复杂问题分解为一系列较为简单 的局部最优选择，每一步

2、选择都是对当前解的一的局部最优选择，每一步选择都是对当前解的一 个扩展，直到获得问题的完整解。个扩展，直到获得问题的完整解。 2021-8-13算法设计与分析-贪心法2 第第7章章 贪心法贪心法 7.1 概概 述述 7.2 图问题中的贪心法图问题中的贪心法 7.3 组合问题中的贪心法组合问题中的贪心法 2021-8-13算法设计与分析-贪心法3 7.1 概概 述述 7.1.1 贪心法的设计思想贪心法的设计思想 7.1.2 例子：埃及分数例子：埃及分数 2021-8-13算法设计与分析-贪心法4 贪心法只根据当前已有的信息就做出选择，而贪心法只根据当前已有的信息就做出选择，而 且一旦做出了选择，

3、不管将来有什么结果，这个选且一旦做出了选择，不管将来有什么结果，这个选 择都不会改变。择都不会改变。 7.1.1 贪心法的设计思想贪心法的设计思想 换言之，贪心法并不是从整体最优考虑，它所换言之，贪心法并不是从整体最优考虑，它所 做出的选择只是在某种意义上的局部最优。做出的选择只是在某种意义上的局部最优。 这种局部最优选择并不总能获得整体最优解这种局部最优选择并不总能获得整体最优解 （Optimal Solution），但通常能获得近似最优解），但通常能获得近似最优解 （Near-Optimal Solution）。）。 2021-8-13算法设计与分析-贪心法5 例：用贪心法求解付款问题。例

4、：用贪心法求解付款问题。 假设有面值为假设有面值为5元、元、2元、元、1元、元、5角、角、2角、角、1角角 的货币，需要找给顾客的货币，需要找给顾客4元元6角现金，如何使付出的角现金，如何使付出的 货币的数量最少货币的数量最少? 面值改为面值改为3元、元、1元、元、8角、角、5角、角、1角的货币如角的货币如 何何? 贪心法求解贪心法求解: 2元，元，2元，元，5角，角，1角，总共付出角，总共付出4 张货币。张货币。 此时最优解此时最优解3张货币：张货币：1张张3元和元和2个个8角。角。 2021-8-13算法设计与分析-贪心法6 在付款问题每一步的贪心选择中，只选择面在付款问题每一步的贪心选择

5、中，只选择面 值最大的货币，而不去考虑在后面看来这种选择值最大的货币，而不去考虑在后面看来这种选择 是否合理。是否合理。 付款问题的贪心选择策略是尽可能使付出的付款问题的贪心选择策略是尽可能使付出的 货币最快地满足支付要求，其目的是使付出的货货币最快地满足支付要求，其目的是使付出的货 币张数最慢地增加，这正体现了贪心法的设计思币张数最慢地增加，这正体现了贪心法的设计思 想。想。 2021-8-13算法设计与分析-贪心法7 贪心法求解的问题的特征：贪心法求解的问题的特征： v 动态规划法通常以自底向上的方式求解各个子问动态规划法通常以自底向上的方式求解各个子问 题，而贪心法则通常以自顶向下的方式

6、做出一系列题，而贪心法则通常以自顶向下的方式做出一系列 的贪心选择。的贪心选择。 （1）最优子结构性质最优子结构性质 当一个问题的最优解包含其子问题的最优解时，当一个问题的最优解包含其子问题的最优解时， 称此问题具有最优子结构性质，也称此问题满足最称此问题具有最优子结构性质，也称此问题满足最 优性原理。优性原理。 （2）贪心选择性质贪心选择性质 所谓贪心选择性质是指问题的整体最优解可以所谓贪心选择性质是指问题的整体最优解可以 通过一系列局部最优的选择，即贪心选择来得到。通过一系列局部最优的选择，即贪心选择来得到。 2021-8-13算法设计与分析-贪心法8 动态规划方法求解付款问题：动态规划方

7、法求解付款问题： （1）设有）设有n种不同面值的货币，面值存于数组种不同面值的货币，面值存于数组Tn 中，且中，且0T1T2.Tn ； （2）当只用面值）当只用面值T1i的货币时，可找出钱数的货币时，可找出钱数j的的 最少货币张数记为最少货币张数记为ci,j。 该问题具有最优子结构性质该问题具有最优子结构性质。 2021-8-13算法设计与分析-贪心法9 v 计算计算ci,j的递归表达式如下：的递归表达式如下： *, 1min, /0 iTkjickjic iTjk v 初始条件为初始条件为ci,0=0, i=1,n 0 1 mod 1 0 1 mod , 1 TjTdivj Tj jc 20

8、21-8-13算法设计与分析-贪心法10 7.1.2 例例-埃及分数埃及分数 问题问题：埃及分数问题埃及分数问题把一个真分数表示为最少的埃把一个真分数表示为最少的埃 及分数之和，所谓埃及分数是分子为及分数之和，所谓埃及分数是分子为1的分数。的分数。 例例 7/8=1/2+1/3+1/24=1/8+1/8+1/8+1/8+1/8+1/8+1/8 一个真分数的埃及分数表示不是唯一的。一个真分数的埃及分数表示不是唯一的。 贪心策略选择真分数包含的最大埃及分数。贪心策略选择真分数包含的最大埃及分数。 如何找到真分数包含的最大埃及分数？如何找到真分数包含的最大埃及分数？ 2021-8-13算法设计与分析

9、-贪心法11 7.2 图问题中的贪心法图问题中的贪心法 7.2.1 TSP问题问题 7.2.2 图着色问题图着色问题 7.2.3 最小生成树问题最小生成树问题 2021-8-13算法设计与分析-贪心法12 7.2.1 TSP问题问题 求解求解TSP问题至少有两种贪心策略是合理的：问题至少有两种贪心策略是合理的： （1）最近邻点最近邻点策略：从任意城市出发，每次在策略：从任意城市出发，每次在 没有到过的城市中选择最近的一个，直到经过没有到过的城市中选择最近的一个，直到经过 了所有的城市，最后回到出发城市。了所有的城市，最后回到出发城市。 2021-8-13算法设计与分析-贪心法13 (d) 城市

10、城市3城市城市5 (e) 城市城市5城市城市2 (f) 城市城市2城市城市1 最近邻点贪心策略求解最近邻点贪心策略求解TSP问题的过程问题的过程 2 5 2 2 1 5 43 2 2 5 2 2 1 5 43 2 3 2 5 2 2 1 5 43 2 7 3 6 32 1 5 4 3 2 2 3 3 2 1 5 43 2 C= 3 3 2 6 3 7 3 2 3 7 2 5 2 3 2 3 6 2 5 3 (a) 5城市的代价矩阵城市的代价矩阵 (b) 城市城市1城市城市4 (c) 城市城市4城市城市3 2021-8-13算法设计与分析-贪心法14 算法算法7.2最近邻点策略求解最近邻点策略求

11、解TSP问题问题 1 P= ; 2 V=V- -u0; u=u0; /从顶点从顶点u0出发出发 3 循环直到集合循环直到集合P中包含中包含n- -1条边条边 3.1 查找与顶点查找与顶点u邻接的最小代价边邻接的最小代价边(u, v)并且并且v属于集合属于集合V； 3.2 P=P+(u, v); 3.3 V=V- -v; 3.4 u=v; /从顶点从顶点v出发继续求解出发继续求解 设图设图G有有n个顶点，边上的代价存储在二维数组个顶点，边上的代价存储在二维数组 wnn中，集合中，集合V存储图的顶点，集合存储图的顶点，集合P存储经过存储经过 的边，最近邻点策略求解的边，最近邻点策略求解TSP问题的

12、算法如下：问题的算法如下： 2021-8-13算法设计与分析-贪心法15 算法算法7.1的时间性能为的时间性能为O(n2)，因为共进行，因为共进行n-1次贪心选次贪心选 择，每一次选择都需要查找满足贪心条件的最短边。择，每一次选择都需要查找满足贪心条件的最短边。 用最近邻点贪心策略求解用最近邻点贪心策略求解TSP问题所得的结果不一定问题所得的结果不一定 是最优解，图是最优解，图7.1(a)中从城市中从城市1出发的最优解是出发的最优解是1254 31，总代价只有，总代价只有13。 当图中顶点个数较多并且各边的代价值分布比较均匀当图中顶点个数较多并且各边的代价值分布比较均匀 时，最近邻点策略可以给

13、出较好的近似解，不过，这个近时，最近邻点策略可以给出较好的近似解，不过，这个近 似解以何种程度近似于最似解以何种程度近似于最优解，却难以保证。例如，在图优解，却难以保证。例如，在图 7.1中，如果增大边中，如果增大边(2, 1)的代价，则总代价只好随之增加，的代价，则总代价只好随之增加， 没有选择的余地。没有选择的余地。 2021-8-13算法设计与分析-贪心法16 （2）最短链接最短链接策略：每次在整个图的范围内选择策略：每次在整个图的范围内选择 最短边加入到解集合中，但是，要保证加入解集合最短边加入到解集合中，但是，要保证加入解集合 中的边最终形成一个哈密顿回路。中的边最终形成一个哈密顿回

14、路。 因此，当从剩余边集因此，当从剩余边集E中选择一条边中选择一条边(u, v)加入解集加入解集 合合S中，应满足以下条件：中，应满足以下条件： 边边(u, v)是边集是边集E中代价最小的边；中代价最小的边； 边边(u, v)加入解集合加入解集合S后，后，S中不产生回路；中不产生回路； 边边(u, v) 加入解集合加入解集合S后，后，S中不产生分枝；中不产生分枝； 2021-8-13算法设计与分析-贪心法17 2 1 5 43 2 2 1 5 43 2 C= 3 3 2 6 3 7 3 2 3 7 2 5 2 3 2 3 6 2 5 3 (a) 5城市的代价矩阵城市的代价矩阵 (b) 城市城市

15、1城市城市4 (c) 城市城市5城市城市2 2 (d) 城市城市4城市城市3 (e) 城市城市3城市城市5 (f) 城市城市2回到出发城市回到出发城市1 最短链接贪心策略求解最短链接贪心策略求解TSP问题的过程问题的过程 2 2 2 1 5 43 2 2 2 2 1 5 43 2 2 2 2 1 5 43 2 5 3 5 2021-8-13算法设计与分析-贪心法18 算法算法7.3最短链接策略求解最短链接策略求解TSP问题问题 1P= ; 2E=E; /候选集合，初始时为图中所有边候选集合，初始时为图中所有边 3循环直到集合循环直到集合P中包含中包含n- -1条边条边 3.1 在在E中选取最短

16、边中选取最短边(u, v); 3.2 E=E- -(u, v); 3.3 如果如果 (顶点顶点u和和v在在P中不连通中不连通 and 不产生分枝不产生分枝) 则则P=P+(u, v); 设图设图G有有n个顶点，边上的代价存储在二维数组个顶点，边上的代价存储在二维数组wnn中，中， 集合集合E是候选集合即存储所有未选取的边，集合是候选集合即存储所有未选取的边，集合P存储经过的存储经过的 边，最短链接策略求解边，最短链接策略求解TSP问题的算法如下：问题的算法如下： 2021-8-13算法设计与分析-贪心法19 在算法在算法7.2中，如果操作中，如果操作“在在E中选取最短边中选取最短边 (u, v

17、)”用顺序查找，则算法用顺序查找，则算法7.2的时间性能是的时间性能是 O(n2)。 如果采用堆排序的方法将集合如果采用堆排序的方法将集合E中的边建立中的边建立 堆，则选取最短边的操作可以是堆，则选取最短边的操作可以是O(log2n)，对于，对于 两个顶点是否连通以及是否会产生分枝，可以用两个顶点是否连通以及是否会产生分枝，可以用 并查集的操作将其时间性能提高到并查集的操作将其时间性能提高到O(n)，此时算，此时算 法法7.2的时间性能为的时间性能为O(nlog2n)。 2021-8-13算法设计与分析-贪心法20 7.2.2 图着色问题图着色问题 给定无向连通图给定无向连通图G=(V, E)

18、，求图，求图G的最小色数的最小色数k， 使得用使得用k种颜色对种颜色对G中的顶点着色，可使任意两个相中的顶点着色，可使任意两个相 邻顶点着色不同。邻顶点着色不同。 2021-8-13算法设计与分析-贪心法21 12 3 4 5 下图可以只用两种颜色着色，将顶点下图可以只用两种颜色着色，将顶点1、3和和4着着 成一种颜色，将顶点成一种颜色，将顶点2和顶点和顶点5着成另外一种颜色。着成另外一种颜色。 2021-8-13算法设计与分析-贪心法22 贪心策略：选择一种颜色，以任意顶点作为开始贪心策略：选择一种颜色，以任意顶点作为开始 顶点，依次考察图中的未被着色的每个顶点，如果顶点，依次考察图中的未被

19、着色的每个顶点，如果 一个顶点可以用颜色一个顶点可以用颜色1着色，换言之，该顶点的邻接着色，换言之，该顶点的邻接 点都还未被着色，则用颜色点都还未被着色，则用颜色1为该顶点着色。为该顶点着色。 当没有顶点能以这种颜色着色时，选择颜色当没有顶点能以这种颜色着色时，选择颜色2和和 一个未被着色的顶点作为开始顶点，用第二种颜色一个未被着色的顶点作为开始顶点，用第二种颜色 为尽可能多的顶点着色，如果还有未着色的顶点，为尽可能多的顶点着色，如果还有未着色的顶点， 则选取颜色则选取颜色3并为尽可能多的顶点着色，依此类推。并为尽可能多的顶点着色，依此类推。 2021-8-13算法设计与分析-贪心法23 3

20、4 5 121 2 3 4 5 顶点顺序顶点顺序1,2,3,4,5顶点顺序顶点顺序1,5, 2,3,4 2021-8-13算法设计与分析-贪心法24 算法算法7.4图着色问题图着色问题 1color1=1; /顶点顶点1着颜色着颜色1 2for (i=2; i=n; i+) /其他所有顶点置未着色状态其他所有顶点置未着色状态 colori=0; 3k=0; 4循环直到所有顶点均着色循环直到所有顶点均着色 4.1 k+; /取下一个颜色取下一个颜色 4.2 for (i=2; iC) 4.1 xi=1; /将第将第i个物品放入背包个物品放入背包 4.2 C=C-wi; 4.3 i+; 5. xi

21、=C/wi; 算法算法7.7的的C+语言描述见教材语言描述见教材P140。 时间复杂性为时间复杂性为O(nlog2n)。 2021-8-13算法设计与分析-贪心法41 7.3.2 活动安排问题活动安排问题 问题问题:设有设有n个活动的集合个活动的集合E=1, 2, , n，其中每个活，其中每个活 动都要求使用同一资源，而在同一时间内只有一个活动都要求使用同一资源，而在同一时间内只有一个活 动能使用这一资源。每个活动动能使用这一资源。每个活动i都有一个起始时间都有一个起始时间si和和 结束时间结束时间fi，且，且si =fj) 则则 4.1.1 B=B+j; 4.1.2 j=i; 4.2 i+;

22、 算法的时间复杂性为算法的时间复杂性为O(nlog2n)。 2021-8-13算法设计与分析-贪心法46 贪心法求解活动安排问题贪心法求解活动安排问题C+描述描述 int ActiveManage(int s , int f , bool a , int n) /各活动的起始时间和结束时间存储于数组各活动的起始时间和结束时间存储于数组s和和f中且中且 /按结束时间的非减序排列按结束时间的非减序排列 a1=1; j=1; count=1; for (i=2; i=fj) ai=1; j=i; count+; else ai=0; return count; 活动安排问题满足贪心选择性质？活动安排

23、问题满足贪心选择性质？ 2021-8-13算法设计与分析-贪心法47 7.3.3 多机调度问题（略）多机调度问题（略） 设有设有n个独立的作业个独立的作业1, 2, , n，由，由m台相台相 同的机器同的机器M1, M2, , Mm进行加工处理，作业进行加工处理，作业i 所需的处理时间为所需的处理时间为ti（1in），每个作业均可在），每个作业均可在 任何一台机器上加工处理，但不可间断、拆分。任何一台机器上加工处理，但不可间断、拆分。 多机调度问题要求给出一种作业调度方案，使所多机调度问题要求给出一种作业调度方案，使所 给的给的n个作业在尽可能短的时间内由个作业在尽可能短的时间内由m台机器加台

24、机器加 工处理完成。工处理完成。 2021-8-13算法设计与分析-贪心法48 贪心法求解多机调度问题的贪心策略是贪心法求解多机调度问题的贪心策略是最长最长 处理时间处理时间作业优先，即把处理时间最长的作业分作业优先，即把处理时间最长的作业分 配给最先空闲的机器，这样可以保证处理时间长配给最先空闲的机器，这样可以保证处理时间长 的作业优先处理，从而在整体上获得尽可能短的的作业优先处理，从而在整体上获得尽可能短的 处理时间。处理时间。 按照最长处理时间作业优先的贪心策略，当按照最长处理时间作业优先的贪心策略，当 mn时，只要将机器时，只要将机器i的的0, ti)时间区间分配给作业时间区间分配给作业i 即可；当即可；当mn时，首先将时，首先将n个作业依其所需的处个作业依其所需的处 理时间从大到小排序，然后