第三章贪心算法精选文档.ppt

《第三章贪心算法精选文档.ppt》由会员分享，可在线阅读，更多相关《第三章贪心算法精选文档.ppt（51页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章贪心算法本讲稿第一页，共五十一页2023/4/12计算机算法设计与分析2找硬币n假设有四种硬币，面值分别为二角五分二角五分一角一角五分五分一分一分现在要找给某顾客六角三分钱，哪种找钱方法拿出的硬币个数最少呢？二角五分二角五分二角五分二角五分一角一角一分一分一分一分一分一分首先选出一个面值不超过六角三分的最大硬币，即二角五分；然后从六角三分中减去二角五分，剩下三角八分；再选出一个面值不超过三角八分的最大硬币，即又一个二角五分，如此一直做下去。这种方法实际上就是贪心算法。本讲稿第二页，共五十一页2023/4/12计算机算法设计与分析3再找硬币n若硬币的面值改为一分、五分和一角一分3种，而要找

2、个顾客的是一角五分钱。n还用贪心算法，将找个顾客1个一角一分的硬币和4个一分的硬币。n然而，3个五分的硬币显然才是最好的找法。本讲稿第三页，共五十一页2023/4/12计算机算法设计与分析4贪心算法的特点n贪心算法总是作出在当前来看是最好的选择。n就是说，贪心算法并不从整体最优上来考虑，所作出的选择只是某种意义上的局部最优选择。n当然希望贪心算法得到的最终结果是最优的。n可是贪心算法并不能保证最终结果是最优的。n不过，在许多情况下，应用贪心算法能够得到整体最优解；并且在一些情况下，即使得到的不是最优解，也是一个很好的近似解。本讲稿第四页，共五十一页2023/4/12计算机算法设计与分析5贪心算

3、法的一般框架nGreedyAlgorithm(parameters)n初始化；n重复执行以下的操作：n选择当前可以选择的(相容)最优解；n将所选择的当前解加入到问题的解中；n直至满足问题求解的结束条件。n本讲稿第五页，共五十一页2023/4/12计算机算法设计与分析6最小生成树n设G=(V,E)是一个无向连通带权图，即一个网络。E的每条边(v,w)的权为cvw。n如果G的一个子图G是一棵包含G的所有顶点的树，则称G为G的生成树。n生成树的各边的权的总和称为该生成树的耗费。n在G的所有生成树中，耗费最小的生成树称为G的最小(优)生成树。本讲稿第六页，共五十一页2023/4/12计算机算法设计与分

4、析7树的基本性质n连通无回路的图G称为树。n树是点比边多一的连通图，G连通且q=p1。n树是点比边多一的无回路图：G无回路且q=p1n树若添条边就有回路：G无回路，但对任意的u,vV(G)，若uvE(G)，则G+uv中恰有一条回路n树若减条边就不连通：G连通，但对eE(G),Ge不连通。nn个顶点的连通图的生成树含有n1条边。本讲稿第七页，共五十一页若G的任何最小生成树都不包含e1。设T为G的最小生成树，e1T。于是T+e1是一个有回路的图且该回路中包含e1。该回路中必有条不是e的边ei。令T=T+e1ei。T也是G的生成树。又c(T)=c(T)+c(e1)c(ei)，c(e1)c(ei)，从

5、而c(T)c(T)，T是G的最小生成树且含有边e1。矛盾。故必定有图G的最小生成树包含了e1。2023/4/12计算机算法设计与分析8最小生成树的贪心选择性质n令G中权最小的边为e1。首先必定有图G的一棵最小生成树包含了e1。n选定第一条边e1以后，该如何选择第二条边呢？n依据各条边的权重，依次选出权重较轻的n1条边。这n1条边必定包括了G的n个顶点。这样就得到了G的一棵最小生成树。这样做是否可以呢？n不行！因为不能保证这n1条边构成树？n要保证这n1条边构成树，必须使这n1条边是连通的或者是无回路的。nPrim算法的做法：在保证连通的前提下依次选出权重较小的n1条边（在实现中体现为n个顶点的

