第7章 贪心法

1、算法设计与分析算法设计与分析第第7章章 贪心法贪心法 贪婪，我找不到一个更好的词来描述它，它就是好！它就是对！它就是有效！美国演员道格拉思，在影片华尔街中的台词2Coin ChangingGreed is good. Greed is right. Greed works. Greed clarifies, cuts through, and captures the essence of the evolutionary spirit. - Gordon Gecko (Michael Douglas)算法设计与分析算法设计与分析思考思考 你的朋友要开一家安全公司，这需要得到n个不同的密码软件

2、的许可证根据规章，他们只能以每个月至多一个的速度得到这些许可证。每个许可证目前的售价是100美元，但他们全都按指数增长曲线变得更贵，设许可证j的费用每个月按照rj1的因子增加，且假设所有价格增长率是不同的，应该按照什么次序买这些许可证使花的总钱数最少？ 贪婪法又叫登山法贪婪法又叫登山法, , 它的根本思想是逐步它的根本思想是逐步到达山顶到达山顶, ,即逐步获得最优解。贪婪算法即逐步获得最优解。贪婪算法没有没有固定的算法框架固定的算法框架，算法设计的关键是贪婪策略，算法设计的关键是贪婪策略的选择。的选择。选择的贪婪策略要具有选择的贪婪策略要具有无后向性无后向性。某状态。某状态以后的过程不会影响以

3、前的状态以后的过程不会影响以前的状态, ,只与当前状只与当前状态或以前的状态有关态或以前的状态有关, ,称这种特性为称这种特性为无后效性无后效性。算法设计与分析算法设计与分析7.1 概概 述述 7.2 图问题中的贪心法图问题中的贪心法7.3 组合问题中的贪心法组合问题中的贪心法算法设计与分析算法设计与分析7.1 概概 述述 7.1.1 贪心法的设计思想贪心法的设计思想 7.1.2 贪心法的求解过程贪心法的求解过程算法设计与分析算法设计与分析 贪心法在解决问题的策略上目光短浅，只根据当贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出选择，而且一旦做出了选择，前已有的信息就做出选择，而

4、且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。换言不管将来有什么结果，这个选择都不会改变。换言之，贪心法并不是从整体最优考虑，它所做出的选之，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。择只是在某种意义上的局部最优。 这种局部最优选择并不总能获得整体最优解这种局部最优选择并不总能获得整体最优解（Optimal Solution），但通常能获得近似最优解），但通常能获得近似最优解（Near-Optimal Solution）。）。7.1.1 贪心法的设计思想贪心法的设计思想 Coin ChangingnGoal. Given currency denomin

5、ations: 1, 5, 10, 25, 100, devise a method to pay amount to customer using fewest number of coins.nEx: 34.nCashiers algorithm. At each iteration, add coin of the largest value that does not take us past the amount to be paid.nEx: $2.89.算法设计与分析算法设计与分析例：用贪心法求解付款问题。例：用贪心法求解付款问题。假设有面值为假设有面值为5元、元、2元、元、1元

6、、元、5角、角、2角、角、1角的货币，需角的货币，需要找给顾客要找给顾客4元元6角现金，为使付出角现金，为使付出的货币的数量最少，首的货币的数量最少，首先选出先选出1张面值不超过张面值不超过4元元6角的最大面值的货币，即角的最大面值的货币，即2元，元，再选出再选出1张面值不超过张面值不超过2元元6角的最大面值的货币，即角的最大面值的货币，即2元，元，再选出再选出1张面值不超过张面值不超过6角的最大面值的货币，即角的最大面值的货币，即5角，再选角，再选出出1张面值不超过张面值不超过1角的最大面值的货币，即角的最大面值的货币，即1角，总共付出角，总共付出4张货币。张货币。算法设计与分析算法设计与分

