ACM程序设计基础之图论

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,ACM,程序设计之贪心算法,贪心法的设计思想,贪心法的求解过程,贪心法的基本要素,贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。换言之，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。,这种局部最优选择并不总能获得整体最优解（,Optimal Solution,），,但通常能获得近似最优解（,Near-Optimal Solution,）。,1,贪心法的设计思想,例：用贪心法求解付款问题。,假设有面值为,5,元、,2,元、,1,元、,5,角、,2,角、,1,角的货币，需要找给顾客,4,元,6,角现金，为使付出,的货币的数量最少，首先选出,1,张面值不超过,4,元,6,角的最大面值的货币，即,2,元，再选出,1,张面值不超过,2,元,6,角的最大面值的货币，即,2,元，再选出,1,张面值不超过,6,角的最大面值的货币，即,5,角，再选出,1,张面值不超过,1,角的最大面值的货币，即,1,角，总共付出,4,张货币。,在付款问题每一步的贪心选择中，在不超过应付款金额的条件下，只选择面值最大的货币，而不去考虑在后面看来这种选择是否合理，而且它还不会改变决定：一旦选出了一张货币，就永远选定。付款问题的贪心选择策略是尽可能使付出的货币最快地满足支付要求，其目的是使付出的货币张数最慢地增加，这正体现了贪心法的设计思想。,贪心法求解的问题的特征：,（,1,）,最优子结构性质,当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质，也称此问题满足最优性原理。,（,2,）,贪心选择性质,所谓贪心选择性质是指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到。,动态规划法通常以自底向上的方式求解各个子问题，而贪心法则通常以自顶向下的方式做出一系列的贪心选择。,2,贪心法的求解过程,用贪心法求解问题应该考虑如下几个方面：,（,1,）,候选集合,C,：,为了构造问题的解决方案，有一个候选集合,C,作为问题的可能解，即问题的最终解均取自于候选集合,C,。,例如，在付款问题中，各种面值的货币构成候选集合。,（,2,）,解集合,S,：,随着贪心选择的进行，解集合,S,不断扩展，直到构成一个满足问题的完整解。例如，在付款问题中，已付出的货币构成解集合。,（,3,）,解决函数,solution,：,检查解集合,S,是否构成问题的完整解。例如，在付款问题中，解决函数是已付出的货币金额恰好等于应付款。,（,4,）,选择函数,select,：,即贪心策略，这是贪心法的关键，它指出哪个候选对象最有希望构成问题的解，选择函数通常和目标函数有关。例如，在付款问题中，贪心策略就是在候选集合中选择面值最大的货币。,（,5,）,可行函数,feasible,：,检查解集合中加入一个候选对象是否可行，即解集合扩展后是否满足约束条件。例如，在付款问题中，可行函数是每一步选择的货币和已付出的货币相加不超过应付款。,贪心法的一般过程,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;,例,1,、 活动安排问题,活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。,例,1,、活动安排问题,设有,n,个活动的集合,E=1,2,n,，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动,i,都有一个要求使用该资源的起始时间,si,和一个结束时间,fi,且,si,fi,。如果选择了活动,i,，则它在半开时间区间,si,fi,),内占用资源。若区间,si,fi,),与区间,sj,fj,),不相交，则称活动,i,与活动,j,是相容的。也就是说，当,si,fj,或,sj,fi,时，活动,i,与活动,j,相容。,例,1,、,活动安排问题,在下面所给出的解活动安排问题的贪心算法,greedySelector,:,public static,int,greedySelector,(,int, s,int, f,boolean,a),int,n=s.length-1;,a1=true;,int,j=1;,int,count=1;,for (,int,i=2;i=fj) ,ai=true;,j=i;,count+;,else ai=false;,return count;,各活动的起始时间和结束时间存储于数组,s,和,f,中且按结束时间的非减序排列,例,1,、,活动安排问题,由于输入的活动以其完成时间的,非减序,排列，所以算法,greedySelector,每次总是选择,具有最早完成时间,的相容活动加入集合,A,中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是,使剩余的可安排时间段极大化,，以便安排尽可能多的相容活动。,算法,greedySelector,的效率极高。当输入的活动已按结束时间的非减序排列，算法只需,O(n),的时间安排,n,个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用,O(,nlogn,),的时间重排。,例,1,、活动安排问题,例：,设待安排的,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,例,1,、,活动安排问题,算法,greedySelector,的计算过程,如左图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合,A,的活动，而空白长条表示的活动是当前正在检查相容性的活动。,例,1,、,活动安排问题,若被检查的活动,i,的开始时间,Si,小于最近选择的活动,j,的结束时间,fi,，则不选择活动,i,，否则选择活动,i,加入集合,A,中。,贪心算法并不总能求得问题的,整体最优解,。但对于活动安排问题，贪心算法,greedySelector,却总能求得的整体最优解，即它最终所确定的相容活动集合,A,的规模最大。这个结论可以用数学归纳法证明。,3,、贪心算法的基本要素,对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢,?,这个问题很难给予肯定的回答。,但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有,2,个重要的性质：,贪心选择性质,和,最优子结构性质,。,3,贪心算法的基本要素,1.,贪心选择性质,所谓,贪心选择性质,是指所求问题的,整体最优解,可以通过一系列,局部最优,的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。,动态规划算法通常以,自底向上,的方式解各子问题，而贪心算法则通常以,自顶向下,的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。,对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。,3,贪心算法的基本要素,2.,最优子结构性质,当一个问题的最优解包含其子问题的最优解时，称此问题具有,最优子结构性质,。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。,贪心与动态规划,【,例,】,在一个,NM,的方格阵中，每一格子赋予一个数（即为权）。规定每次移动时只能向上或向右。现试找出一条路径，使其从左下角至右上角所经过的权之和最大。,贪心：,1 3 4 6,动规：,1 2 10 6,局部最优解,VS,全局最优解,3,4,6,1,2,10,例,2,、,背包问题,给定,n,种物品和一个容量为,C,的背包，物品,i,的重量是,w,i,，,其价值为,v,i,，,背包问题是如何选择装入背包的物品，使得装入背包中物品的总价值最大,?,0-1,背包问题：,给定,n,种物品和一个背包。物品,i,的重量是,Wi,，其价值为,Vi,，背包的容量为,C,。应如何选择装入背包的物品，使得装入背包中物品的总价值最大,?,在选择装入背包的物品时，对每种物品,i,只有,2,种选择，即装入背包或不装入背包。不能将物品,i,装入背包多次，也不能只装入部分的物品,i,。,背包问题：,与,0-1,背包问题类似，所不同的是在选择物品,i,装入背包时，,可以选择物品,i,的一部分,，而不一定要全部装入背包，,1in,。,这,2,类问题都具有,最优子结构,性质，极为相似，但背包问题可以用贪心算法求解，而,0-1,背包问题却不能用贪心算法求解。,于是，背包问题归结为寻找一个满足约束条件式,7.1,，并使目标函数式,7.2,达到最大的解向量,X,=(,x,1,x,2, ,x,n,),。,设,x,i,表示物品,i,装入背包的情况，根据问题的要求，有如下约束条件和目标函数：,（式,7.1,）,（式,7.2,）,至少有三种看似合理的贪心策略：,（,1,）选择,价值最大,的物品，因为这可以尽可能快地增加背包的总价值。但是，虽然每一步选择获得了背包价值的极大增长，但背包容量却可能消耗得太快，使得装入背包的物品个数减少，从而不能保证目标函数达到最大。,（,2,）选择,重量最轻,的物品，因为这可以装入尽可能多的物品，从而增加背包的总价值。但是，虽然每一步选择使背包的容量消耗得慢了，但背包的价值却没能保证迅速增长，从而不能保证目标函数达到最大。,（,3,）选择,单位重量价值最大,的物品，在背包价值增长和背包容量消耗两者之间寻找平衡。,应用第三种贪心策略，每次从物品集合中选择单位重量价值最大的物品，如果其重量小于背包容量，就可以把它装入，并将背包容量减去该物品的重量，然后我们就面临了一个最优子问题,它同样是背包问题，只不过背包容量减少了，物品集合减少了。因此背包问题具有最优子结构性质。,120 50,背包,180 190 200,(a),三个物品及背包,(b),贪心策略,1 (c),贪心策略,2 (d),贪心策略,3,50,30,10,20,20,30,20/30,20,10,10/20,30,10,例如，有,3,个物品，其重量分别是,20, 30, 10,，价值分别为,60, 120, 50,，背包的容量为,50,，应用三种贪心策略装入背包的物品和获得的价值如图所示。,设背包容量为,C,，,共有,n,个物品，物品重量存放在数组,wn,中，价值存放在数组,vn,中，问题的解存放在数组,xn,中。,1,改变数组,w,和,v,的排列顺序，使其按单位重量价值,vi/wi,降序排列；,2,将数组,xn,初始化为,0,；,/,初始化解向量,3,i=1;,循环直到,(wiC),1,xi=1; /,将第,i,个物品放入背包,2,C=C-wi;,3,i+;,5. xi=C/wi;,伪代码,算法的时间主要消耗在将各种物品依其单位重量的价值从大到小排序。因此，其时间复杂性为,O,(,n,log2,n,),。,对于,0-1,背包问题,，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑,0-1,背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用,动态规划算法,求解的另一重要特征。,实际上也是如此，动态规划算法的确可以有效地解,0-1,背包问题。,例,3,最优装载,有一批集装箱要装上一艘载重量为,c,的轮船。其中集装箱,i,的重量为,Wi,。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。,1.,算法描述,最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。具体算法描述如下页。,最优装载,public static float,loading,(float c, float w,int, x),int,n=w.length;,Element d = new Element n;,for (,int,i = 0; i n; i+),di = new Element(wi,i);,MergeSort,.,mergeSort,(d);,float opt=0;,for (,int,i = 0; i n; i+) xi = 0;,for (,int,i = 0; i n i+) ,xdi.i = 1;,opt+=di.w;,c -= di.w;,return opt;,最优装载,2.,贪心选择性质,可以证明最优装载问题具有贪心选择性质,。,3.,最优子结构性质,最优装载问题具有最优子结构性质。,由最优装载问题的贪心选择性质和最优子结构性质，容易证明算法,loading,的正确性。,算法,loading,的主要计算量在于将集装箱依其重量从小到大排序，故算法所需的计算时间为,O(,nlogn,),。,例,4,、 哈夫曼编码,哈夫曼编码,是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在,20%,90%,之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用,0,，,1,串表示各字符的最优表示方式。,给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。,1.,前缀码,对每一个字符规定一个,0,1,串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀。这种编码称为,前缀码,。,例,4,、,哈夫曼编码,编码的前缀性质可以使译码方法非常简单。,表示,最优前缀码,的二叉树总是一棵,完全二叉树,，即树中任一结点都有,2,个儿子结点。,平均码长,定义为：,使平均码长达到最小的前缀码编码方案称为给定编码字符集,C,的,最优前缀码,。,例,4,、哈夫曼编码,2.,构造哈夫曼编码,哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为,哈夫曼编码,。,哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树,T,。,算法以,|C|,个叶结点开始，执行,|C|,1,次的“合并”运算后产生最终所要求的树,T,。,例,4,、哈夫曼编码,在书上给出的算法,huffmanTree,中，编码字符集中每一字符,c,的频率是,f(c),。,以,f,为键值的优先队列,Q,用在,贪心选择,时有效地确定算法当前要合并的,2,棵具有最小频率的树。一旦,2,棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的,2,棵树的频率之和，并将新树插入优先队列,Q,。经过,n,1,次的合并后，优先队列中只剩下一棵树，即所要求的树,T,。,算法,huffmanTree,用最小堆实现优先队列,Q,。初始化优先队列需要,O(n),计算时间，由于最小堆的,removeMin,和,put,运算均需,O(,logn,),时间，,n,1,次的合并总共需要,O(,nlogn,),计算时间。因此，关于,n,个字符的哈夫曼算法的,计算时间,为,O(,nlogn,),。,例,4,、哈夫曼编码,3.,哈夫曼算法的正确性,要证明哈夫曼算法的正确性，只要证明最优前缀码问题具有,贪心选择性质,和,最优子结构性质,。,(1),贪心选择性质,(2),最优子结构性质,例,5,、 单源最短路径,给定带权有向图,G =(V,E),，其中每条边的权是非负实数。另外，还给定,V,中的一个顶点，称为,源,。现在要计算从源到所有其他各顶点的,最短路长度,。这里路的长度是指路上各边权之和。这个问题通常称为,单源最短路径问题,。,1.,算法基本思想,Dijkstra,算法是解单源最短路径问题的贪心算法。,例,5,、 单源最短路径,其,基本思想,是，设置顶点集合,S,并不断地作,贪心选择,来扩充这个集合。一个顶点属于集合,S,当且仅当从源到该顶点的最短路径长度已知。,初始时，,S,中仅含有源。设,u,是,G,的某一个顶点，把从源到,u,且中间只经过,S,中顶点的路称为从源到,u,的特殊路径，并用数组,dist,记录当前每个顶点所对应的最短特殊路径长度。,Dijkstra,算法每次从,V-S,中取出具有最短特殊路长度的顶点,u,，将,u,添加到,S,中，同时对数组,dist,作必要的修改。一旦,S,包含了所有,V,中顶点，,dist,就记录了从源到所有其他顶点之间的最短路径长度。,例,5,、 单源最短路径,例如,，对右图中的有向图，应用,Dijkstra,算法计算从源顶点,1,到其他顶点间最短路径的过程列在下页的表中。,例,5,、,单源最短路径,迭代,S,u,dist2,dist3,dist4,dist5,初始,1,-,10,maxint,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,Dijkstra,算法的迭代过程：,5,单源最短路径,2.,算法的正确性和计算复杂性,(1),贪心选择性质,(2),最优子结构性质,(3),计算复杂性,对于具有,n,个顶点和,e,条边的带权有向图，如果用带权邻接矩阵表示这个图，那么,Dijkstra,算法的主循环体需要 时间。这个循环需要执行,n-1,次，所以完成循环需要 时间。算法的其余部分所需要时间不超过 。,6,最小生成树,设,G =(V,E),是无向连通带权图，即一个,网络,。,E,中每条边,(v,w),的权为,cvw,。如果,G,的子图,G,是一棵包含,G,的所有顶点的树，则称,G,为,G,的生成树。生成树上各边权的总和称为该生成树的,耗费,。在,G,的所有生成树中，耗费最小的生成树称为,G,的,最小生成树,。,网络的最小生成树在实际中有广泛应用。,例如,，在设计通信网络时，用图的顶点表示城市，用边,(v,w),的权,cvw,表示建立城市,v,和城市,w,之间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案。,6,最小生成树,1.,最小生成树性质,用贪心算法设计策略可以设计出构造最小生成树的有效算法。本节介绍的构造最小生成树的,Prim,算法,和,Kruskal,算法,都可以看作是应用贪心算法设计策略的例子。尽管这,2,个算法做贪心选择的方式不同，它们都利用了下面的,最小生成树性质,：,设,G=(V,E),是连通带权图，,U,是,V,的真子集。如果,(u,v),E,，且,u,U,，,v,V-U,，且在所有这样的边中，,(u,v),的权,cuv,最小，那么一定存在,G,的一棵最小生成树，它以,(u,v),为其中一条边。这个性质有时也称为,MST,性质,。,6,最小生成树,2.Prim,算法,设,G=(V,E),是连通带权图，,V=1,2,n,。,构造,G,的最小生成树的,Prim,算法的,基本思想,是：首先置,S=1,，然后，只要,S,是,V,的真子集，就作如下的,贪心选择,：,选取满足条件,i,S,，,j,V-S,，且,cij,最小的边，将顶点,j,添加到,S,中。这个过程一直进行到,S=V,时为止。,在这个过程中选取到的所有边恰好构成,G,的一棵,最小生成树,。,6,最小生成树,利用最小生成树性质和数学归纳法容易证明，上述算法中的,边集合,T,始终包含,G,的某棵最小生成树中的边,。因此，在算法结束时，,T,中的所有边构成,G,的一棵最小生成树。,例如,，对于右图中的带权图，按,Prim,算法,选取边的过程如下页图所示。,6,最小生成树,6,最小生成树,在上述,Prim,算法中，还应当考虑,如何有效地找出满足条件,i,S,j,V-S,，且权,cij,最小的边,(i,j),。实现这个目的的较简单的办法是设置,2,个数组,closest,和,lowcost,。,在,Prim,算法执行过程中，先找出,V-S,中使,lowcost,值最小的顶点,j,，然后根据数组,closest,选取边,(j,closestj,),，最后将,j,添加到,S,中，并对,closest,和,lowcost,作必要的修改。,用这个办法实现的,Prim,算法所需的,计算时间,为,6,最小生成树,3.,Kruskal,算法,Kruskal,算法构造,G,的最小生成树的,基本思想,是，首先将,G,的,n,个顶点看成,n,个孤立的连通分支。将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接,2,个不同的连通分支：当查看到第,k,条边,(v,w),时，如果端点,v,和,w,分别是当前,2,个不同的连通分支,T1,和,T2,中的顶点时，就用边,(v,w),将,T1,和,T2,连接成一个连通分支，然后继续查看第,k+1,条边；如果端点,v,和,w,在当前的同一个连通分支中，就直接再查看第,k+1,条边。这个过程一直进行到只剩下一个连通分支时为止。,6,最小生成树,例如，,对前面的连通带权图，按,Kruskal,算法顺序得到的最小生成树上的边如下图所示。,6,最小生成树,关于,集合的一些基本运算,可用于实现,Kruskal,算法。,按权的递增顺序查看等价于对,优先队列,执行,removeMin,运算。可以用,堆,实现这个优先队列。,对一个由连通分支组成的集合不断进行修改，需要用到抽象数据类型,并查集,UnionFind,所支持的基本运算。,当图的边数为,e,时，,Kruskal,算法所需的,计算时间,是 。当 时，,Kruskal,算法比,Prim,算法差，但当 时，,Kruskal,算法却比,Prim,算法好得多。,键盘输入一个高精度的正整数,N,，,去掉其中任意,S,个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的,N,和,S,，,寻找一种方案使得剩下的数字组成的新数最小。,输入数据均不需判错。输出应包括所去掉的数字的位置和组成的新的正整数,例,7,、删数游戏,问题分析,在位数固定的前提下，让高位的数字尽量小其值就较小，依据此贪婪策略就可以解决这个问题。,怎么样根据贪婪策略删除数字呢？总目标是删除高位较大的数字，具体地相邻两位比较若高位比低位大则删除高位。我们通过,“,枚举归纳,”,设计算法的细节，看一个实例（,s=3,） ：,n1=,“,1 2 4 3 5 8 6 3”,4,比,3,大,删除,“,1 2 3 5 8 6 3,”,8,比,6,大,删除,“,1 2 3 5 6 3,”,6,比,3,大,删除,“,1 2 3 5 3,”,问题分析,只看这个实例，有可能,“,归纳,”,出不正确的算法，先看下一个实例，我们再进一步解释：,n2=”2 3 1 1 8 3”,3,比,1,大,删除,“,2 1 1 8 3”,2,比,1,大,删除,“,1 1 8 3”,8,比,3,大,删除,“,1 1 3”,再看以下两个实例又可总结出一些需要算法特殊处理的情况。,n3=”1 2 3 4 5 6 7” s=3,由这个实例看出，经过对,n3,相邻比较一个数字都没有删除，这就要考虑将后三位进行删除，当然还有可能，在相邻比较的过程中删除的位数小于,s,时，也要进行相似的操作。,n4=”1 2 0 0 8 3”,3,比,0,大,删除,“,1 0 0 8 3”,2,比,0,大,删除,“,0 0 8 3”,8,比,3,大,删除,“,0 0 3”,得到的新数数据是,3,由这个实例子又能看出，当删除掉一些数字后，结果的高位有可能出现数字,“,0,”,，直接输出这个数据不合理，要将结果中高位的数字,“,0,”,全部删除掉，再输出。特别地还要考虑若结果串是,“,0000,”,时，不能将全部,“,0,”,都删除，而要保留一个,“,0,”,最后输出。,由此可以看出进行算法设计时，从具体到抽象的归纳一定要选取大量不同的实例，充分了解和体会解决问题的过程、规律和各种不同情况，才能设计出正确的算法。,设计一个算法， 把一个真分数表示为埃及分数之和的形式。所谓埃及分数，是指分子为,1,的形式。如：,7/8=1/2+1/3+1/24,。,取数游戏,有,2,个人轮流取,2n,个数中的,n,个数，取数之和大者为胜。请编写算法，让先取数者胜，模拟取数过程。,