6、选择）。nKruskal算法的做法：在保证无回路的前提下依次选择权重较小的n1条边。本讲稿第八页，共五十一页2023/4/12计算机算法设计与分析9Prim算法n基本思想：在保证连通的前提下依次选出权重较小的n1条边。nG=(V,E)为无向连通带权图，令V=1,2,n。n设置一个集合S，初始化S=1，T=。n贪心策略：如果VS中的顶点j与S中的某个点i连接且(i,j)的权重最小，于是就选择j(将j加入S)，并将(i,j)加入T中。n重复执行贪心策略，直至VS为空。本讲稿第九页，共五十一页2023/4/12计算机算法设计与分析10Prim算法中的数据结构n图用连接矩阵Cij给出，即Cij为结点i

7、到结点j的权重。n标志数组Si指示顶点i是否已经加入到S中。n为了有效地找出VS中满足与S中的某个点i连接且(i,j)权重最小的顶点j，对其中的每个顶点j设立两个数组closestj和lowcostj：nclosestj是S中与j最近的顶点，(closestj,j)即为选中的边，而lowcostj是相应边的权重。本讲稿第十页，共五十一页2023/4/12计算机算法设计与分析11Prim算法的实现nPrim(intn,Type*c)初始化：结点1放入S；并初始化lowcost和closest；执行以下操作n1次：依据lowcost找出与S最近的点j并放入S；调整lowcost和closest；i

8、ntj=1;sj=true;for(inti=2;i=n;i+)closesti=1;lowcosti=c1i;si=false;for(i=1;in;i+)min=inf;for(intk=2;k=n;k+)if(lowcostkmin&!sk)min=lowcostk;j=ksj=true;s中仅加入了一个新成员j，因此只需要依据结点j调整lowcost和closest；for(k=2;k=n;k+)if(cjklowcostk&!sk)lowcostk=cjk;closestk=j本讲稿第十一页，共五十一页2023/4/12计算机算法设计与分析12Prim算法的示例n给定一个连通带权图如

9、下：1234561655536624n初始时S=1，T=；1n第一次选择：(1,3)权最小S=1,3T=(1,3)；3n第二次选择：(3,6)权最小S=1,3,6，T=(1,3),(3,6)；6n第三次选择：(6,4)权最小S=1,3,6,4，T=(1,3),(3,6),(6,4)；4n第四次选择：(2,3)权最小S=1,3,6,4,2，T=(1,3),(3,6),(6,4),(2,3)；2n第五次选择：(5,2)权最小S=1,3,6,4,2,5，T=(1,3),(3,6),(6,4),(3,2)(2,5)；5本讲稿第十二页，共五十一页2023/4/12计算机算法设计与分析13Kruskal算

10、法n基本思想：在保证无回路的前提下依次选出权重较小的n1条边。n贪心策略：如果(i,j)是E中尚未被选中的边中权重最小的，并且(i,j)不会与已经选择的边构成回路，于是就选择(i,j)。问题：如何知道(i,j)不会造成回路？n若边(i,j)的两个端点i和j属于同一个连通分支，则选择(i,j)会造成回路，反之则不会造成回路n因此初始时将图的n个顶点看成n个孤立分支。本讲稿第十三页，共五十一页2023/4/12计算机算法设计与分析14Kruskal算法的数据结构n结构数组e表示图的边，ei.u、ei.v和ei.w分别表示边i的两个端点及其权重。n函数Sort(e,w)将数组e按权重w从小到大排序。

11、n一个连通分支中的顶点表示为一个集合。n函数Initialize(n)将每个顶点初始化为一个集合n函数Find(u)给出顶点u所在的集合。n函数Union(a,b)给出集合a和集合b的并集。n重载算符!=判断集合的不相等。本讲稿第十四页，共五十一页2023/4/12计算机算法设计与分析15Kruskal算法的实现Kruskal(intn,*e)Sort(e,w);/将边按权重从小到大排序initialize(n);/初始时每个顶点为一个集合k=1;/k累计已选边的数目，j=1;/j为所选的边在e中的序号while(kn)/选择n1条边a=Find(ej.u);b=Find(ej.v);/找出第

