第三章贪心算法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,计算机算法设计与分析,*,2026/3/6 周五,计算机算法设计与分析,1,第三章,贪心算法,2026/3/6 周五,计算机算法设计与分析,2,找硬币,假设有四种硬币，面值分别为,二角五分,一角,五分,一分,现在要找给某顾客六角三分钱，哪种找钱方法拿出的硬币个数最少呢？,二角五分,二角五分,一角,一分,一分,一分,首先选出一个面值不超过六角三分的最大硬币，即二角五分；然后从六角三分中减去二角五分，剩下三角八分；再选出一个面值不超过三角八分的最大硬币，即又一个二角五分，如此一直做下去。这种方法实际上就是贪心算法。,2026/3/6 周五,计算机算法设计与分析,3,再找硬币,若硬币的面值改为一分、五分和一角一分,3,种，而要找个顾客的是一角五分钱。,还用贪心算法，将找个顾客,1,个一角一分的硬币和,4,个一分的硬币。,然而，,3,个五分的硬币显然才是最好的找法。,2026/3/6 周五,计算机算法设计与分析,4,贪心算法的特点,贪心算法总是作出在当前来看是最好的选择。,就是说，贪心算法并不从整体最优上来考虑，所作出的选择只是某种意义上的局部最优选择。,当然希望贪心算法得到的最终结果是最优的。,可是贪心算法并不能保证最终结果是最优的。,不过，在许多情况下，应用贪心算法能够得到整体最优解；并且在一些情况下，即使得到的不是最优解，也是一个很好的近似解。,2026/3/6 周五,计算机算法设计与分析,5,贪心算法的一般框架,GreedyAlgorithm(parameters),初始化；,重复执行以下的操作：,选择当前可以选择的,(,相容,),最优解；,将所选择的当前解加入到问题的解中；,直至满足问题求解的结束条件。,2026/3/6 周五,计算机算法设计与分析,6,最小生成树,设,G=(V,E),是一个无向连通带权图，即一个网络。,E,的每条边,(v,w),的权为,cvw,。,如果,G,的一个子图,G,是一棵包含,G,的所有顶点的树，则称,G,为,G,的生成树。,生成树的各边的权的总和称为该生成树的耗费。,在,G,的所有生成树中，耗费最小的生成树称为,G,的最小,(,优,),生成树。,2026/3/6 周五,计算机算法设计与分析,7,树的基本性质,连通无回路的图,G,称为树。,树是点比边多一的连通图，,G,连通且,q=p1,。,树是点比边多一的无回路图：,G,无回路且,q=p1,树若添条边就有回路：,G,无回路，但对任意的,u,vV(G),，,若,uv,E(G),，,则,G+uv,中恰有一条回路,树若减条边就不连通：,G,连通，但对,eE(G),Ge,不连通。,n,个顶点的连通图的生成树含有,n 1,条边。,若,G,的任何最小生成树都不包含,e,1,。设,T,为,G,的最小生成树，,e,1,T,。于是,T+e,1,是一个有回路的图且该回路中包含,e,1,。该回路中必有条不是,e,的边,e,i,。令,T=T+e,1,e,i,。,T,也是,G,的生成树。又,c(T)=c(T)+c(e,1,)c(e,i,),，,c(e,1,)c(e,i,),，从而,c(T)c(T),，,T,是,G,的最小生成树且含有边,e,1,。矛盾。故必定有图,G,的最小生成树包含了,e,1,。,2026/3/6 周五,计算机算法设计与分析,8,最小生成树的贪心选择性质,令,G,中权最小的边为,e,1,。首先必定有图,G,的一棵最小生成树包含了,e,1,。,选定第一条边,e,1,以后，该如何选择第二条边呢？,依据各条边的权重，依次选出权重较轻的,n 1,条边。这,n 1,条边必定包括了,G,的,n,个顶点。这样就得到了,G,的一棵最小生成树。,这样做是否可以呢？,不行！因为不能保证这,n 1,条边构成树？,要保证这,n 1,条边构成树，必须使这,n 1,条边是连通的或者是无回路的。,Prim,算法的做法：在保证连通的前提下依次选出权重较小的,n 1,条边（在实现中体现为,n,个顶点的选择）。,Kruskal,算法的做法：在保证无回路的前提下依次选择权重较小的,n 1,条边。,2026/3/6 周五,计算机算法设计与分析,9,Prim,算法,基本思想：在保证连通的前提下依次选出权重较小的,n 1,条边。,G=(V,E),为无向连通带权图，令,V=1,2,n,。,设置一个集合,S,，初始化,S=1,，,T=,。,贪心策略：如果,VS,中的顶点,j,与,S,中的某个点,i,连接且,(i,j),的权重最小，于是就选择,j(,将,j,加入,S),，并将,(i,j),加入,T,中。,重复执行贪心策略，直至,VS,为空。,2026/3/6 周五,计算机算法设计与分析,10,Prim,算法中的数据结构,图用连接矩阵,Cij,给出，即,Cij,为结点,i,到结点,j,的权重。,标志数组,Si,指示顶点,i,是否已经加入到,S,中。,为了有效地找出,VS,中满足与,S,中的某个点,i,连接且,(i,j),权重最小的顶点,j,，对其中的每个顶点,j,设立两个数组,closestj,和,lowcostj,：,closestj,是,S,中与,j,最近的顶点，,(closestj,j),即为选中的边，而,lowcostj,是相应边的权重。,2026/3/6 周五,计算机算法设计与分析,11,Prim,算法的实现,Prim(int n,Type*c),初始化：结点,1,放入,S,；并初始化,lowcost,和,closest,；,执行以下操作,n1,次：,依据,lowcost,找出与,S,最近的点,j,并放入,S,；,调整,lowcost,和,closest,；,int j=1;sj=true;,for(int i=2;i=n;i+),closesti=1;lowcosti=c1i;si=false;,for(i=1;i n;i+)min=inf;,for(int k=2;k=n;k+),if(lowcostkmin&!sk),min=lowcostk;j=k,sj=true;,s,中仅加入了一个新成员,j,，因此只需要依据结点,j,调整,lowcost,和,closest,；,for(k=2;k=n;k+),if(cjk lowcostk&!sk),lowcostk=cjk;closestk=j,2026/3/6 周五,计算机算法设计与分析,12,Prim,算法的示例,给定一个连通带权图如下：,1,2,3,4,5,6,1,6,5,5,5,3,6,6,2,4,初始时,S=1,，,T=,；,1,第一次选择：,(1,3),权最小,S=1,3,T=(1,3),；,3,第二次选择：,(3,6),权最小,S=1,3,6,，,T=(1,3),(3,6),；,6,第三次选择：,(6,4),权最小,S=1,3,6,4,，,T=(1,3),(3,6),(6,4),；,4,第四次选择：,(2,3),权最小,S=1,3,6,4,2,，,T=(1,3),(3,6),(6,4),(2,3),；,2,第五次选择：,(5,2),权最小,S=1,3,6,4,2,5,，,T=(1,3),(3,6),(6,4),(3,2)(2,5),；,5,2026/3/6 周五,计算机算法设计与分析,13,Kruskal,算法,基本思想：在保证无回路的前提下依次选出权重较小的,n 1,条边。,贪心策略：如果,(i,j),是,E,中尚未被选中的边中权重最小的，并且,(i,j),不会与已经选择的边构成回路，于是就选择,(i,j),。,问题：如何知道,(i,j),不会造成回路？,若边,(i,j),的两个端点,i,和,j,属于同一个连通分支，则选择,(i,j),会造成回路，反之则不会造成回路,因此初始时将图的,n,个顶点看成,n,个孤立分支。,2026/3/6 周五,计算机算法设计与分析,14,Kruskal,算法的数据结构,结构数组,e,表示图的边，,ei.u,、,ei.v,和,ei.w,分别表示边,i,的两个端点及其权重。,函数,Sort(e,w),将数组,e,按权重,w,从小到大排序。,一个连通分支中的顶点表示为一个集合。,函数,Initialize(n),将每个顶点初始化为一个集合,函数,Find(u),给出顶点,u,所在的集合。,函数,Union(a,b),给出集合,a,和集合,b,的并集。,重载算符,!=,判断集合的不相等。,2026/3/6 周五,计算机算法设计与分析,15,Kruskal,算法的实现,Kruskal(int n,*e),Sort(e,w);/,将边按权重从小到大排序,initialize(n);/,初始时每个顶点为一个集合,k=1;/k,累计已选边的数目，,j=1;/j,为所选的边在,e,中的序号,while(k n)/,选择,n 1,条边,a=Find(ej.u);b=Find(ej.v);,/,找出第,j,条边两个端点所在的集合,if(a!=b)Tk=j;Union(a,b);k=k+1;,/,若不同，第,j,条边放入树中并合并这两个集合,j+/,继续考察下一条边,2026/3/6 周五,计算机算法设计与分析,16,Kruskal,算法的例子,1,2,3,4,5,6,1,6,5,5,5,3,6,6,2,4,1,3,1,4,6,2,2,5,3,3,6,4,1,4,5,2,3,5,3,4,5,1,2,6,3,5,6,5,6,6,初始时为,6,个孤立点,1,2,3,4,5,6,选择了边,1,，于是,1,、,3,点合并为同一个集合。,选择了边,2,，于是,4,、,6,点合并为同一个集合。,选择了边,3,，于是,2,、,5,点合并为同一个集合。,选择了边,4,，于是,1,、,3,、,4,、,6,点合并为同一个集合,考察边,5,，因为,1,、,4,点属于同一个集合，被放弃。,选择边,6,，于是,1,、,3,、,4,、,6,、,2,、,5,点属于同一个集合。,已经选择边了,n1,条边，算法结束。结果如图所示。,u,v,w,2026/3/6 周五,计算机算法设计与分析,17,Prim,与,Kruskal,两算法的复杂性,Prim,算法为两重循环，外层循环为,n,次，内层循环为,O(n),，因此其复杂性为,O(n,2,),。,Kruskal,算法中，设边数为,e,，则边排序的时间为,O(eloge),，最多对,e,条边各扫描一次，每次确定边的时间为,O(loge),，所以整个时间复杂性为,O(eloge),。,当,e=,(n,2,),时，,Kruskal,算法要比,Prim,算法差；,当,e=,(n,2,),时，,Kruskal,算法比,Prim,算法好得多。,2026/3/6 周五,计算机算法设计与分析,18,贪心算法也能获得最优解,用,Kruskal,算法得到的,生成树,T*,必是最优树。,证明：,设,T*,不是最优，令,T,是与,T*,有,k,条共同边的最优树且,k,是最优树与,T*,共有边数的,最大值,TT*,e,k+1,:e,k+1,E(T),且,e,k+1,E(T*),。,则,T+e,k+1,含唯一回路,C,，,C,必有条边,e,k,E(T*),。,令,T=(T+e,k+1,)e,k,w(T)=w(T)+w(e,k+1,)w(e,k,),。,由算法知，,w(e,k+1,),w(e,k,),，,T,是最优树。,但,T,与,T*,有,k+1,条共同边，矛盾。故,T*,是最优,2026/3/6 周五,计算机算法设计与分析,19,0-1,背包问题,给定,n,个物品和一个背包。物品,i,的重量为,w,i,，价值为,v,i,，背包容量为,c,。问如何选择装入背包中的物品，使得装入背包的物品的价值最大？,在装入背包时，每种物品,i,只有两种选择，装入或者不装入，既不能装入多次，也不能只装入一部分。因此，此问题称为,0-1,背包问题。,如果在装入背包时，物品可以切割，即可以只装入一部分，这种情况下的问题称为背包问题。,2026/3/6 周五,计算机算法设计与分析,20,0-1,背包问题不适用贪心算法,背包容量为,50kg,，物品,1,2,和,3,的容量和价值分别为,(10kg,$60),(20kg,$100),和,(30kg,$120),。,单位重量价值最高的为物品,1,，,6$/kg,。但是依照贪心算法首选物品,1,却不能获得最优解：,物品,1,物品,2,物品,1,物品,3,物品,2,物品,3,总价值为,$160,空余,20 kg,总价值为,$180,空余,10 kg,总价值为,$220,没有空余,但是背包问题却是适用贪心算法的。,2026/3/6 周五,计算机算法设计与分析,21,贪心算法的基本要素,贪心算法的基本要素是：,贪心选择性质,。,所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优解的选择，即贪心选择来达到。,贪心选择每次选取当前最优解，因此它依赖以往的选择，而不依赖于将来的选择。,贪心算法通常以自顶向下的方式进行，每次贪心选择就将原问题转化为规模更小的子问题。,2026/3/6 周五,计算机算法设计与分析,22,如何确定贪心选择性质,证明贪心选择将导致整体的最优解：,首先证明存在问题的一个整体最优解必定包含了第一个贪心选择。,然后证明在做了贪心选择后，原问题简化为规模较小的类似子问题，即可继续使用贪心选择。,于是用数学归纳法可证明，经过一系列贪心选择可以得到整体最优解。,2026/3/6 周五,计算机算法设计与分析,23,单源最短路径,给定一个图,G=(V,E),，其中每条边的权是一个非负实数。另外给定,V,中的一个顶点,v,，称为源。求从源,v,到所有其它各个顶点的最短路径。,单源最短路径问题的贪心选择策略：选择从源,v,出发目前用最短的路径所到达的顶点，这就是目前的局部最优解。,1,2,5,4,3,10,20,50,100,30,10,60,赋权图,G,2026/3/6 周五,计算机算法设计与分析,24,单源最短路径的贪心算法,基本思想：首先设置一个集合,S,；用数组,dis,来记录,v,到,S,中各点的目前最短路径长度。然后不断地用贪心选择来扩充这个集合，并同时记录或修订数组,dis,；直至,S,包含所有,V,中顶点。,贪心选择：一个顶点,u,属于,S,当且仅当从,v,到,u,的最短路径长度已知。,初始化：,S,中仅含有源,v,。,2026/3/6 周五,计算机算法设计与分析,25,Dijkstra,算法,Dijkstra,算法的做法是：,由近到远逐步计算，每次最近的顶点的距离就是它的最短路径长度。,然后再从这个最近者出发。即依据最近者修订到各顶点的距离，然后再选出新的最近者。,如此走下去，直到所有顶点都走到。,2026/3/6 周五,计算机算法设计与分析,26,Dijkstra,算法,Procedure Dijkstra,(1)S:=1;/,初始化,S,(2)for i:=2 to n do/,初始化,dis,(3)disi=C1,i;/,初始时为源到顶点,i,一步的距离,(4)for i:=1 to n do,(5),从,V-S,中选取一个顶点,u,使得,disu,最小；,(6),将,u,加入到,S,中；,/,将新的最近者加入,S,(7)for w,V-S do /,依据最近者,u,修订,disw,(8)disw:=min(disw,disu+Cu,w),2026/3/6 周五,计算机算法设计与分析,27,Dijkstra,算法举例,迭代,S u dis2 dis3 dis4 dis5,初始,1 -,10,30 100,1 1,2 2 10 60,30,100,2 1,2,4 4 10,50,30 90,3 1,2,4,3 3 10 50 30,60,4 1,2,4,3,5 5 10 50 30 60,1,2,5,4,3,10,20,50,100,30,10,60,赋权图,G,由数组,disi,可知：从顶点,1,到顶点,2,、,3,、,4,、,5,的最短通路的长度分别为,10,、,50,、,30,和,60,。,2026/3/6 周五,计算机算法设计与分析,28,Dijkstra,算法的贪心选择性质,Dijkstra,算法中所做的贪心选择是：若,u,是,VS,中具有最短路径的特殊顶点，就将,u,选入,S,，并确定了从源到,u,的最短路径长度,disu,。,为什么从源到,u,没有更短的路径呢？,若有，则将如下图所示：,S,v,disu,(,最近距离,),u,x,disx,若该路径经,S,外一点,x,到达,u,，则：,disx+d(x,u),disu,从而,disx,disu,，这与,u,的选取矛盾,2026/3/6 周五,计算机算法设计与分析,29,Dijkstra,算法的计算复杂性,Dijkstra,算法有两层循环，外层循环为,n,次，内层有两个循环：一个是选出最小的,u(,第,5,行,),，另一个是修订,disw(,第,7,、,8,行,),，内层循环的时间为,O(n),。,因此,Dijkstra,算法的时间复杂度为,O(n,2,),。,Dijkstra,算法能求出从源到其它各顶点的最短通路的长度，但是却并没有给出其最短通路。,对,Dijkstra,算法做适当的修改便可求出最短通路。见书上,P37,2026/3/6 周五,计算机算法设计与分析,30,旅行商问题,推销员从某城市出发，遍历,n,个城市最后返回出发城市。设从城市,i,到城市,j,的费用为,c,ij,，如何选择旅行路线使得该推销员此趟旅行的总费用最小,?,图论语言表述：给定,n,个节点简单无向完全图,G=,，,c(i,j),是节点,i,到,j,的代价,(,边权,),。在,G,中求遍历所有节点简单回路,C,，使,C,上所有边权的和最小。,2026/3/6 周五,计算机算法设计与分析,31,旅行商问题分析,1,2,3,4,5,1,1,2,7,5,2,4,4,3,3,1,2,4,3,5,对于,n,个节点的旅行商问题，,n,个节点的任意一个圆排列都是问题的一个可能解。,n,个节点的圆排列有,(n-1)!,个，因此问题归结为在,(n-1)!,个回路中选取最小回路。,是否能够不用,O(n-1)!),时间来求解旅行商问题？,2026/3/6 周五,计算机算法设计与分析,32,旅行商问题的贪心算法,基本思想：首先设置一个集合,Path,和当前节点,v,，然后不断地用贪心选择来扩充这个集合，直至,Path,包含所有,V,中顶点。,贪心选择：如果,VPath,中的顶点,j,是与当前节点,v,相邻接的顶点中边权最小的，于是就选择,j(,将,j,加入,Path),，并将,j,作为新的当前节点。,初始化：,Path,中仅含有源,v,。,2026/3/6 周五,计算机算法设计与分析,33,最临近算法中的数据结构,图用连接矩阵,Wij,给出，即,Wij,为结点,i,到结点,j,的权重。,Path,记录依次连接的城市，,p,记录当前到达的最后一个顶点，,cost,为当前路径长度。,如果节点,k,已经到达，则,arrivedk=true,。,2026/3/6 周五,计算机算法设计与分析,34,旅行商问题的最临近算法,CostType Tray_Greedy(int n,CostType*w,int*path),for(i=1;i=n;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&wpjs,i+1,，所以第,i+1,个活动无法安排，这就必须舍弃第,i+1,个活动，检测第,i+2,个活动,直到第,i+k,个活动的,s,i+k,f,i,，就把此活动安排进来。,2026/3/6 周五,计算机算法设计与分析,41,先将所有活动按照结束时间,fi,递增排序,活动安排的例子,首先选定活动,1,，其结束时间,f1=4,。,然后因,s4=54,，选定活动,4,，这时,f4=7,。,又因,s8=87,，选定活动,8,，这时,f8=11,。,最后因,s11=1211,，选定活动,11,。,最终的活动安排为：,1,、,4,、,8,和,11,。,i,1,2,3,4,5,6,7,8,9,10,11,si,1,3,0,5,3,5,6,8,8,2,12,fi,4,5,6,7,8,9,10,11,12,13,14,2026/3/6 周五,计算机算法设计与分析,42,活动安排贪心算法的实现,typedef struct int number;/,活动的编号,float start;/,活动开始的时间,float end;/,活动结束的时间,Bool selected;/,标记活动是否被选择,Active;,int greedySelector(Active activity,int n),QuitckSort(activity,n);/,将活动按结束时间排序,activity1.selected=true;j=1;count=1;,for(i=2;i=activityj.end),activityi.selected=true;j=i;count+;else activityi.selected=false;,return count;,2026/3/6 周五,计算机算法设计与分析,43,贪心算法能够得到活动安排问题的最优解,设活动集合,E=1,2,n,已按结束时间的非减顺序排列，活动,1,具有最早结束时间。,首先必定有最优解包含活动,1,。否则设,A,是,E,的最优解，且,A,中最早结束的活动是,k,。若,k,1,，则活动,1,必与,A,中除,k,以外的活动相容。令,B=Ak1,，则,B,也是最优解。,进一步，假设,A,是原问题的包含活动,1,的最优解，则,A=A1,是活动集合,E=iE,且,s,i,f,1,的一个最优解。反之，如果能够找到,E,的一个解,B,，它包含了比,A,更多的活动，则将活动,1,加入到,B,中将产生,E,的一个解,B,，它包含比,A,更多的活动。这与假设矛盾。,因此，所做的每一步贪心选择都将产生一个比原问题规模更小的具有相同特征的子问题。由数学归纳法可知，贪心法得到的是最优解。,2026/3/6 周五,计算机算法设计与分析,44,算法复杂性分析,算法由两部分组成：,第一部分是排序，时间复杂度为,O(nlogn),；,第二部分是选择合适的活动，是一个定长循环，时间复杂度为,O(n),；,故总的时间复杂度为,O(nlogn),。,2026/3/6 周五,计算机算法设计与分析,45,最优装载问题,有一批集装箱要装上一艘载重为,C,的轮船。其中集装箱,i,的重量为,Wi,。假定装载体积不受限制，要将尽可能多,(,这个多，是指的货物数目,),的集装箱装上轮船。,该问题的形式化描述为：,有约束条件,其中，,x,i,=0,表示不装入集装箱，,x,i,=1,反之。,2026/3/6 周五,计算机算法设计与分析,46,最优装载问题的贪心算法,基本思想：,这个题目比较简单，可以用贪心法求解。每次采用重量最轻者优先装入的贪心选择策略,2026/3/6 周五,计算机算法设计与分析,47,最优装载贪心算法的实现,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,。,由于货物是升序排列，显然有,w,r,w,i,，,故有,S(x,1,x,2,x,i-1,，,x,i+1,x,n,，,x,r,)S(A),，,S(A),表示,A,解的总重量。,又由已知条件可得：,S(A)+w,m,C,，所以有,S(B)C,，故,B,不是可行解。所以不存在比,A,更优的解。,2026/3/6 周五,计算机算法设计与分析,49,算法复杂性分析,很容易看出，算法主要的时间消耗在排序上，时间复杂度也和排序相同，是,O(nlogn),。,2026/3/6 周五,计算机算法设计与分析,50,贪心算法小结,贪心算法每次选择目前最优的解，即通过一系列局部最优来获得整体最优。,贪心算法只有在具有贪心选择性质时才能保证获得整体最优。,证明贪心选择性质：第一个选择是对的；在作出贪心选择后原问题转化为同样的子问题；由归纳法知问题具有贪心选择性质。,若原问题是求带权拟阵的最优独立子集问题，则必满足贪心选择性质。,作业：,第三章课后习题,1,，,5,，,6,，,9,，,11-15,任选两题。,2026/3/6 周五,计算机算法设计与分析,51,