贪心法专题参考资料

1、目录 算法设计技术 贪心法专题 1 一、贪心法的设计思想 1 例 1 埃及分数 1 例 2 TSP 问题 2 例 3 图着色问题 3 例 4 最小生成树问题 prim 算法 4 例 5 最小生成树问题 Kruskal 算法 5 例 6 背包问题 6 例 7 活动安排问题 7 例 8 多机调度问题 9 算法设计技术贪心法专题 一、贪心法的设计思想 正如其名字一样， 贪心法(greedy method)在解决问题的策略上目光短浅，只根据当前已有的 信息做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。 考虑用贪心法求解 付款问题 (payment problem ) 。假设有面

2、值为 5元、 2元、1元、5角、2角、 1 角的货币，需要找给顾客 4 元 6 角现金，为使付出的货币的数量最少，首先选出1 张面值不超过 4 元 6 角的最大面值的货币，即 2 元，再选出 1 张面值不超过 2 元 6 角的最大面值的货币，即 2 元， 再选出 1 张面值不超过 6角的最大面值的货币，即 5角，再选出 1张面值不超过 1 角的最大面值的 货币，即 1角，总共付出 4 张货币。在付款问题每一步的贪心选择中，在不超过应付款金额的条件 下，只选择面值最大的货币，而不去考虑在后面看来这种选择是否合理，而且它还不会改变决定： 一旦选出了一张货币，就永远选定。付款问题的贪心选择策略是尽可

3、能使付出的货币最快地满足支 付要求，其目的是使付出的货币张数最慢地增加，这正体现了贪心法的设计思想。 上述付款问题应用贪心法得到的是整体最优解，但是如果把面值改为3 元、1元、 8角、5角、 1 角，需要找给顾客 4 元 6 角现金，则找给顾客的是 1 个 3 元、 1 个 1 元、 1 个 5 角和 1 个 1 角共 4 张货币，但最优解却是 3 张货币： 1 个 3 元和 2个 8 角。由于贪心法并不是从整体最优考虑，它所 做出的选择只是在某种意义上的局部最优，这种局部最优选择并不总能获得整体最优解 ( optimal solution )，但通常能获得 近似最优解(near-optima

4、l solution )。如果一个问题的最优解只能用蛮力法 穷举得到，则贪心法不失为寻找问题近似最优解的一个较好办法。 例1 埃及分数 【问题】 埃及同中国一样，也是世界文明古国之一。古埃及人只用分子为1 的分数，在表示一 个真分数时，将其分解为若干个埃及分数之和，例如：7/8表示为1/2 + 1/3 + 1/24。埃及分数问题(Egypt fraction )要求把一个真分数表示为最少的埃及分数之和的形式。 【想法】一个真分数的埃及分数表示不是唯一的， 例如： 7/8又可以表示为 1/8 + 1/8 + 1/8 + 1/8 + 1/8 + 1/8 + 1/8 。显然，把一个真分数表示为最少的

5、埃及分数之和的形式，其贪心策略是选择真分数 包含的最大埃及分数， 以7/8为例，7/8 1/2，则1/2是第一次贪心选择的结果； 7/8 -1/2 = 3/8 1/3 , 则1/3是第二次贪心选择的结果；7/8 -1/2 -1/3 = 1/24，则1/24是第三次贪心选择的结果， 即7/8 = 1/2 + 1/3 + 1/24 。 接下来的问题是：如何找到真分数包含的最大埃及分数？设真分数为A/B , B除以A的整数部 分为C,余数为D，则有下式成立： B = A X C + D 即： B/A = C + D/A 1/(C + 1) 即1/(C + 1)即为真分数A/B包含的最大埃及分数。设E

6、 = C + 1，由于 A/B T/E = (A X E) -B)/(B X E) 则真分数减去最大埃及分数后，得到真分数(A X E) -B)/B X E,该真分数可能存在公因子，需要化 简，可以将分子和分母同时除以最大公约数。 【算法】设函数EgyptFraction实现埃及分数问题，算法用伪代码描述如下： ；算法 7.1 :埃及分数 EgyptFraction: :输入：真分数的分子 A和分母B； : -输出：最少的埃及分数之和： i :1. E = B/A + 1; :2.输出 1/E;: ! ：3. A = A * E -B; B = B * E; j! :4.求A和B的最大公约数

