算法课件(五)贪心算法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,贪心算法,目录,背包问题,作业安排问题,带期限的单机作业安排问题,多机调度问题,贪心算法的理论基础,-,拟阵（略）,贪心算法的进一步讨论,什么是贪心算法,贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。,贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。,喷水装置,现有一块草坪，长为,20,米，宽为,2,米，要在横中心线上放置半径为,Ri,的喷水装置，每个喷水装置的效果都会让以它为中心的半径为实数,Ri(0Ri15),的圆被湿润,，现有,充足的喷水装置,i,（,1i0 , 1,i,n,背包问题,(,Knapsack Problem,),问题描述,设有,n,个物体和一个背包,物体,i,的重量为,w,i,价值为,v,i,背包的容量为,C.,若将物体,i,的,x,i,部分,(1,i,n, 0,x,i,1),装入背包,则具有价值为,v,i,x,i,。目标是找到一个方案,使放入背包的物体总价值最高,.,约,束,条,件,目标函数,贪心方法的数据选择策略,首先要选出最优的度量标准。,1,、以,价值,为量度标准,按价值从高到低的次序将物品一件件放到背包中,背包容量消耗过快,2,、以,容量,作为量度,按物品重量的从清到重次序来把物品放入背包：容量消耗过程中，效益值没有迅速的增加。,3,、采用,单位价值,为度量标准：每一次装入的物品应使它占用的每一单位容量获得当前最大的单位效益。,使物品的装入次序,按,p,i,/,w,i,比值的从大到小,来考虑。,背包问题实例,考虑下列情况的背包问题,n=3,M=20,(v,1,v,2,v,3,)=(25,24,15,),(w,1,w,2,w,3,)=(18,15,10),算法思路,1),将各物体按单位价值由高到低排序,.,2),取价值最高者放入背包,.,3),计算背包剩余空间,.,4),在剩余物体中取价值最高者放入背包,.,若背包剩余容量,=0,或物体全部装入背包为止,x1,x2,x3,0,2/3,1,0,1,1/2,.,1,2/15,0,20,20,20,28.2,31,31.5,.,.,背包问题贪心算法,GreedyKnapsack,(p, w, M, x, n) / M,是背包容量，,x,是解向,/,量,价值数组,p1.n,、重量数组,w1.n,，它们元素的排列顺,/,序满足,pi/wipi+1/wi+1,x= 0 /,将解向量初始化为零,rc,= M /,背包的剩余容量初始化为,M,for i to n do,if,wi, ,rc,then break,end if,xi,:=1,rc,:=,rc-wi,;,end for,if,in,then,xi,:=,rc/wi,;,end if,算法分析,:,排序为主要算法时间,所以,T(n)=,O(nlogn,),背包问题中的物体不能分拆,只能整个装入称为,0-1,背包问题,.,算法证明,:,该算法能得到在最优解,用贪心算法能得到,0-1,背包的最优解吗,?,计算每种物品单位重量的价值,V,i,/,W,i,，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过,C,，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。,0-1,背包问题与背包问题,10,20,30,50,1.,￥,60 2.,￥,100 3.,￥,120 4.,背包,=,￥,220,=,￥,160,=,￥,180,=,￥,240,100,20,120,30,60,10,100,20,60,10,120,30,60,10,100,20,80,20,120,20,30,0-1,背包,背包,物品价值及重量,对于,0-1,背包问题,，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。,事实上，在考虑,0-1,背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用,动态规划算法,求解的另一重要特征。,实际上也是如此，动态规划算法的确可以有效地解,0-1,背包问题。,活动安排问题,问题描述,有,n,个活动的集合,E=1,2,n,，要求使用同一资源，如演讲会场、教室安排等等。而在同一时间内只有一个活动能使用这一资源。第,k,个活动要求使用的起始时间和结束时间分别是,s,i,、,f,i,s,j,f,j,或者,s,j,f,i,。,活动安排问题就是要在所给的活动集合中选出最大,(,活动个数最多,),的相容活动子集。,解决活动安排问题的基本思路是在安排时应该将结束时间早的活动尽量往前安排，也就是说，使剩余的可安排时间段极大化，,从而达到安排最多活动的目的。,据此，贪心准则应当是：在未安排的活动中挑选结束时间最早的活动安排。,在贪心算法中，将各项活动的开始时间和结束时间分别用两个数组,s,和,f,存储，并使得数组中元素的顺序按结束时间非减序排列：,f1 f2 fn,。,1 2 3 4 5 6 7 8 9 10 11,1 3 0 5 3 5 6 8 8 2 12,4 5 6 7 8 9 10 11 12 13 14,i,si,fi,例,设待安排的,11,个活动起止时间按结束时间的非减序排列,最大相容活动子集,(1, 4, 8, 11),也可表示为等长,n,元数组,:(1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1),算法思路,将,n,个活动按结束时间非减序排列,依次考虑活动,i,若,i,与已选择的活动相容,则添加此活动到相容活动子集,.,活动安排问题是可以用贪心算法有效求解的很好例子。,活动安排贪心算法伪代码,GreedyAction(s, f,，,n) / s1.n,、,f1.n,分别代表,n,项活动的起始时间和结束时间,并且满足,f1 f2,fn,j:=1,solution:=1 /,解向量初始化,for i from 2 to n do,if,sifj,then,solution:=solution j; /,将,j,加入解中,j:=i;,endif,endfor,return(solution,);,endGreedyAction,算法,greedySelector,的效率极高。当输入的活动已按结束时间的非减序排列，算法只需,O(n),的时间安排,n,个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用,O(nlogn,),的时间重排。,T(n)=,O(nlogn,) (,未排序时,),算法分析,T(n)=O(n) (,排序时,),算法证明,算法达到最优解,.,带限期的单机作业安排问题,贪心算法可用来解决操作系统中的单机、无资源约束且每个作业可在等量,t,i,时间内完成的,作业调度问题,。,已知,n,项作业,E=1, 2, ,n,，要求使用同台机器完成（该台机器在同一时刻至多进行一个作业），而且每项作业需要的时间都是,1,。第,k,项作业要求在时刻,f,k,之前完成,而且完成这项作业将获得效益,p,k,，,k=1, 2, , n,。,作业集,E,的子集称为相容的，如果其中的作业可以被安排由一台机器完成。带限期单机作业安排问题就是要在所给的作业集合中选出总效益值最大的相容子集。,例如：,n=4,，,(p1,p2,p3,p4)=100,10,15,20,，,(d1,d2,d3,d4)=2,1,2,1,例子 设,n=7, (p1, p2, ,pn,)=(35,30,25,20,15,10,5),(d1, d2, ,dn,)=(4,2,4,3,4,8,3),算法,GreedyJob,的执行过程可描述如下：,d1,;,d2, d1,;,d2, d1,d3,;,d2, d4, d1,d3;,d2, d4, d1,d3, d6;,4,;,2, 4,;,2, 4, 4,;,2, 3, 4, 4,;,2, 3, 4, 4, 8,；,带限期作业安排的贪心算法,GreedyJob(f, p, n) /f1.n,和,p1.n,分别代表各项作业的限期,/,和效益值，,n,项作业的排序满足：,p1 p2 ,pn,J:=1;/,初始化解集,for i from 2 to n do,if J i,中的作业是相容的,then /,此步需要认真验证,J:= J i; /,将,i,加入解中,endif,endfor,endGreedyJob,如何判断 “,J i,中的作业是相容的”？,如果每选入一个作业,i,的期限为,t,，,J,中至少有,t,个作业的期限不晚于,t,，则,J i,一定是不相容的。反之，若,J,中期限不晚于,t,的作业少于,t,个，则作业,i,比可插入到作业集,J,中，即,J i,一定是相容的。,因而，,J i,的相容性判断最坏情况下需要,|J|,次比较。上述算法在最坏情况下的时间复杂度为,O(n,2,),。,带期限作业安排问题贪心算法,GreedyJobS(D,J,n,k,) /D(1),D(n,),是期限值，作业已,按p1 p2 pn排,/,/,序,排序。,J(i,),是最优解中的第,i,个作业。终止时,D(J(i,) D(J(i+1),，,1ik,D(0):=0; J(0):=0; /,初始化,K:=1; J(1):=1; /,计入作业,1,，,k,表示当前选择的作业个数,for i from 2 to n do,/,按,p,的非增次序考虑作业，找,i,的位置，并检查插入的可能性,r:=k;,while,D(J(r,),D(i,) and,D(J(r,)r do,r:=r-1;,endwhile,;,/,期限不晚于,D(i,),的作业个数小于,D(i,),时,if,D(J(r,),D(i,) and,D(i,)r then,for j from k to r+1 by 1 do /,给作业,i,腾出位置,J(j+1):=,J(j,);,endfor,;,J(r+1):=i; k:=k+1;,endif,;,endfor,;,为避免调度表调整，将算法,GreedyJob,稍做改进：在每次选择作业时，在调度表中尽量地向后分配时间片，这样好为后面的作业安排留下更多的空间,:,1,，,3,4;,1,2,3,4,1,2;,1,2,3,3,4,1,2,2,3;,1,2,3,4,3,4,1,2,2,3,0,1;,1,2,3,4,6,3,4, 1,2,2,3,0,1,7,8.,根据该思路构造的算法时间复杂度为,O(n,),证明：假设贪心算法所选择的作业的集合,J,不是最优解，则一定有相容的作业子集,I,，其产生更大的效益值。假定,I,是具有最大效益值的相容作业子集中使得,IJ,最大者，往证,I=J,。,反证法：若不成立，则这两个作业集,JI,=,I,和之间没有包含关系。这是因为算法,GreedyJob,的特性和假定,I,产生的效益值比,J,的效益值更大。假设,a,是,JI,中具有最大效益的作业，于是，,J,中比,a,具有更大效益的作业,(,如果有的话,),都应该在,I,中。现在将作业,a,加入到,I,中，得,J,*,=,aI,.,由,I,的极大性知，,I,*,一定是不相容的,.,从而，对于,I,的任何一个调度表,S,，在,f,a,时刻前的时间片都已经被,I,中的作业占用。假定,S,是,I,的这样一个调度表：在,f,a,时刻之前最大限度地安排了,IJ,中的作业。如果,S,中,f,a,时刻以前的作业仍然都是,J,中的，则,IJ,中结束时刻不晚于,fa,的作业至少有,f,a,个。但,aIJ,这与,J,的相容性矛盾。因此，,S,中必有某个作业,bI,J,其被安排在,fa,时刻之前的时间片上。在所有这样的作业,b,中选择结束时刻最晚的。由于,a,的选法以及,bI,J,，必然有,papb,。不然，按照算法，,b,将先于,a,考虑加入到,J,中。令,J*=I*b,，则,J*,必然具有最大效益，而且,|J,*,I|JI|,这与,I,的选取矛盾。故,J,具有最大效益。 证毕,多机调度问题,设有,n,项独立的作业,1,2, n,由,m,台相同的机器加工处理。作业,i,所需要的处理时间为,ti,。约定：任何一项作业可在任何一台机器上处理，但未完工前不准中断处理；任何作业不能拆分更小的子作业分段处理。多机调度问题要求给出一种调度方案，使所给的,n,个作业在,尽可能短,的时间内由,m,台机器处理完。,这是一个,NP,完全问题，到目前为止还没有一个有效的解法。利用贪心策略，有时可以设计出较好的近似解。,采用贪心准则：需要长时间处理的作业优先处理。,例 设有,7,项独立的作业,1,2,3,4,5,6,7,要由三台机器,M1, M2 , M3,处理。各个作业所需要的处理时间分别为,2,14,4,16,6,5,3.,将作业标号按它们所需时间的长短排列：,4, 2, 5, 6, 3, 7,1.,将需要时间最长的未被安排作业首先安排给能够最早空闲下来的机器处理。,时间复杂性分析,：,O(nlogn+nlogm,),多机问题不一定得到最优解,：多机调度是,NP,完全问题，贪心算法得到其近似解。,贪心法解多机调度问题算法分析,Maximizing Job Benefits on MultiprocessorSystems Using a Greedy Algorithm,用贪心算法使多处理器系统作业效益最大化（,2007,）,This project considers a benefit model,（效益模型）,for on-line preemptive multiprocessor scheduling,（抢占式多处理器调度）,. In this model, each job arrives with its own benefit function,（效益函数）,and execution time,（执行时间）,. The flow time,（作业流转时间）,of a job is the time between its arrival and its completion. The benefit function determines the benefit gained for any given flow time. The goal is to maximize the total benefit gained only by the jobs that meet their deadlines.,In order to achieve this goal, a variety of approximation algorithms and their applications in multiprocessor scheduling were studied.,A greedy algorithm with 2-approximation ratio is proposed to be added to an existing benefit based scheduling algorithm, in order to reduce the delay of each job, by assigning it to the processor with least utilization so far.,This method will decrease the flow time of the jobs, resulting in higher benefits gained by each job. Also, evaluation of this approach shows that it uses the CPU cycles more efficiently by providing more balanced distribution of the jobs between the processors.,Therefore, more jobs can meet their deadlines and add their gained benefits to the total benefit. In addition, the proposed method is computationally less expensive than the existing benefit based method.,贪心算法进一步讨论,贪心策略是最接近人的日常思维的一种解题策略,虽然它不能保证求得的最后解一定是最佳的,但是它可以为某些问题确定一个可行性范围,因此在对,NPC,类问题的求解中发挥着重要作用。,贪心策略无回溯过程,每一步都是当前看似最佳的选择。一般而言，一个问题，如果能够使用贪心算法，极为高效。,贪心算法是一种极为重要的算法，哈夫曼树，最小生成树的Prim算法，Kruskal算法，单源最短路径的dijkstra，拓扑排序等许多经典算法都是以贪心算法为基础。,贪心算法可以生成部分解，结合局部搜索（随机）并进行迭代以改进局部优解的方法，得到一个较为满意的全局优解。,建立数学模型来描述问题,把求解的问题分成若干个子问题,对每一子问题求解，得到子问题的局部最优解,把子问题的解局部最优解合成原来解问题的一个解,贪心算法的基本思路,从问题的某一初始解出发；,while,能朝给定总目标前进一步,do,求出可行解的一个解元素；由所有解元素组合成问题的一个可行解；,实现该算法的过程,贪心算法的性质,对于一个具体的问题，如何知道是否可用贪心算法，以及能否得到问题的一个最优解呢,?,这个问题很难给予肯定的回答。但从许多可以用贪心算法求解的问题中可以看到它们一般具有两个重要的性质：贪心选择性质和最优子结构性质。,贪心选择性质：指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。,贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。,对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。,最优子结构性质：当一个问题的最优解包含着它的子问题的最优解时，称此问题具有最优子结构性质。最优子结构性质也即每个子问题的最优解的集合就是整体最优解。,贪心算法的几个注意问题,寻找贪心选择的量度,根据量度设计出算法：分析复杂性,问题变形算法可能不适用,贪心算法讨论（,1,）：背包问题的应用,背包问题,( knap sack problem,简称,KP),是一类在给定约束条件的情况下,求最大值的组合优化问题,是典型的非确定多项式完全难题,.,解决该问题无论在理论上,还是在实际中都具有重要的意义,.,许多工程优化问题都可以归结为背包问题,典型问题有,:,处理机和数据库在分布式计算机系统上的分配问题、资源分配问题、厂址选择问题、货物装载问题、批量切割问题、项目选择决策问题、削减库存问题等。,随着网络技术的不断发展,背包公钥密码在电子商务中的公钥设计中也起着重要的作用,.,同时,在设计解决大量的复杂组合优化问题算法时,背包问题往往作为子问题出现,.,背包问题的算法改进,对复杂组合优化问题算法的改良是十分有益的,.,近几十年中, KP,建模与算法的研究受到广泛的重视,研究前景十分广阔,.,随着背包问题的发展,产生了许多该问题的变形,.,其中,0 - 1,背包问题是最基础的背包问题,包含了背包问题的最基本思想,其他类型的背包问题往往也可以转换成背包问题求解,.,背包问题是个,NP,困难问题,是否存在多项式时间有效算法尚不可知,.,目前对此类问题的研究已出现了不少有价值的方法,.,这些方法主要分两大类,:,一类是精确式方法,如,:,分支限界法、动态规划法、回溯法、穷举法、图论法等,这些精确式方法都是指数级的,用来解决目前的实际问题比较困难,;,另一类是启发式方法,如,:,贪心算法、遗传算法、蚁群系统、禁忌搜索算法、模拟退火算法、微粒群优化算法等,.,由于启发式算法是模拟自然现象或人类思维过程而提出的新型算法,具有框架灵活、与问题本身无关等一系列优点,因而获得了非常广泛的应用,参考文献,姜正涛，张京良，王育民,.,一种新的等价于大整数分解的公钥密码体制研究,J.,电子与信息学报，,2008, 30(6): 1450-1452.,王保仓，韦永壮，胡予濮，,基于随机背包的公钥密码,J.,电子与信息学报 ，,2010,，,Vol.32,，,No.7,，,1580-1584,贪心算法讨论（,2,）：最优化问题求解,贪心算法一般是求“最优解”这类问题的。,最优解问题可描述为：有,n,个输入，它的解是由这,n,个输入的某个子集组成，并且这个子集必须满足事先给定的条件。这个条件称为约束条件。而把满足约束条件的子集称为该问题的可行解。,这些可行解可能有多个，为了衡量可行解的优劣，事先给了一个关于可行解的函数，称为目标函数。,目标函数最大（或最小）的可行解，称为最优解。,求“最优解”最原始的方法为搜索枚举方案法（一般为回溯法）。,除了极简单的问题，一般用深度优先搜索或宽度优先搜索。通常优化方法为利用约束条件进行可行性判断剪枝；或利用目标函数下界（或上界），根据当前最优解进行分枝定界。,其次是动态规划：动态规划主要是利用最优子问题的确定性，从后向前（即从小规模向大规模）得到当前最优策略，从而避免了重复的搜索。,采用回溯法，搜索过程如下：,贪心算法不同，它不是建立在枚举方案的基础上的。它从前向后，根据当前情况，“贪心地”决定出下一步，从而一步一步直接走下去，最终得到解。假如上面的例子中，我们定下这样的贪心策略：节点号,k%3=1,。则有图,3,。,显然，它只访问了节点,1,、,4,、,7,、,10,、,11,，工作量最少，效率最高。当然，对本题来说，它不能得到最优解,最短路径。从图,3,中可以看出，贪心算法是一种比动态规划更高效的算法。只是要保证得到最优解是贪心算法的关键。,贪心算法的证明问题,贪心算法的关键是正确性证明。,有一个证明模型是“矩阵胚理论”，但要证明一个问题是矩阵胚，十分困难。,其他证明方法：,构造法：根据描述的算法，用贪心策略，依次构造出一个解，可证明一定是合法的解。,反证法：用贪心策略，依次构造出一个解,S1,。假设最优解,S2,不同于,S1,，可以证明是矛盾的。从而,S1,就是最优解。,调整法：用贪心策略，依次构造出一个解,S1,。假设最优解,S2,不同于,S1,，找出不同之处，在不破坏最优性的前提下，逐步调整,S2,，最终使其变为,S1,。从而,S1,也是最优解。,士兵排队问题,-,构造法证明,有,N,个士兵,(1N26),，编号依次为,A,，,B,，,C,，,.,。队列训练时，指挥官要把一些士兵从高到矮依次排成一行，但现在指挥官不能直接获得每个人的身高信息，只能获得“,P1,比,P2,高”这样的比较结果,(P1,，,P2A,，,B,，,C,，,.,，,Z,，记为,P1P2),，如“,AB”,表示,A,比,B,高。请编一程序，根据所得到的比较结果求出一种符合条件的排队方案。,INPUT.TXT,AB,BD,FD,OUTPUT.TXT,AFBD,排队问题,-,反证法证明,在一个超市，有,N,个人排队到一个柜台付款，已知每个人需要处理的时间为,Ti,（,0,iN,），请你找一种排列次序，使每个人排队的时间总和最小。,输入输出示例,INPUT.TXT,4,5 10 8 7,OUTPUT.TXT,67,作业：,实现背包问题的贪心算法。,*实现带期限的作业调度算法。,