12、j条边两个端点所在的集合if(a!=b)Tk=j;Union(a,b);k=k+1;/若不同，第j条边放入树中并合并这两个集合j+/继续考察下一条边本讲稿第十五页，共五十一页2023/4/12计算机算法设计与分析16Kruskal算法的例子1234561655536624131462253364145235345126356566初始时为6个孤立点123456选择了边1，于是1、3点合并为同一个集合。选择了边2，于是4、6点合并为同一个集合。选择了边3，于是2、5点合并为同一个集合。选择了边4，于是1、3、4、6点合并为同一个集合考察边5，因为1、4点属于同一个集合，被放弃。选择边6，于是1、

13、3、4、6、2、5点属于同一个集合。已经选择边了n1条边，算法结束。结果如图所示。uvw本讲稿第十六页，共五十一页2023/4/12计算机算法设计与分析17Prim与Kruskal两算法的复杂性nPrim算法为两重循环，外层循环为n次，内层循环为O(n)，因此其复杂性为O(n2)。nKruskal算法中，设边数为e，则边排序的时间为O(eloge)，最多对e条边各扫描一次，每次确定边的时间为O(loge)，所以整个时间复杂性为O(eloge)。n当e=(n2)时，Kruskal算法要比Prim算法差；n当e=(n2)时，Kruskal算法比Prim算法好得多。本讲稿第十七页，共五十一页2023

14、/4/12计算机算法设计与分析18贪心算法也能获得最优解n用Kruskal算法得到的生成树T*必是最优树。n证明：设T*不是最优，令T是与T*有k条共同边的最优树且k是最优树与T*共有边数的最大值nTT*ek+1:ek+1E(T)且ek+1E(T*)。n则T+ek+1含唯一回路C，C必有条边ekE(T*)。n令T=(T+ek+1)ek,w(T)=w(T)+w(ek+1)w(ek)。n由算法知，w(ek+1)w(ek)，T是最优树。n但T与T*有k+1条共同边，矛盾。故T*是最优本讲稿第十八页，共五十一页2023/4/12计算机算法设计与分析190-1背包问题n给定n个物品和一个背包。物品i的重

15、量为wi，价值为vi，背包容量为c。问如何选择装入背包中的物品，使得装入背包的物品的价值最大？n在装入背包时，每种物品i只有两种选择，装入或者不装入，既不能装入多次，也不能只装入一部分。因此，此问题称为0-1背包问题。n如果在装入背包时，物品可以切割，即可以只装入一部分，这种情况下的问题称为背包问题。本讲稿第十九页，共五十一页2023/4/12计算机算法设计与分析200-1背包问题不适用贪心算法n背包容量为50kg，物品1,2和3的容量和价值分别为(10kg,$60),(20kg,$100)和(30kg,$120)。n单位重量价值最高的为物品1，6$/kg。但是依照贪心算法首选物品1却不能获得

16、最优解：物品1物品2物品1物品3物品2物品3总价值为$160,空余20kg总价值为$180,空余10kg总价值为$220,没有空余n但是背包问题却是适用贪心算法的。本讲稿第二十页，共五十一页2023/4/12计算机算法设计与分析21贪心算法的基本要素n贪心算法的基本要素是：贪心选择性质。n所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优解的选择，即贪心选择来达到。n贪心选择每次选取当前最优解，因此它依赖以往的选择，而不依赖于将来的选择。n贪心算法通常以自顶向下的方式进行，每次贪心选择就将原问题转化为规模更小的子问题。本讲稿第二十一页，共五十一页2023/4/12计算机算法设计与分

17、析22如何确定贪心选择性质n证明贪心选择将导致整体的最优解：n首先证明存在问题的一个整体最优解必定包含了第一个贪心选择。n然后证明在做了贪心选择后，原问题简化为规模较小的类似子问题，即可继续使用贪心选择。n于是用数学归纳法可证明，经过一系列贪心选择可以得到整体最优解。本讲稿第二十二页，共五十一页2023/4/12计算机算法设计与分析23单源最短路径n给定一个图G=(V,E)，其中每条边的权是一个非负实数。另外给定V中的一个顶点v，称为源。求从源v到所有其它各个顶点的最短路径。n单源最短路径问题的贪心选择策略：选择从源v出发目前用最短的路径所到达的顶点，这就是目前的局部最优解。125431020