7、R，如果R不为1,则将A和B同时除以R; :5.如果A等于1,则输出1/B，算法结束；否则转步骤1重复执行；： 例2 TSP问题 【问题】TSP问题是指旅行家要旅行 n个城市，要求各个城市经历且仅经历一次然后回到出发 城市，并要求所走的路程最短。 【想法1】TSP问题的贪心策略可以采用最近邻点策略：从任意城市出发，每次在没有到过的 城市中选择最近的一个，直到经过了所有的城市，最后回到出发城市。 如图7.1(a)所示是一个无向图的代价矩阵，从顶点1出发，按照最近邻点的贪心策略，得到的路 径是13t1,总代价是14,求解过程如图 7.1(b)(f)所示。 f OO 3 3 2 6 3 CO 7 3

8、 2 厂 / C= 3 7 CO 2 5 / / 2 3 2 CO 3 / / 6 1 2 5 3 CO J O- (a) 一个无向图的代价矩阵 (b)顶点1t顶点4 (c)顶点 4t顶点3 1 2 (d)顶点3 t顶点5 (e)顶点5t顶点2 (f)顶点2 t顶点1 1 3 2 图7.1最近邻点贪心策略求解 TSP问题的过程 需要说明的是，用最近邻点贪心策略求解TSP问题所得的结果不一定是最优解，例如，图7.1(a) 中从顶点1出发的最优解是1 t2t5t4t3t 1,总代价只有13。当图中顶点个数较多并且各边的代 价分布比较均匀时，最近邻点策略可以给出较好的近似解，不过，这个近似解以何种程

9、度近似于最 优解，却难以保证。例如，在图7.1中，如果增大边(2, 1)的代价，则总代价只好随之增加，没有选 择的余地。 【算法1】设图G中n个顶点的编号为1,2,n, q表示顶点i到顶点j的代价(1 i, j n), 集合V存储图的顶点，集合P存储经过的边，从顶点w出发采用最近邻点策略求解 TSP问题的算法 如下： 算法7.2:最近邻点策略求解 TSP问题 :输入：无向带权图 G=(V, E) .输出：回路长度TSPLe ngth 1. 初始化：P= ; TSPLength = 0; 2. u=w; V=V-w; :3.循环直到集合P中包含n-1条边: |3.1查找与顶点u邻接的最小代价边(

10、u, v)并且v属于集合V;! 3.2 P=P+(u, v); V=V-v; TSPLe ngth = TSPLe ngth + Cuv； |3.3输出经过的路径 u v，u=v，转步骤3继续求解；| 4.输出 TSPLength + Cuw； 例3图着色问题 【问题】给定无向连通图 G=(V, E)，图着色问题(graph coloring problem)求图G的最小色数k, 使得用k种颜色对G中的顶点着色，可使任意两个相邻顶点着不同颜色。例如，图7.3所示的无向 图可以只用两种颜色着色，将顶点 1、3和4着一种颜色，将顶点 2和顶点5着另外一种颜色。 【想法】假定k个颜色的集合为1,2,

11、k。一种显然的贪心策略是选择一种颜色，用该颜色 为尽可能多的顶点着色，具体地，选取颜色 1,依次考察图中的未被着色的每个顶点，如果某顶点 可以用颜色1着色，换言之，该顶点的邻接点都还未被着色，则用颜色1为该顶点着色；再选择颜 色2,依次考察图中的未被着色的每个顶点，如果某顶点着颜色2与其相邻顶点的着色不发生冲突， 则用颜色2为该顶点着色；如果还有未着色的顶点，则选取颜色3并为尽可能多的顶点着色，依此 类推。 需要说明的是，贪心法求解图着色问题得到的不一定是最优解。考虑一个具有2n个顶点的无向 图，顶点的编号从1到2n，当i是奇数时，顶点i与除了顶点i+1之外的其他所有编号为偶数的顶点 邻接，当

12、i是偶数时，顶点i与除了顶点i-1之外的其他所有编号为奇数的顶点邻接，这样的图称为 二部图(bipartite graph)。在二部图中，顶点可以分成两个集合V1 (编号为奇数的顶点集合)和V2 (编号为偶数的顶点集合)，并且每一条边都连接 V1中的一个顶点和 V2中的一个顶点。图 7.4 所示 就是一个具有8个顶点的二部图。 图7.4具有8个顶点的二部图 显然，二部图只用两种颜色就可以完成着色，例如，可以将奇数顶点全部着成颜色1将偶数 顶点全部着成颜色 2。如果贪心法以1,3,2n-1,2, 4,2n的顺序为二部图着色，则算法可以得 到这个最优解，但是如果贪心法以1,2,n的自然顺序为二部图

