贪心法(The Greedy Method).ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,贪心法（,The Greedy Method,）,宫秀军,天津大学计算机科学与技术学院,gongxj,problem,),贪心算法基本原理,(,The principle of greedy method,),贪心算法应用,货箱装船问题（,Container Loading,),背包问题（,Knapsack Problem,）,拓扑排序问题,(,Topological Sorting,),最短路径问题,(,Shortest Path,),最小代价生成树,(,Minimum Spanning Tree,),本章小结,13.1,优化问题,一个优化问题可以描述如下,:,问题的解可表示为一复杂的结构，例如元组形式,约束条件,(,结构性的约束条件,使约束条件为,true,的元组称为可行解（,feasible solution,）,目标函数,优化解即指使目标函数极大化,(,或极小化,),的可行解，对应的目标函数值称为优化值。,很多优化问题是,NP,难度问题，迄今找不到它们的多项式算法。所以计算上可行的方法就是求其近似解。贪心法是求近似算法的主要途径之一。,例,13.1,Thirsty Baby,有一个聪明的婴儿，她可能得到的饮料包括一桶水、一桶牛奶、多罐不同种类的果汁、许多不同的装在瓶子或罐子中的苏打水。假定婴儿可得到,n,种不同的饮料。根据以前关于这,n,种饮料的不同体验，婴儿知道其中那些饮料更合自己的胃口。因此，婴儿为每一种饮料赋予一个满意度值,s,i,：饮用,1,盎司第,i,种饮料，满意度,s,i,。,设第,i,种饮料有,a,i,盎司，婴儿共需喝,t,盎司饮料,例,13.1,Thirsty Baby,设,x,i,为第,i,种饮料的饮用量，假定满意程度是可加的，则最满意的选择是极大化,该优化问题可表示如下,约束条件,目标函数,例,13.2,loading Problem,一艘船准备用来装载货物,所有货物都放在集装箱中。设第,i,个集装箱的重量为,w,i,（,1,i,n,），,船的最大载重量为,c,，,试设计一装载方法使得装入的集装箱数目最多。,例,13.2,Loading Problem,用,n,维布尔向量代表一种装箱方案,约束条件,目标函数,极大化目标函数,例,13.3,最小成本通信网络,城市之间的通信网络应是以这些城市为顶点的连通图,图的每条边代表一条通信线路,.,给每条边赋予一个权值,等于建设这条通信线路所要花费的成本,最小成本通信网络问题就是找这样一个连通图,其总成本最小,.,设所有的权值都非负,则最小成本通信网络问题的可行解可限制为连接这些城市的生成树,而最优解是其中具有最小成本的生成树,.,例,13.3,最小成本通讯网络,n-1,条边的元组,约束条件：这些边构成生成树,目标函数：边权之和,原则上所有上述问题需在很大的范围内搜索,优化解；但这常常导致指数复杂度的算法；,是计算上不可接受的。贪心法退而求其次求,所谓的“次优”解。,13.2,贪心法,贪心法指每步,(stage),按所谓的“贪心标准,(,策略,)”,选择,(,元组的,),一个分量，逐步构造出问题解的方法。,贪心法的主要特点是：,分阶段完成：按一定的步骤，每步决定一个分量（,自顶向下,）,不回溯：选定一个分量后,不重试其它可能,贪心标准：指每次选择一个分量时使用的“优化,”,策略。所选策略可能导致优化解，但更多情形是得到近似解，特别是对,NP,难度问题。不同的人可能有不同的“优化”策略。,常常采纳使目标函数有最大增量的策略为贪心策略。,基本要素,贪心选择性质,:,所求问题的整体最优解可以通过一系列局部最优选择,(,贪心选择,),来达到,最优子结构性质：问题的最优解包含其子问题的最优解,例,13.4,找零钱,一个小孩买了价值少于,1,美元的糖，并将,1,美元的钱放入取款机。取款机要用数目最少的硬币将零钱找给小孩。假设取款机内有任意多的面值为,25,美分、,10,美分、,5,美分、及,1,美分的硬币。,贪心策略为：每次给出不超过应找钱数的面值最大的硬币。,贪心策略得到优化解,:,20-25,美分之间：选,2,个,10,美分最好,.,25-30,美分之间选一个,25,最好,;,30,美分：一个,25,加一个,5,美分等等,.,硬币面值之间有倍数关系,;,否则没解,:,例如,面值,14,12,5,和,1;,则,17,12,5,用,2,枚硬币,而贪心法为,14,加,3,个,1,共,4,枚硬币,.,例,13.5,机器调度,现有,n,个任务和足够多台处理这些任务的机器。,每个任务的开始时间为,s,i,，,完成时间为,f,i,（,s,i,f,i,）,s,i,f,i,为处理任务,i,的时间区间。,两个任务,i,，,j,重叠是指两个任务的时间区间有重叠。例如：区间,1,4,与区间,2,5,重叠，而与区间,4,7,不重叠。,可行的任务分配,分配中不会将重叠的任务分配给同一台机器。,每台机器在任何时刻最多只处理一个任务。,最优分配指占用机器数最少的可行分配。,图,13-1,任务及三台机器的调度,a)7,个任务,b),调度,例,13.5(,续,),贪心算法：,步骤：按任务起始时间排序并安排任务,贪心准则：尽可能使用旧机器，即以前使用过的机器,上述贪心法产生优化解，因为：,任何可行解使用的机器数不少于最大重迭任务数,贪心解使用的机器数不超过最大重迭任务数,实现问题：,使用,min-,堆存放每台旧机器的可用时间,即此时间以后可安排新任务,算法的时间复杂度为,(,nlogn,),例题,13.6(,最短路算法,),选择“最近”的且不在路径上的下一节点,贪心解不是优化解,:,13.3,应用,货箱装船问题（,Container Loading,),背包问题（,Knapsack Problem,）,拓扑排序问题,(,Topological Sorting,),最短路径问题,(,Shortest Path,),最小代价生成树,(,Minimum Spanning Tree,),13.3.1 Container loading,问题,目标函数：装载的集装箱数目,极大化目标函数,贪心策略,船可以分步装载，每步装一个集装箱，且需要考虑装载哪一个集装箱。,贪心标准：在剩下的集装箱中选择有最小重量的集装箱,实现,算法首先按重量对物品排序,按贪心策略装箱,程序,13.1,程序,13.1,（续）,定理,13.1,上述贪心法产生的解是优化解,:,优化解,(y,1,y,n,),可经有限次替换得到贪心解,而且每次替换箱子数不变,.,如该优化解不会箱子,1,将其替换其中一个箱子,仍是优化解,.(,必须替换,否则不是优化解,),反复替换将得到一个优化解,它就是贪心法得到的解,.,13.2.2 0/1,背包问题,0/1,背包问题：设有,容量,c,的背包，和,n,件物品，物品,i,的重量为,w,i,，,假定装入物品,i,获得的效益值为,p,i,试给出一装入物品的方法，使得获得的总效益值最大。,集装箱装载问题是,0/1,背包问题的特例。,0/1,背包问题是,NP,难度问题。所以贪心法产生的解是近似解。,13.2.2 0/1,背包问题,可行解元组表示,x,i,=1,表示物品,i,装入背包中，,x,i,=0,表示物品,i,不装入背包。,问题,目标函数：,装入物品效益值,约束条件：,求解：,极大化目标函数，,计算,x,i,的值,0/1,背包问题,贪心策略,1,：从未装入的物品中，选出效益值最大的物品装入,利用这种规则，效益值最大的物品首先被装入（假设有足够容量），然后是下一个效益值最大的物品，如此继续下去。,这种策略不能保证得到最优解,n=3,c=105,w=100,10,10,p=20,15,15,贪心解为：,1,0,0,，效益值为：,20,优化解为：,0,1,1,，效益值为,30,(,续,),贪心策略,2,：从尚未装入的物品中选择重量最小的物品。,虽然这一贪心法对于上述例子能产生最优解，但在一般情况下不一定能得到最优解,n=2,c=25,w=10,20,p=5,100,贪心策略,3,：按,密度,p,i,/,w,i,，,从剩余物品中选择可装入背包的密度值最大的物品，这种策略也不能保证得到最优解,:,n=3,c=30,w=20,15,15,p=40,25,25,贪心解为,1,0,0,但优化解为,0,1,1,(,续,),密度贪心法的伪代码,:,(1),将物品按密度从大到小排序,(2)for(i=1;i10/9,时,优化值,9y.,误差为,(9y-10)/9y.,对任意大的,y,误差可近似达到百分之百,.,例,13.9 k-,优化算法,k-,优化算法是上述密度贪心算法的改进，改进后其误差可控值在,100/(k+1),之内,.,k-,优化算法：,预先将不超过,k,种物品的子集装入背包，对其余物品用密度贪心法。,对所有,k,物品子集执行上述过程，并从中找到有最大效益值的解。,考虑,n,=4,w,=2,4,6,7,p,=6,10,12,13,c,=11,。,k,2,：,当,k,=0,时，同于前述的密度贪心法。因此解为,x,=1,1,0,0,，效益值为,16,。,例,13.9(,续,1,）,k,=1,时。初始子集为,1,2,3,4,。,子集,1,2,产生与,k,=0,时相同的结果：,x,=1,1,0,0,，效益值为,16,。,考虑子集,3,，置,x,3,为,1,。此时还剩,5,个单位的容量，按价值密度非递增顺序来考虑如何利用这,5,个单位的容量。首先考虑物品,1,，它适合，因此取,x,1,为,1,，这时仅剩下,3,个单位容量了，且剩余物品没有能够加入背包中的物品。通过子集,3,开始求解得结果为,x,=1,0,1,0,，,获得的价值为,18,。,若从子集,4,开始，产生的解为,x,=1,0,0,1,，,获得的价值为,19,。,k=0,1,时获得的最优解为,1,0,0,1,，获得的价值为,19,。,n,=4,c,=11,，,w,=2,4,6,7,p,=6,10,12,13,例,13.9,（续,2,）,若,k,=2,，,除了考虑,k,0),得到的解误差不超过,(100/(k+1),当,k,=1,时,为,50%,以内,即如优化值为,100,贪心法算出的值不低于,50;,当,k,=2,时,为,33.33%,以内,.,算法的时间复杂度随,k,的增大而增加,需要测试的子集数目为,O(,n,k,),每一个子集所需时间为,O(,n,),因此当,k,0,时总的时间开销为,O(,n,k,+1,),。,13.3,拓扑排序,拓扑排序定义：,任务的先后顺序可用有向图表示,称为,AOV,网络,(Activity On Vertex),.,有向图的顶点代表任务,有向边,(i,j),表示先后关系,:,任务,i,完成后才能开始任务,j,.,根据上述,AOV,网络我们要对任务进行排序使得排序序列的先后关系与,AOV,网定义的先后关系一致,.,根据任务的有向图建立拓扑序列的过程称为拓扑排序,.,13.3,拓扑排序,对所有顶点的排列逐个检验的方法是不足取的,:,O(n,!),的时间复杂度,.,假设从空集开始，每步产生拓扑排序序列中的一个顶点,w,怎样选择顶点,w,？,greedy,策略,:,从不在拓扑序列的顶点中选择一顶点,w,其,所有先行节点,v,都在已产生的拓扑序列中,(,或无先行顶点,).,用减入度的方法确定,w,:,入度变成,0,的顶点,使用栈的伪代码,(1),计算每个顶点的入度,(2),将入度为,0,的顶点入栈,(3)While(,栈不空,),任取一入度为,0,的顶点放入拓扑序列中,;,将与其相邻的顶点的入度减,1;,如有新的入度为,0,的顶点出现,将其放入,栈中,;,(4),如有剩余的顶点则该图有环路,引理,13.1,如果,伪代码,13.5,失败，则有向图含有环路。,证明：,当失败时,|V|d(i)+,c,ij,then,d(j):=d(i)+,c,ij,and,pred(j,):=i;,Update(i,)is used in,Dijkstras,algorithm and in the label correcting algorithm,Update(7),1,8,2,7,1,3,2,0,1,4,6,9,5,3,2,1,3,11,9,8,d(7)=6 at some point in the algorithm,because of the path 1-8-2-7,Suppose 7 is incident to nodes 9,5,3,with temporary distance labels as shown.,We now perform Update(7).,8,7,no change,On Updates,Note,:distance labels cannot increase in an update step.They can decrease.,We do not need to perform Update(7)again,unless d(7)decreases.Updating sooner could not lead to further decreases in distance labels.,In general,if we perform Update(j),we do not do so again unless d(j)has decreased.,1,8,2,7,1,3,2,0,1,4,6,9,5,3,2,1,3,11,9,8,8,7,no change,Dijkstras,Algorithm,Let d*(j)denote the shortest path distance from node 1 to node j.,Dijkstras,algorithm will determine d*(j)for each j,in order of increasing distance from the origin node 1.,S denotes the set of,permanently labeled,nodes.,That is,d(j)=d*(j)for j,S.,T denotes the set of,temporarily labeled,nodes.,That is,d(j),d*(j)for j,T.,Dijkstras,Algorithm,begin,S:=1;,T=N 1;,d(1):=0 and pred(1):=0;d(j)=,for j=2 to n;,update(1);,while,S,N,do,begin,(,node selection,also called FINDMIN),let i,T be a node for which d(i)=min d(j):j,T;S:=S,i;T:=T i;,Update(i),end,;,end,;,Why Does,Dijkstras,Algorithm Work?,A standard method for proving correctness.,Determine things that are true at each iteration.These are called,invariants,.,Prove invariants using induction,Prove that the algorithm is finite,Choose invariants so that the algorithms correctness follows directly from the invariants and the fact that the algorithm terminates.,Why Does,Dijkstras,Algorithm Work?,Invariants for,Dijkstras,Algorithm,If j,S,then d(j)is the shortest distance from node 1 to node j.,If i,S,and j,T,then d(i),d(j,).,If,j,T,then d(j)is the length of the shortest path from node 1 to node j in S,j.,Note:,S increases by one node at a time.So,at the end the algorithm is correct by invariance 1.,Verifying invariants when S=1,1.If j,S,then d(j)is the shortest distance from node 1 to node j.,2.If i,S,and,j,T,then d(i),d(j).,3.If,j,T,then d(j)is the length of the shortest path from node 1 to node j in S,j.,1,2,3,4,5,6,2,4,2,1,3,4,2,3,2,1,0,2,4,Consider S=,1,and after update(1),Verifying invariants Inductively,1,2,4,6,2,4,2,1,3,4,2,a,2,0,3,2,3,6,4,5,6,2.If i,S,and,j,T,then d(i),d(j).,If this was true before node 5 was transferred,it remains true afterwards.,Assume that the invariants are true before the update.,Node 5 was just selected.It is now transferred from T to S.,Verifying invariants Inductively,1,2,4,6,2,4,2,1,3,4,2,a,2,0,3,2,3,6,4,5,6,To show,:1.,If j,S,then d(j)is the shortest distance from node 1 to node j.,By inductive hypothesis,:Before the transfer of node j*(node 5)to S,if,k,T,then d(k)is the length of the shortest path from node 1 to node k in S,k.,The result is clearly true for nodes in S prior to transferring node j*.We need to prove it for j*=5.Any path from node 1 to node j*has a first node k in T prior to the transfer,and the path from 1 to k has length at least d(k),d(j*).So,the shortest path to j*has length at least d(j*).,Verifying invariants Inductively,1,2,4,6,2,4,2,1,3,4,2,a,2,0,3,2,3,6,4,5,6,To show,:3.,If,j,T,then d(j)is the length of the shortest path from node 1 to node j in S,j.,By inductive hypothesis,:1-3 are all true prior to the transfer of node j*to S and prior to update(j*).,Consider node k,T(e.g.,node 4).By hypothesis,d(4)is the shortest path length from 1 to 4 in G restricted to 1,2,3,4.Let d(4)be the value after update(5).We want to show that d(4)is the length of the shortest path P from 1 to 4 in G as restricted to 1,2,3,4,5.,If P does not contain node 5,then d(4)=d(4)and the result is true.,If P does contain node 5,then 5 immediately precedes node 4 and the result is true.,A comment on invariants,It is the standard way to prove that algorithms work.,Finding the best invariants for the proof is often challenging.,A reasonable method.Determine what is true at each iteration(by carefully examining several useful examples)and then use all of the invariants.,Then shorten the proof later.,Complexity Analysis of,Dijkstras,Algorithm,Update Time:,update(j,)occurs once for each j,upon transferring j from T to S.The time to perform all updates is,O(m,)since the arc(,i,j,)is only involved in,update(i,).,FindMin,Time:,To find the minimum(in a straightforward approach)involves scanning,d(j,)for each j,T.,Initially T has n elements.,So the number of scans is n+n-1+n-2+1=O(n,2,).,O(n,2,)time in total.,This is the best possible only if the network is,dense,that is m is about n,2,.,We can do better if the network is,sparse,.,图,13.10,最短路径举例,13.3.6,最小生成树,具有,n,个顶点的连通的无向图,G,图的每条边,e,有一非负权值,c(e,),也称为成本,求有最小成本的生成树,.,每个生成树刚好具有,n,-1,条边，所以问题是用某种方法选择,n,-1,条边使它们形成,G,的最小生成树。,我们采用以下二种不同的贪心策略来选择这,n,-1,条边。,这二种贪心策略对应求解最小生成树的二个算法：,Kruskals,算法，,Prims,算法。,Kruskals,算法,贪心策略,:,每次选择权值,c(e,),最小且与以前选择的边不构成,cycle,的边,e.,上述策略要求按权值从小到大对边排序,.,图,13.12,构造最小生成树,图,13.12,构造最小生成树（续,1,）,图,13.12,构造最小生成树（续,2,）,图,13.13,Kruskals,算法,的伪代码,正确性证明,利用类似装载问题所用的变换技术可以证明图,13.13,的贪心法总能建立一棵最小生成树,.,需要证明：,只要图是连通的,Kruskals,算法总能产生一棵生成树,;,产生的生成树具有最小成本,.,证明,设,T,是贪心法产生的解，,U,是优化解,设,e,是属于,T,但不属于,U,的成本最小的边,;,换言之,T,中成本小于,c(e,),的边都在,U,中,.,设,f,是,e+U,产生的环路上不在,T,中的一条边,这样的,f,一定在,否则,T,将包含一个环路,.,c(f,),的不小于,c(e,):,因,T,中比,e,成本小的边都在,U,中,所以,f,与,T,中成本小于,e,的成本的边,(,这些边都在,U,里,),不构成环路,;,如果,f,的成本小于,e,的成本,贪心法会先于,e,将,f,加入到,T,中,矛盾,.,从,U,中删除,f,并加入,e,得到的树,U,仍是优化的,.,数据结构,使用,UNION,FIND,数据结构,初始为单个顶点的集合,对每条边做,2,次,FIND,找到边的端点所在的集合,;,如果在同一集合中则舍弃该条边,否则将,2,个集合合并,(UNION),算法可在,O(n+eloge,),找出最小生成树,:,边排序,:,O(eloge,),initializing:O(n,),union-,find:O(e,),Prim,s,算法,设,A,为算法执行过程中产生的生成树中的顶点,.,初始化,A,包含图中任一顶点,;,V-A,作成一个优先级队列,Q,关键字值取为连接该顶点和,A,的边的最小权值,.,每步从,Q,中取出关键字值最小的顶点,u,将其加入,A;,修改,Q,中与,u,相邻的顶点的关键字值,.,该算法不要求对边排序。,算法的伪代码如下,:,Prims,算法,图,13.5,图,13.15,Prims,算法的步骤,Prims,算法的步骤（续）,Analysis,Analysis,Extract min needs at most,(,log|V,|),Decrease key needs,(|E|),Total time is,(|,V|log|V|+|E,|),小结,贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的,局部最优,选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。,