7、析 在付款问题每一步的贪心选择中，在不超过应付款在付款问题每一步的贪心选择中，在不超过应付款金额的条件下，只选择面值最大的货币，而不去考虑在金额的条件下，只选择面值最大的货币，而不去考虑在后面看来这种选择是否合理，而且它还不会改变决定：后面看来这种选择是否合理，而且它还不会改变决定：一旦选出了一张货币，就永远选定。付款问题的贪心选一旦选出了一张货币，就永远选定。付款问题的贪心选择策略是尽可能使付出的货币最快地满足支付要求，其择策略是尽可能使付出的货币最快地满足支付要求，其目的是使付出的货币张数最慢地增加，这正体现了贪心目的是使付出的货币张数最慢地增加，这正体现了贪心法的设计思想。法的设计思想。

8、算法设计与分析算法设计与分析贪心法求解的问题的特征：贪心法求解的问题的特征：（1）最优子结构性质 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质，也称此问题满足最优性原理。（2）贪心选择性质 所谓贪心选择性质是指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到。v 动态规划法通常以自底向上的方式求解各个子问题，而贪心法则通常以自顶向下的方式做出一系列的贪心选择。算法设计与分析算法设计与分析7.1.2 贪心法的求解过程贪心法的求解过程 用贪心法求解问题应该考虑如下几个方面：（1）候选集合C：为了构造问题的解决方案，有一个候选集合C作为问题的可能解，即问题的最终

9、解均取自于候选集合C。例如，在付款问题中，各种面值的货币构成候选集合。（2）解集合S：随着贪心选择的进行，解集合S不断扩展，直到构成一个满足问题的完整解。例如，在付款问题中，已付出的货币构成解集合。算法设计与分析算法设计与分析 （3）解决函数solution：检查解集合S是否构成问题的完整解。例如，在付款问题中，解决函数是已付出的货币金额恰好等于应付款。 （4）选择函数select：即贪心策略，这是贪心法的关键，它指出哪个候选对象最有希望构成问题的解，选择函数通常和目标函数有关。例如，在付款问题中，贪心策略就是在候选集合中选择面值最大的货币。 （5）可行函数feasible：检查解集合中加入一