13、着色，则算法找到的是一个需要n 种颜色的解。 【算法】设数组colorn表示顶点的着色情况，贪心法求解图着色问题的算法如下： |算法7.4：贪心法求解图着色问题； :输入：无向连通图 G=(V, E); -输出：最小色数 k- :1.所有顶点置未着色状态：1 :2.颜色k初始化为0;- :! :3.循环直到所有顶点均着色: |3.1 取下一种颜色k+;| |3.2依次考察所有顶点：I ! !3.2.1若顶点i已着色，则转步骤 3.2，考察下一个顶点；| |3.2.2 若顶点i着颜色k不冲突，则colori=k;| | 4.输出各顶点的着色； 例4最小生成树问题prim算法 【问题】 设G=(V

14、, E)是一个无向连通网，求 G的最小生成树。 最小生成树(minimal spanning tree)是各边的权值之和最小的生成树。 【想法】 最小生成树问题的贪心策略可以采用最近顶点策略：任选一个顶点，并以此建立生成 树的根结点，每一步的贪心选择是把不在生成树中的最近顶点添加到生成树中。Prim算法就应用了 这个贪心策略，它使生成树以一种自然的方式生长，即从任意顶点开始，每一步为这棵树添加一个 分枝，直到生成树中包含全部顶点。 设最小生成树 T=(U, TE)，初始时U=u。 ( U0为任意顶点)，TE= 。显然，Prim算法的关键是 如何找到连接U和V-U的最短边来扩充生成树 T。对于每

15、一个不在当前生成树中的顶点v V-U ,必 须知道它连接生成树的最短边信息。所以，对不在当前生成树中的顶点v V-U，需要保存两个信息： lowcostv表示顶点v到生成树中所有顶点的最短边；adjvexv表示该最短边在生成树中的顶点。例 如，对于图7.5(a)所示连通网，图7.5(b)(g)给出了从顶点A出发，用Prim算法构造最小生成树的过 程。 v0 (a)连通网 (b)初始化 (c)加入最近顶点V5(d)加入最近顶点V2 (e)加入最近顶点V3 图7.5 Prim算法构造最小生成树的过程 【算法】设置数组shortEdgen表示候选最短边集，数组元素包括 adjvex和lowcost两