18、50100301060赋权图G本讲稿第二十三页，共五十一页2023/4/12计算机算法设计与分析24单源最短路径的贪心算法n基本思想：首先设置一个集合S；用数组dis来记录v到S中各点的目前最短路径长度。然后不断地用贪心选择来扩充这个集合，并同时记录或修订数组dis；直至S包含所有V中顶点。n贪心选择：一个顶点u属于S当且仅当从v到u的最短路径长度已知。n初始化：S中仅含有源v。本讲稿第二十四页，共五十一页2023/4/12计算机算法设计与分析25Dijkstra算法nDijkstra算法的做法是：n由近到远逐步计算，每次最近的顶点的距离就是它的最短路径长度。n然后再从这个最近者出发。即依据最

19、近者修订到各顶点的距离，然后再选出新的最近者。n如此走下去，直到所有顶点都走到。本讲稿第二十五页，共五十一页2023/4/12计算机算法设计与分析26Dijkstra算法ProcedureDijkstra(1)S:=1;/初始化S(2)fori:=2tondo/初始化dis(3)disi=C1,i;/初始时为源到顶点i一步的距离(4)fori:=1tondo(5)从V-S中选取一个顶点u使得disu最小；(6)将u加入到S中；/将新的最近者加入S(7)forwV-Sdo/依据最近者u修订disw(8)disw:=min(disw,disu+Cu,w)本讲稿第二十六页，共五十一页2023/4/1

20、2计算机算法设计与分析27Dijkstra算法举例迭代Sudis2dis3dis4dis5初始1-10 3010011,22106030 10021,2,441050309031,2,4,331050306041,2,4,3,551050306012543102050100301060赋权图G由数组disi可知：从顶点1到顶点2、3、4、5的最短通路的长度分别为10、50、30和60。本讲稿第二十七页，共五十一页2023/4/12计算机算法设计与分析28Dijkstra算法的贪心选择性质nDijkstra算法中所做的贪心选择是：若u是VS中具有最短路径的特殊顶点，就将u选入S，并确定了从源到u

21、的最短路径长度disu。n为什么从源到u没有更短的路径呢？n若有，则将如下图所示：Svdisu(最近距离)uxdisx若该路径经S外一点x到达u，则：disx+d(x,u)disu从而disxdisu，这与u的选取矛盾本讲稿第二十八页，共五十一页2023/4/12计算机算法设计与分析29Dijkstra算法的计算复杂性nDijkstra算法有两层循环，外层循环为n次，内层有两个循环：一个是选出最小的u(第5行)，另一个是修订disw(第7、8行)，内层循环的时间为O(n)。n因此Dijkstra算法的时间复杂度为O(n2)。nDijkstra算法能求出从源到其它各顶点的最短通路的长度，但是却并

22、没有给出其最短通路。n对Dijkstra算法做适当的修改便可求出最短通路。见书上P37本讲稿第二十九页，共五十一页2023/4/12计算机算法设计与分析30旅行商问题n推销员从某城市出发，遍历n个城市最后返回出发城市。设从城市i到城市j的费用为cij，如何选择旅行路线使得该推销员此趟旅行的总费用最小?n图论语言表述：给定n个节点简单无向完全图G=，c(i,j)是节点i到j的代价(边权)。在G中求遍历所有节点简单回路C，使C上所有边权的和最小。本讲稿第三十页，共五十一页2023/4/12计算机算法设计与分析31旅行商问题分析12345112752443312435 对于对于n n个节点的旅行商问

23、题，个节点的旅行商问题，n n个节点的任意一个圆排列个节点的任意一个圆排列都是问题的一个可能解。都是问题的一个可能解。n n个节点的圆排列有个节点的圆排列有(n-1)!(n-1)!个，因个，因此问题归结为在此问题归结为在(n-1)!(n-1)!个回路中选取最小回路。个回路中选取最小回路。是否能够不用O(n-1)!)时间来求解旅行商问题？本讲稿第三十一页，共五十一页2023/4/12计算机算法设计与分析32旅行商问题的贪心算法n基本思想：首先设置一个集合Path和当前节点v，然后不断地用贪心选择来扩充这个集合，直至Path包含所有V中顶点。n贪心选择：如果VPath中的顶点j是与当前节点v相邻接