10、个候选对象是否可行，即解集合扩展后是否满足约束条件。例如，在付款问题中，可行函数是每一步选择的货币和已付出的货币相加不超过应付款。 算法设计与分析算法设计与分析贪心法的一般过程Greedy(C) /C是问题的输入集合即候选集合 S= ; /初始解集合为空集 while (not solution(S) /集合S没有构成问题的一个解 x=select(C); /在候选集合C中做贪心选择 if feasible(S, x) /判断集合S中加入x后的解是否可行 S=S+x; C=C-x; return S;算法设计与分析算法设计与分析7.2 图问题中的贪心法图问题中的贪心法 7.2.1 TSP问题问

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

12、题的过程问题的过程25221543225221543232522154327363215432233215432C= 3 3 2 63 7 3 23 7 2 52 3 2 36 2 5 3 (a) 5城市的代价矩阵城市的代价矩阵 (b) 城市城市1城市城市4 (c) 城市城市4城市城市3算法设计与分析算法设计与分析算法算法7.1最近邻点策略求解最近邻点策略求解TSP问题问题 1 P= ; 2 V=V- -u0; u=u0; /从顶点从顶点u0出发出发 3 循环直到集合循环直到集合P中包含中包含n- -1条边条边 3.1 查找与顶点查找与顶点u邻接的最小代价边邻接的最小代价边(u, v)并且并且

13、v属于集合属于集合V； 3.2 P=P+(u, v); 3.3 V=V- -v; 3.4 u=v; /从顶点从顶点v出发继续求解出发继续求解 设图设图G有有n个顶点，边上的代价存储在二维数组个顶点，边上的代价存储在二维数组wnn中，集合中，集合V存储图的顶点，集合存储图的顶点，集合P存储经过的边，最近邻点存储经过的边，最近邻点策略求解策略求解TSP问题的算法如下：问题的算法如下： 算法设计与分析算法设计与分析 算法7.1的时间性能为O(n2)，因为共进行n-1次贪心选择，每一次选择都需要查找满足贪心条件的最短边。 用最近邻点贪心策略求解TSP问题所得的结果不一定是最优解，图7.1(a)中从城市

14、1出发的最优解是125431，总代价只有13。当图中顶点个数较多并且各边的代价值分布比较均匀时，最近邻点策略可以给出较好的近似解，不过，这个近似解以何种程度近似于最优解，却难以保证。例如，在图7.1中，如果增大边(2, 1)的代价，则总代价只好随之增加，没有选择的余地。 算法设计与分析算法设计与分析（2）最短链接最短链接策略：每次在整个图的范围内选择策略：每次在整个图的范围内选择最短边加入到解集合中，但是，要保证加入解集合最短边加入到解集合中，但是，要保证加入解集合中的边最终形成一个哈密顿回路。因此，当从剩余中的边最终形成一个哈密顿回路。因此，当从剩余边集边集E中选择一条边中选择一条边(u,

15、v)加入解集合加入解集合S中，应满足中，应满足以下条件：以下条件： 边边(u, v)是边集是边集E中中代价最小的边代价最小的边； 边边(u, v)加入解集合加入解集合S后，后，S中中不产生回路不产生回路； 边边(u, v) 加入解集合加入解集合S后，后，S中中不产生分枝不产生分枝；算法设计与分析算法设计与分析215432215432C= 3 3 2 63 7 3 23 7 2 52 3 2 36 2 5 3 (a) 5城市的代价矩阵城市的代价矩阵 (b) 城市城市1城市城市4 (c) 城市城市5城市城市22(d) 城市城市4城市城市3 (e) 城市城市3城市城市5 (f) 城市城市2回到出发城

16、市回到出发城市1最短链接贪心策略求解最短链接贪心策略求解TSP问题的过程问题的过程222154322221543222215432535算法设计与分析算法设计与分析算法7.2最短链接策略求解TSP问题 1P= ; 2E=E; /候选集合，初始时为图中所有边 3循环直到集合P中包含n-1条边 3.1 在E中选取最短边(u, v); 3.2 E=E-(u, v); 3.3 如果 (顶点u和v在P中不连通 and 不产生分枝) 则P=P+(u, v); 设图设图G有有n个顶点，边上的代价存储在二维数组个顶点，边上的代价存储在二维数组wnn中，中，集合集合E是候选集合即存储所有未选取的边，集合是候选集

17、合即存储所有未选取的边，集合P存储经过的存储经过的边，最短链接策略求解边，最短链接策略求解TSP问题的算法如下：问题的算法如下： 算法设计与分析算法设计与分析 在算法在算法7.2中，如果操作中，如果操作“在在E中选取最短边中选取最短边(u, v)”用顺序查找，则算法用顺序查找，则算法7.2的时间性能是的时间性能是O(n2)，如果采用堆排序的方法将集合，如果采用堆排序的方法将集合E中的边中的边建立堆，则选取最短边的操作可以是建立堆，则选取最短边的操作可以是O(log2n)，对于两个顶点是否连通以及是否会产生分枝，可对于两个顶点是否连通以及是否会产生分枝，可以用并查集的操作将其时间性能提高到以用并

18、查集的操作将其时间性能提高到O(n)，此，此时算法时算法7.2的时间性能为的时间性能为O(nlog2n)。 算法设计与分析算法设计与分析7.2.2 图着色问题图着色问题 给定无向连通图给定无向连通图G=(V, E)，求图，求图G的最小色数的最小色数k，使得用使得用k种颜色对种颜色对G中的顶点着色，可使任意两个相中的顶点着色，可使任意两个相邻顶点着色不同。邻顶点着色不同。算法设计与分析算法设计与分析12345例如，图例如，图7.3(a)所示的图可以只用两种颜色着色，将所示的图可以只用两种颜色着色，将顶点顶点1、3和和4着成一种颜色，将顶点着成一种颜色，将顶点2和顶点和顶点5着成另着成另外一种颜色

19、。为简单起见，下面假定外一种颜色。为简单起见，下面假定k个颜色的集合个颜色的集合为为颜色颜色1, 颜色颜色2, , 颜色颜色k。算法设计与分析算法设计与分析贪心策略：选择一种颜色，以任意顶点作为开始顶点，依次贪心策略：选择一种颜色，以任意顶点作为开始顶点，依次考察图中的未被着色的每个顶点，如果一个顶点可以用颜色考察图中的未被着色的每个顶点，如果一个顶点可以用颜色1着色，换言之，该顶点的邻接点都还未被着色，则用颜色着色，换言之，该顶点的邻接点都还未被着色，则用颜色1为为该顶点着色，当没有顶点能以这种颜色着色时，选择颜色该顶点着色，当没有顶点能以这种颜色着色时，选择颜色2和和一个未被着色的顶点作为

20、开始顶点，用第二种颜色为尽可能一个未被着色的顶点作为开始顶点，用第二种颜色为尽可能多的顶点着色，如果还有未着色的顶点，则选取颜色多的顶点着色，如果还有未着色的顶点，则选取颜色3并为尽并为尽可能多的顶点着色，依此类推。可能多的顶点着色，依此类推。 3451212345算法设计与分析算法设计与分析算法算法7.3图着色问题图着色问题 1color1=1; /顶点顶点1着颜色着颜色1 2for (i=2; i=n; i+) /其他所有顶点置未着色状态其他所有顶点置未着色状态 colori=0; 3k=0; 4循环直到所有顶点均着色循环直到所有顶点均着色 4.1 k+; /取下一个颜色取下一个颜色 4.

21、2 for (i=2; iC) 4.1 xi=1; /将第将第i个物品放入背包个物品放入背包 4.2 C=C-wi; 4.3 i+;5. xi=C/wi;算法算法7.6的时间主要消耗在将各种物品依其单位重量的价值的时间主要消耗在将各种物品依其单位重量的价值从大到小排序。因此，其时间复杂性为从大到小排序。因此，其时间复杂性为O(nlog2n)。算法设计与分析算法设计与分析7.3.2 活动安排问题活动安排问题 设有设有n个活动的集合个活动的集合E=1, 2, , n，其中每个活，其中每个活动都要求使用同一资源（如演讲会场），而在同一时动都要求使用同一资源（如演讲会场），而在同一时间内只有一个活动能

22、使用这一资源。每个活动间内只有一个活动能使用这一资源。每个活动i都有都有一个要求使用该资源的起始时间一个要求使用该资源的起始时间si和一个结束时间和一个结束时间fi，且且si =fj) 则则 4.1.1 B=B+j; 4.1.2 j=i; 4.2 i+; 算法算法7.7的时间主要消耗在将各个活动按结束时间从的时间主要消耗在将各个活动按结束时间从小到大排序。因此，算法的时间复杂性为小到大排序。因此，算法的时间复杂性为O(nlog2n)。算法设计与分析算法设计与分析算法算法7.8活动安排问题活动安排问题 int ActiveManage(int s , int f , bool a , int n

23、) /各活动的起始时间和结束时间存储于数组各活动的起始时间和结束时间存储于数组s和和f中且中且 /按结束时间的非减序排列按结束时间的非减序排列 a1=1; j=1; count=1; for (i=2; i=fj) ai=1; j=i; count+; else ai=0; return count; 算法设计与分析算法设计与分析7.3.3 多机调度问题多机调度问题 设有设有n个独立的作业个独立的作业1, 2, , n，由，由m台相台相同的机器同的机器M1, M2, , Mm进行加工处理，作业进行加工处理，作业i所需的处理时间为所需的处理时间为ti（1in），每个作业均可在），每个作业均可在任

24、何一台机器上加工处理，但不可间断、拆分。任何一台机器上加工处理，但不可间断、拆分。多机调度问题要求给出一种作业调度方案，使所多机调度问题要求给出一种作业调度方案，使所给的给的n个作业在尽可能短的时间内由个作业在尽可能短的时间内由m台机器加台机器加工处理完成。工处理完成。算法设计与分析算法设计与分析贪心法求解多机调度问题的贪心策略是贪心法求解多机调度问题的贪心策略是最长处理最长处理时间时间作业优先，即把处理时间最长的作业分配给作业优先，即把处理时间最长的作业分配给最先空闲的机器，这样可以保证处理时间长的作最先空闲的机器，这样可以保证处理时间长的作业优先处理，从而在整体上获得尽可能短的处理业优先处理，从而在整体上获得尽可能短的处理时间。按照最长处理时间作业优先的贪心策略，时间。按照最长处理时间作业优先的贪心策略，当当mn时，只要将机器时，只要将机器i的的0, ti)时间区间分配给作时间区间分配给作