16、个域，分 别表示候选最短边的邻接点和权值，例如，式7-1表明候选最短边(Vj, vQ的权值为w，其中Vj V-U , Vk U。 -shortEdgei.adjvex = k 彳(式7-1) -shortEdgei.lowcost = w 假设从顶点w出发构造最小生成树，则初始时，U = w，且shortEdgew.lowcost = 0 ,表示顶 点 w 已加入集合 U 中，数组元素 shortEdgei.adjvex = 0, shortEdgei.lowcost = (w, i)的权值(1 i w n-1)。然后在数组 shortEdgen中不断选取最小权值shortEdge k.low

17、cost，将 shortEdgek.lowcost 置为0,表示顶点k已加入集合U中。由于顶点k从集合V-U进入集合U后，候选最短边集发生了 变化，依据式7-2更新数组shortEdge的内容： (式 7-2) shortEdgej.lowcost = min shortEdgej.lowcost , cost( j, k) shortEdgej.adjvex = k (如果 cost(j, k)C) |4.1将第i个物品放入背包：xi=1; 4.2 C=C-wi; 4.3 i+; :5.xi=C/wi; 例7活动安排问题 【问题】设有n个活动的集合E=1,2,n，其中每个活动都要求使用同一资

18、源(如演讲会场)， 而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间色 和一个结束时间fi,且Si fj或sjfi时，活动i与活动 j相容。活动安排问题 (activity arrangement problem )要求在所给的活动集合中选出最大的相容活动 子集。 【想法】贪心法求解活动安排问题的关键是如何选择贪心策略，使得按照一定的顺序选择相容 活动，并能够安排尽量多的活动。至少有两种看似合理的贪心策略： (1) 最早开始时间：这样可以增大资源的利用率。 (2) 最早结束时间：这样可以使下一个活动尽早开始。 由于活动占用资源的时间没有限制，因此，后一种贪心

19、选择更为合理。直观上，按这种策略选 择相容活动可以为未安排的活动留下尽可能多的时间，也就是说，这种贪心选择的目的是使剩余时 间段极大化，以便安排尽可能多的相容活动。 为了在每一次贪心选择时快速查找具有最早结束时间的相容活动，可以将n个活动按结束时间 非减序排列。这样，贪心选择时取当前活动集合中结束时间最早的活动就归结为取当前活动集合中 排在最前面的活动。 例如，设有11个活动等待安排，这些活动按结束时间的非减序排列如表7.1所示。 表7.111个活动的开始时间和结束时间 i 1 2 3 4 5 6 7 8 9 10 11 s 1 3 0 5 3 5 6 8 8 2 12 1 :i 4 5 6

20、7 8 9 10 11 12 13 14 贪心法求解活动安排问题的过程如图7.9所示，其中阴影长条表示该活动已加入解集合中，空 白长条表示该活动是当前正在检查相容性的活动。首先选择活动1加入解集合，因为活动1具有最 早结束时间；活动 2和活动3与活动1不相容，所以舍弃他们；活动 4与活动1相容，因此将活动 4加入解集合；然后在剩下的活动中找与活动4相容并具有最早结束时间的活动，依此类推。最终 被选定的活动集合为1,4, 8, 11。 【算法】设有n个活动等待安排，色表示活动i的起始时间，fi表示活动i的结束时间(K i = fj)贝U 4.1.1 B=B+j；| 4.1.2 j=i; 4.2i

21、+; | 例8多机调度问题 【问题】设有n个独立的作业1,2,n，由m台相同的机器M M2,Mm进行加工处理， 作业i所需的处理时间为ti ( K i w n),每个作业均可在任何一台机器上加工处理，但不可间断、拆 分。多机调度问题 (multi-machine scheduling problem )要求给出一种作业调度方案，使所给的n个 作业在尽可能短的时间内由m台机器加工处理完成。 【想法】贪心法求解多机调度问题的贪心策略是最长处理时间作业优先，即把处理时间最长的 作业分配给最先空闲的机器，这样可以保证处理时间长的作业优先处理，从而在整体上获得尽可能 短的处理时间。按照最长处理时间作业优

22、先的贪心策略，当mn时，只要将机器i的0, ti)时间区间 分配给作业i即可；当mvn时，首先将n个作业按其所需的处理时间从大到小排序，然后依此顺序 将作业分配给最先空闲的处理机。 例如，设7个独立作业1,2, 3, 4, 5, 6, 7由3台机器M1, M2, M3加工处理，各作业所需的处理 时间分别为2, 14, 4, 16, 6, 5, 3,首先将这7个作业按处理时间从大到小排序，则作业4, 2, 5, 6, 3, 7, 1的处理时间为16, 14, 6, 5, 4, 3, 2,贪心法产生的作业调度如图7.10所示，具体过程如下： (1) 按照最长处理时间作业优先的贪心策略，将作业4分配

23、给机器 M1,则机器M1将在时间 16后空闲；将作业2分配给机器M2,则机器M2将在时间14后空闲；将作业5分配给机器M3,则 机器M3将在时间6后空闲，至此，三台机器均已分配作业； (2) 在三台机器中空闲最早的是机器M3,将作业6分配给机器 M3,并且机器 M3将在时间6 + 5 = 11后空闲； 将作业3分配给机器 M3，并且机器 M3将在时间11 图7.10三台机器的调度冋题示例 tn中，m台机器的空闲时间存储在数组dm中, (3) 在三台机器中空闲最早的是机器M3, + 4=15后空闲； (4) 在三台机器中空闲最早的是机器 M2, 将作业7分配给机器M2,并且机器M2将在时间 14+ 3=17后空闲； (5) 在三台机器中空闲最早的是机器M3, 将作业1分配给机器M3,并且机器M3将在时间 15+ 2=17后空闲。最后得到所需加工的最短时 间为17。 【算法】设n个作业的处理时间存储在数组 集合数组Sm存储每台机器所处理的作业，其中集合Si表示机器i所处理的作业，贪心法