24、的顶点中边权最小的，于是就选择j(将j加入Path)，并将j作为新的当前节点。n初始化：Path中仅含有源v。本讲稿第三十二页，共五十一页2023/4/12计算机算法设计与分析33最临近算法中的数据结构n图用连接矩阵Wij给出，即Wij为结点i到结点j的权重。nPath记录依次连接的城市，p记录当前到达的最后一个顶点，cost为当前路径长度。n如果节点k已经到达，则arrivedk=true。本讲稿第三十三页，共五十一页2023/4/12计算机算法设计与分析34旅行商问题的最临近算法CostTypeTray_Greedy(intn,CostType*w,int*path)for(i=1;i=n

25、;i+)arrivedi=false;cost=0;/初始化path1=1;p=1;arrived1=true;/从节点1出发for(i=2;i=n;i+)min=inf;for(j=1;j=n;j+)if(!arrivedj&wpjmin)k=j;min=wpj/搜索最临近p且尚未到达过的节点kcost=cost+wpk;pathi=k;arrivedk=true;p=k;/将节点k加入到路径中cost=cost+wp1;returncost;/加上回路最后一条边的权本讲稿第三十四页，共五十一页2023/4/12计算机算法设计与分析35旅行商算法举例从节点1出发：Path=;cost=14;

26、因此最临近法不保证求得旅行商问题的精确解，只能因此最临近法不保证求得旅行商问题的精确解，只能得到问题地近似解。一般地，贪心选择只依赖于前面选择得到问题地近似解。一般地，贪心选择只依赖于前面选择步骤地最优性，因此是局部最优的，所以贪心法不能够确步骤地最优性，因此是局部最优的，所以贪心法不能够确保求出问题的最优解。保求出问题的最优解。不难看出，从节点2出发：Path=;cost=10;且此为最优解！本讲稿第三十五页，共五十一页2023/4/12计算机算法设计与分析36改进的旅行商算法n如果分别从节点i出发（i=1,2,.n）执行算法Tray_Greedy，通过结果比较，取最小代价回路，可以求得更接

27、近于最佳解的近似解。n详见书上P40算法Tray_Greedy1本讲稿第三十六页，共五十一页2023/4/12计算机算法设计与分析37Tray_Greedy算法的计算复杂性nTray_Greedy算法有两层循环，外层循环为n次，内层循环也是n次，因此Tray_Greedy算法的时间复杂度为O(n2)nTray_Greedy1算法分别从n个节点出发计算最小代价回路，其时间复杂度为O(n3)本讲稿第三十七页，共五十一页2023/4/12计算机算法设计与分析38活动安排问题n设有n个活动的集合E=1,2,n，其中每个活动都要求使用同一资源，且在同一时间里只能有一个活动可以使用该资源。现要求给出一个活

28、动安排，使得利用该资源活动为最多。n每个活动i都有使用该资源的一个启始时间si和一个结束时间fi，sifi，其占用资源的时间为半开区间si,fi)。若区间si,fi)与区间sj,fj)不相交，则称活动i与活动j是相容的。活动安排问题就是求活动安排问题就是求E的最大相容活动子集。的最大相容活动子集。本讲稿第三十八页，共五十一页2023/4/12计算机算法设计与分析39活动安排的例子i12345678910 11si650283183512fi 109613 1254118714本讲稿第三十九页，共五十一页2023/4/12计算机算法设计与分析40活动安排问题的贪心算法n基本思想：某项活动结束时间

29、愈早，安排其它活动的剩余区间愈大。所以贪心策略为尽量选择结束时间早的活动来安排。为此，将活动按结束时间的非减顺序排序，即f1f2fn。显然排序需要的时间为O(nlogn)。n贪心选择：当安排下第i个活动后，可能有：fisi+1，所以第i+1个活动无法安排，这就必须舍弃第i+1个活动，检测第i+2个活动直到第i+k个活动的si+kfi，就把此活动安排进来。本讲稿第四十页，共五十一页2023/4/12计算机算法设计与分析41先将所有活动按照结束时间fi递增排序活动安排的例子首先选定活动1，其结束时间f1=4。然后因s4=54，选定活动4，这时f4=7。又因s8=87，选定活动8，这时f8=11。最

