第7章_贪心算法.

第7章贪心算法GreedyMethod算法设计与分析—本科生课程DesignandAnalysisofAlgorithm邱钊海南大学信息科学技术学院CollegeofInformationScienceandTechnology,[e-mail]2019/12/192教学重点贪心法的设计思想，各种经典问题的贪心思想教学难点各种经典问题的贪心，多机调度问题的贪心算法教学内容及目标知识点教学要求了解理解掌握熟练掌握贪心法的设计思想√TSP问题√图着色问题√最小生成树问题√背包问题√活动安排问题√多机调度问题√学习目标Chapter7GreedyMethod2019/12/19Chapter7GreedyMethod37.1概述7.2图问题中的贪心法7.3组合问题中的贪心法阅读材料——贪心法的正确性证明第7章贪心算法2019/12/19Chapter7GreedyMethod4第7章贪心算法贪心法把一个复杂问题的解分解为一系列较为简单的局部最优选择，每一步选择都是对当前解的一个扩展，直到获得问题的完整解。贪心法的典型应用是求解最优化问题，而且对许多问题都能得到整体最优解，即使不能得到整体最优解，通常也是最优解的很好近似。2019/12/19Chapter7GreedyMethod5什么是贪心算法？贪心法目光短浅，只根据当前已有的信息做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。7.1.1贪心法的设计思想2019/12/19Chapter8GreedyMethod6例：求解付款找零问题的贪心法设货币面值为：5元、2元、1元、5角、2角、1角找零为：4.6元问题：使付出的货币张数最少，即:d=min∑xi,1≤i≥n其中：X称为问题的解向量，所有向量的全体称为问题的解空间。求解：选出1张面值=4元6角的最大面值的货币，即2元；选出1张面值=2元6角的最大面值的货币，即2元；选出1张面值=6角的最大面值的货币，即5角；选出1张面值=1角的最大面值的货币，即1角；总共付出4张货币。7.1.1贪心法的设计思想2019/12/19Chapter7GreedyMethod7付款找零问题的贪心算法在不超过应付款金额A的条件下，只选择面值最大的货币，而不去考虑在后面看来这种选择是否合理，而且它还不会改变决定：一旦选出了一张货币，就永远选定。付款找零问题的贪心选择策略是尽可能使付出的货币最快地满足支付要求，其目的是使付出的货币张数最慢地增加，这正体现了贪心法的设计思想。7.1.1贪心法的设计思想2019/12/19Chapter7GreedyMethod8例：求解付款找零问题的贪心法设货币面值为：3元、1元、8角、5角、1角找零为：4.6元求解：选出1张面值=4元6角的最大面值的货币，即3元；选出1张面值=1元6角的最大面值的货币，即1元；选出1张面值=6角的最大面值的货币，即5角；选出1张面值=1角的最大面值的货币，即1角；总共付出4张货币（3元、1元、5角、1角）但最优解：3张货币（3元、8角、8角）如果一个问题的最优解只能用蛮力法得到，贪心法不失为寻找近似解的一个较好方法7.1.1贪心法的设计思想2019/12/19Chapter7GreedyMethod9与动态规划法的关系动态规划法把一个复杂问题分解为若干相互重叠的子问题，通过求解子问题形成的一系列决策得到原问题的解；贪心法把一个复杂问题分解为一系列较为简单的局部最优选择，每一步选择都是对当前解的一个扩展，直到获得问题的完整解；动态规划法以自底向上的方式求解各个子问题，而贪心法则通常以自顶向下的方式做出一系列的贪心选择。7.1.1贪心法的设计思想2019/12/19Chapter7GreedyMethod10[问题]古埃及人只用分子为1的分数，在表示一个真分数时，将其分解为若干个埃及分数之和，如7/8表示为1/2+1/3+1/24。怎么将一个真分数表示为最少的埃及分数之和的形式？[想法]一个真分数的埃及分数表示不是唯一的，将一个真分数表示为最少埃及分数之和的形式，其贪心策略是选择真分数包含的最大埃及分数。如7/8为例，7/81/2,则1/2是第一次贪心选择的结果；7/8-1/2=3/81/3，则1/3是第二次贪心选择的结果；3/8-1/3=1/24,则1/24是第三次贪心选择的结果。7/8=1/2+1/3+1/247.1.2一个简单的例子——埃及分数2019/12/19Chapter7GreedyMethod11设真分数为A/B，B除以A的整数部分为C，余数为D，则：B＝A*C+D(DA)即B/A=C+D/AC+1则A/B1/(C+1)即1/(C+1)即为真分数A/B包含的最大埃及分数。设E＝C+1，由于A/B-1/E=((A*E)-B)/(B*E)这个分数可能存在公因子，所以需要化简，可将分子和分母同时除以最大公约数。7.1.2一个简单的例子——埃及分数2019/12/19Chapter7GreedyMethod12[算法]伪代码描述如下：算法7.1：埃及分数EgyptFraction输入：真分数的分子A和分母B输出：最少的埃及分数之和1.E＝B/A+1;//E＝C+12.输出1/E;3.A=A*E-B;B=B*E;4.求A和B的最大公约数R，如果R不为1，将A和B同时除以R5.如果A等于1，则输出1/B，算法结束；否则转步骤17.1.2一个简单的例子——埃及分数2019/12/19Chapter7GreedyMethod13voidEgyptFraction(intA,intB){intE,R;coutA“/”B“=”;do{E=B/A+1;cout“1/”E“+”;A=A*E-B;B=B*E;R=CommFractor(B,A);//CommFractor为求最大公约数函数if(R1){A=A/R;B=B/R;}}while(A1);cout“1/”Bendl;return;}7.1.2一个简单的例子——埃及分数2019/12/19Chapter7GreedyMethod147.1概述7.2图问题中的贪心法7.3组合问题中的贪心法阅读材料——贪心法的正确性证明第7章贪心算法2019/12/19Chapter7GreedyMethod157.2图问题中的贪心法7.2.1TSP问题7.2.2图着色问题7.2.3最小生成树问题2019/12/19Chapter7GreedyMethod16求解TSP问题至少有两种贪心策略是合理的最近邻点策略从任意城市出发，每次在没有到过的城市中选择最近的一个，直到经过了所有的城市，最后回到出发城市。最短链接策略每次在整个图的范围内选择最短边加入到解集合S中，但是，要保证加入解集合中的边最终形成一个哈密顿回路。8.2.1TSP问题2019/12/19Chapter7GreedyMethod17(d)城市3→城市5(e)城市5→城市2(f)城市2→城市1最近邻点贪心策略求解TSP问题的过程252154322522154323252154327363215432233215432C=∞33263∞73237∞25232∞36253∞(a)5城市的代价矩阵(b)城市1→城市4(c)城市4→城市37.2.1TSP问题2019/12/19Chapter7GreedyMethod18215432215432C=∞33263∞73237∞25232∞36253∞(a)5城市的代价矩阵(b)城市1→城市4(c)城市5→城市22(d)城市4→城市3(e)城市3→城市5(f)城市2回到出发城市1最短链接贪心策略求解TSP问题的过程2221543222215432222154325357.2.1TSP问题2019/12/19Chapter7GreedyMethod19算法7.2——最近邻点策略求解TSP问题1．P={};//对应解集合S2．V=V-{u0};u=u0;//从顶点u0出发3．循环直到集合P中包含n-1条边3.1找与顶点u邻接的最小代价边(u,v),并且v属于集合V；3.2P=P+{(u,v)};3.3V=V-{v};3.4u=v;//从顶点v出发继续求解[算法1]设图G有n个顶点，边上的代价存储在二维数组w[n][n]中，集合V存储图的顶点，集合P存储经过的边，最近邻点策略求解TSP问题的算法如下：7.2.1TSP问题2019/12/19Chapter7GreedyMethod20算法分析1时间复杂度算法7.2的时间性能为O(n2)，因为共进行n-1次贪心选择，每一次选择都需要查找满足贪心条件的最短边。最优解讨论用最近邻点贪心策略求解TSP问题所得的结果不一定是最优解，图7.1(a)中从城市1出发的最优解是:125431代价：137.2.1TSP问题2019/12/19Chapter7GreedyMethod21当图中顶点个数较多并且各边的代价值分布比较均匀时，最近邻点策略可以给出较好的近似解，不过，这个近似解以何种程度近似于最优解，却难以保证。例如，在图7.1中，如果增大边(2,1)的代价，则总代价只好随之增加，没有选择的余地。7.2.1TSP问题2019/12/19Chapter7GreedyMethod22最短链接策略：每次在整个图的范围内选择(1)最短边加入到解集合中，但是，要保证加入解集合中的(2)边最终形成一个哈密顿回路。因此，当从剩余边集E‘中选择一条边(u,v)加入解集合S中，应满足以下条件：边(u,v)是边集E‘中代价最小的边；边(u,v)加入解集合S后，S中不产生回路；边(u,v)加入解集合S后，S中不产生分枝；7.2.1TSP问题2019/12/19Chapter7GreedyMethod23算法7.3——最短链接策略求解TSP问题1．P={};2．E'=E;//候选集合，初始时为图中所有边3．循环直到集合P中包含n-1条边3.1在E'中选取最短边(u,v);3.2E'=E'-{(u,v)};3.3如果(顶点u和v在P中不连通and不产生分枝)则P=P+{(u,v)};设图G有n个顶点，w[n][n]存储边上的代价，集合E‘存储是候选集合中未选取的边，集合P存储经过的边，最短链接策略求解TSP问题的算法如下：7.2.1TSP问题2019/12/19Chapter7GreedyMethod24时间复杂度讨论在算法7.3中，如操作“在E‘中选取最短边(u,v)”用顺序查找，则算法7.3的时间性能是O(n2)，如果采用堆排序的方法将集合E‘中的边建立堆，则选取最短边的操作可以是O(log2n)，对于两个顶点是否连通以及是否会产生分枝，可以用并查集的操作将其时间性能提高到O(log2n)，此时算法7.3的时间性能为O(nlog2n)。7.2.1TSP问题2019/12/19Chapter7GreedyMethod257.2图问题中的贪心法7.2.1TSP问题7.2.2图着色问题7.2.3最小生成树问题2019/12/19Chapter7GreedyMethod267.2.2图着色问题给定无向连通图G=(V,E)，求图G的最小色数k，使得用k种颜色对G中的顶点着色，可使任意两个相邻顶点着色不同。2019/12/19Chapter7GreedyMethod2712345例如，下图所示可以只用两种颜色着色，将顶点1、3和4着成一种颜色，将顶点2和顶点5着成另外一种颜色。假定k个颜色的集合为{颜色1,颜色2,…,颜色k}。7.2