30、后因s11=1211，选定活动11。最终的活动安排为：最终的活动安排为：1、4、8和和11。i12345678910 11si130535688212fi45678910 11 12 13 14本讲稿第四十一页，共五十一页2023/4/12计算机算法设计与分析42活动安排贪心算法的实现typedefstructintnumber;/活动的编号floatstart;/活动开始的时间floatend;/活动结束的时间Boolselected;/标记活动是否被选择Active;intgreedySelector(Activeactivity,intn)QuitckSort(activity,n);/

31、将活动按结束时间排序activity1.selected=true;j=1;count=1;for(i=2;i=activityj.end)activityi.selected=true;j=i;count+;elseactivityi.selected=false;returncount;本讲稿第四十二页，共五十一页2023/4/12计算机算法设计与分析43贪心算法能够得到活动安排问题的最优解n设活动集合E=1,2,n已按结束时间的非减顺序排列，活动1具有最早结束时间。n首先必定有最优解包含活动1。否则设A是E的最优解，且A中最早结束的活动是k。若k1，则活动1必与A中除k以外的活动相容。令

32、B=Ak1，则B也是最优解。n进一步，假设A是原问题的包含活动1的最优解，则A=A1是活动集合E=iE且sif1的一个最优解。反之，如果能够找到E的一个解B，它包含了比A更多的活动，则将活动1加入到B中将产生E的一个解B，它包含比A更多的活动。这与假设矛盾。n因此，所做的每一步贪心选择都将产生一个比原问题规模更小的具有相同特征的子问题。由数学归纳法可知，贪心法得到的是最优解。本讲稿第四十三页，共五十一页2023/4/12计算机算法设计与分析44算法复杂性分析n算法由两部分组成：n第一部分是排序，时间复杂度为O(nlogn)；n第二部分是选择合适的活动，是一个定长循环，时间复杂度为O(n)；n故

33、总的时间复杂度为O(nlogn)。本讲稿第四十四页，共五十一页2023/4/12计算机算法设计与分析45最优装载问题n有一批集装箱要装上一艘载重为C的轮船。其中集装箱i的重量为Wi。假定装载体积不受限制，要将尽可能多(这个多，是指的货物数目)的集装箱装上轮船。n该问题的形式化描述为：有约束条件其中，xi=0表示不装入集装箱，xi=1反之。本讲稿第四十五页，共五十一页2023/4/12计算机算法设计与分析46最优装载问题的贪心算法n基本思想：这个题目比较简单，可以用贪心法求解。每次采用重量最轻者优先装入的贪心选择策略 本讲稿第四十六页，共五十一页2023/4/12计算机算法设计与分析47最优装载

34、贪心算法的实现typedef struct float w;/货物的重量 int number;/货物的编号 bool selected;/货物是否被装载Goods;int loading(float C,Goods goods,int n)/C是载重量，数组goods记录每件货物的有关信息 float sum=0;int i=0；bool excess=false;QuickSort(goods,n);/按货物重量升序排列 while(!excess&in)if(goodsi.w+sumn，mn。n由于货物是升序排列，显然有wrwi，n故有S(x1,x2,xi-1，xi+1,xn，xr)S(

35、A)，S(A)表示A解的总重量。n又由已知条件可得：S(A)+wmC，所以有S(B)C，故B不是可行解。所以不存在比A更优的解。本讲稿第四十八页，共五十一页2023/4/12计算机算法设计与分析49算法复杂性分析n很容易看出，算法主要的时间消耗在排序上，时间复杂度也和排序相同，是O(nlogn)。本讲稿第四十九页，共五十一页2023/4/12计算机算法设计与分析50贪心算法小结n贪心算法每次选择目前最优的解，即通过一系列局部最优来获得整体最优。n贪心算法只有在具有贪心选择性质时才能保证获得整体最优。n证明贪心选择性质：第一个选择是对的；在作出贪心选择后原问题转化为同样的子问题；由归纳法知问题具有贪心选择性质。n若原问题是求带权拟阵的最优独立子集问题，则必满足贪心选择性质。本讲稿第五十页，共五十一页作业：n第三章课后习题1，5，6，9，11-15任选两题。2023/4/12计算机算法设计与分析51本讲稿第五十一页，共五十一页