贪心法(The Greedy Method)

《贪心法(The Greedy Method)》由会员分享，可在线阅读，更多相关《贪心法(The Greedy Method)（74页珍藏版）》请在装配图网上搜索。

1、贪心法（The Greedy Method）宫秀军天津大学计算机科学与技术学院http:/ problem)n贪心算法基本原理(The principle of greedy method)n贪心算法应用q货箱装船问题（Container Loading)q背包问题（Knapsack Problem）q拓扑排序问题(Topological Sorting)q最短路径问题(Shortest Path)q最小代价生成树(Minimum Spanning Tree)n本章小结13.1优化问题n一个优化问题可以描述如下:q问题的解可表示为一复杂的结构，例如元组形式q约束条件(结构性的约束条件n使约束条

2、件为true的元组称为可行解（feasible solution）q目标函数 n优化解即指使目标函数极大化(或极小化)的可行解，对应的目标函数值称为优化值。n很多优化问题是NP难度问题，迄今找不到它们的多项式算法。所以计算上可行的方法就是求其近似解。贪心法是求近似算法的主要途径之一。例13.1Thirsty Babyn有一个聪明的婴儿，她可能得到的饮料包括一桶水、一桶牛奶、多罐不同种类的果汁、许多不同的装在瓶子或罐子中的苏打水。假定婴儿可得到n 种不同的饮料。根据以前关于这n 种饮料的不同体验，婴儿知道其中那些饮料更合自己的胃口。因此，婴儿为每一种饮料赋予一个满意度值si：饮用1盎司第i 种饮

3、料，满意度si。n设第i种饮料有ai盎司，婴儿共需喝t盎司饮料例13.1Thirsty Babyn设xi为第i种饮料的饮用量，假定满意程度是可加的，则最满意的选择是极大化n该优化问题可表示如下q约束条件q目标函数例13.2loading Problemn一艘船准备用来装载货物,所有货物都放在集装箱中。设第i 个集装箱的重量为wi（1in），船的最大载重量为c，试设计一装载方法使得装入的集装箱数目最多。例例13.213.2 Loading Problemn用n维布尔向量代表一种装箱方案n约束条件n目标函数n极大化目标函数例13.3最小成本通信网络n城市之间的通信网络应是以这些城市为顶点的连通图,

4、图的每条边代表一条通信线路.给每条边赋予一个权值,等于建设这条通信线路所要花费的成本,最小成本通信网络问题就是找这样一个连通图,其总成本最小.n设所有的权值都非负,则最小成本通信网络问题的可行解可限制为连接这些城市的生成树,而最优解是其中具有最小成本的生成树.例13.3最小成本通讯网络nn-1条边的元组n约束条件：这些边构成生成树n目标函数：边权之和原则上所有上述问题需在很大的范围内搜索原则上所有上述问题需在很大的范围内搜索优化解；但这常常导致指数复杂度的算法；优化解；但这常常导致指数复杂度的算法；是计算上不可接受的。贪心法退而求其次求是计算上不可接受的。贪心法退而求其次求所谓的所谓的“次优次

5、优”解。解。13.2 贪心法n贪心法指每步(stage)按所谓的“贪心标准(策略)”选择(元组的)一个分量，逐步构造出问题解的方法。n贪心法的主要特点是：q分阶段完成：按一定的步骤，每步决定一个分量（自顶向下自顶向下）q不回溯：选定一个分量后,不重试其它可能q贪心标准：指每次选择一个分量时使用的“优化”策略。所选策略可能导致优化解，但更多情形是得到近似解，特别是对NP难度问题。不同的人可能有不同的“优化”策略。q常常采纳使目标函数有最大增量的策略为贪心策略。n基本要素q贪心选择性质:所求问题的整体最优解可以通过一系列局部最优选择(贪心选择)来达到q最优子结构性质：问题的最优解包含其子问题的最优

6、解例13.4找零钱 n一个小孩买了价值少于1美元的糖，并将1美元的钱放入取款机。取款机要用数目最少的硬币将零钱找给小孩。假设取款机内有任意多的面值为25美分、10美分、5美分、及1美分的硬币。n贪心策略为：每次给出不超过应找钱数的面值最大的硬币。n贪心策略得到优化解:q20-25美分之间：选2个10美分最好.q25-30美分之间选一个25最好;q30美分：一个25加一个5美分等等.n硬币面值之间有倍数关系;否则没解:例如,面值14,12,5和1;q则17125,用2枚硬币,而贪心法为14加3个1,共4枚硬币.例例13.5 13.5 机器调度 n现有n 个任务和足够多台处理这些任务的机器。q每个

7、任务的开始时间为si，完成时间为fi（sifi）qsi,fi 为处理任务i 的时间区间。q两个任务i，j 重叠是指两个任务的时间区间有重叠。例如：区间1,4与区间2,5重叠，而与区间4,7不重叠。n可行的任务分配q分配中不会将重叠的任务分配给同一台机器。q每台机器在任何时刻最多只处理一个任务。n最优分配指占用机器数最少的可行分配。图13-1 任务及三台机器的调度a)7个任务 b)调度例13.5(续)n贪心算法：q步骤：按任务起始时间排序并安排任务q贪心准则：尽可能使用旧机器，即以前使用过的机器n上述贪心法产生优化解，因为：q任何可行解使用的机器数不少于最大重迭任务数q贪心解使用的机器数不超过最

8、大重迭任务数n实现问题：q使用min-堆存放每台旧机器的可用时间,即此时间以后可安排新任务q算法的时间复杂度为(nlogn)例题13.6(最短路算法)n选择“最近”的且不在路径上的下一节点n贪心解不是优化解:13.3应用n货箱装船问题（Container Loading)n背包问题（Knapsack Problem）n拓扑排序问题(Topological Sorting)n最短路径问题(Shortest Path)n最小代价生成树(Minimum Spanning Tree)13.3.1 Container loadingn问题q目标函数：装载的集装箱数目q极大化目标函数n贪心策略q船可以分步

9、装载，每步装一个集装箱，且需要考虑装载哪一个集装箱。q贪心标准：在剩下的集装箱中选择有最小重量的集装箱n实现q算法首先按重量对物品排序q按贪心策略装箱程序13.1程序13.1（续）定理13.1n上述贪心法产生的解是优化解:q优化解(y1,yn)可经有限次替换得到贪心解,而且每次替换箱子数不变.q如该优化解不会箱子1,将其替换其中一个箱子,仍是优化解.(必须替换,否则不是优化解)反复替换将得到一个优化解,它就是贪心法得到的解.13.2.2 0/1背包问题n0/1背包问题：设有容量c的背包，和n件物品，物品i的重量为wi，假定装入物品i获得的效益值为pi,试给出一装入物品的方法，使得获得的总效益值

10、最大。n集装箱装载问题是0/1背包问题的特例。n0/1背包问题是NP难度问题。所以贪心法产生的解是近似解。13.2.2 0/1背包问题n可行解元组表示qxi=1表示物品i 装入背包中，qxi=0 表示物品i 不装入背包。n问题q目标函数：装入物品效益值q约束条件：n求解：极大化目标函数，计算xi的值0/1背包问题n贪心策略1：从未装入的物品中，选出效益值最大的物品装入q利用这种规则，效益值最大的物品首先被装入（假设有足够容量），然后是下一个效益值最大的物品，如此继续下去。q这种策略不能保证得到最优解qn=3,c=105,w=100,10,10,p=20,15,15q贪心解为：1,0,0，效益值

11、为：20q优化解为：0,1,1，效益值为30(续)n贪心策略2：从尚未装入的物品中选择重量最小的物品。q虽然这一贪心法对于上述例子能产生最优解，但在一般情况下不一定能得到最优解qn=2,c=25,w=10,20,p=5,100n贪心策略3：按密度pi/wi，从剩余物品中选择可装入背包的密度值最大的物品，这种策略也不能保证得到最优解:qn=3,c=30,w=20,15,15,p=40,25,25n贪心解为1,0,0,但优化解为0,1,1(续)n密度贪心法的伪代码:(1)将物品按密度从大到小排序(2)for(i=1;i10/9时,优化值9y.n误差为(9y-10)/9y.n对任意大的y误差可近似达

12、到百分之百.例13.9 k-优化算法nk-优化算法是上述密度贪心算法的改进，改进后其误差可控值在100/(k+1)之内.nk-优化算法：q预先将不超过k种物品的子集装入背包，对其余物品用密度贪心法。q对所有k物品子集执行上述过程，并从中找到有最大效益值的解。n考虑n=4,w=2,4,6,7,p=6,10,12,13,c=11。k2：q当k=0时，同于前述的密度贪心法。因此解为x=1,1,0,0，效益值为16。例13.9(续1）nk=1时。初始子集为1,2,3,4。q子集1,2产生与k=0时相同的结果：x=1,1,0,0，效益值为16。q考虑子集3，置x3 为1。此时还剩5个单位的容量，按价值密

13、度非递增顺序来考虑如何利用这5个单位的容量。首先考虑物品1，它适合，因此取x1为1，这时仅剩下3个单位容量了，且剩余物品没有能够加入背包中的物品。通过子集3开始求解得结果为x=1,0,1,0，获得的价值为18。q若从子集4开始，产生的解为x=1,0,0,1，获得的价值为19。nk=0,1时获得的最优解为1,0,0,1，获得的价值为19。n=4,c=11，w=2,4,6,7,p=6,10,12,13例13.9（续2）n若k=2，除了考虑k0)得到的解误差不超过得到的解误差不超过 (100/(k+1)n当当k=1时时,为为50%以内以内,即如优化值为即如优化值为100,贪心贪心法算出的值不低于法算

14、出的值不低于50;当当k=2时时,为为33.33%以内以内.n算法的时间复杂度随算法的时间复杂度随k 的增大而增加的增大而增加,需要测需要测试的子集数目为试的子集数目为O(nk),每一个子集所需时间每一个子集所需时间为为O(n),因此当因此当k 0时总的时间开销为时总的时间开销为O(nk+1)。13.3拓扑排序拓扑排序定义：n任务的先后顺序可用有向图表示,称为AOV网络(Activity On Vertex).有向图的顶点代表任务,有向边(i,j)表示先后关系:任务i完成后才能开始任务j.n根据上述AOV网络我们要对任务进行排序使得排序序列的先后关系与AOV网定义的先后关系一致.根据任务的有向

15、图建立拓扑序列的过程称为拓扑排序.13.3拓扑排序n对所有顶点的排列逐个检验的方法是不足取的:O(n!)的时间复杂度.n假设从空集开始，每步产生拓扑排序序列中的一个顶点w,怎样选择顶点w？ngreedy策略:从不在拓扑序列的顶点中选择一顶点w,其所有先行节点v都在已产生的拓扑序列中(或无先行顶点).n用减入度的方法确定w:入度变成0的顶点使用栈的伪代码n(1)计算每个顶点的入度n(2)将入度为0的顶点入栈n(3)While(栈不空)任取一入度为0的顶点放入拓扑序列中;将与其相邻的顶点的入度减1;如有新的入度为0的顶点出现,将其放入栈中;n(4)如有剩余的顶点则该图有环路引理13.1n如果伪代码

16、13.5失败，则有向图含有环路。n证明：当失败时|V|d(i)+cij thend(j):=d(i)+cijandpred(j):=i;nUpdate(i)isusedinDijkstrasalgorithmandinthelabelcorrectingalgorithmUpdate(7)182713201469532131198d(7)=6 at some point in the algorithm,because of the path 1-8-2-7Suppose 7 is incident to nodes 9,5,3,with temporary distance labels a

17、s shown.We now perform Update(7).87no changeOn UpdatesNote: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

18、 not do so again unless d(j)has decreased.18271320146953213119887no changeDijkstras AlgorithmLet d*(j)denote the shortest path distancefromnode1tonodej.Dijkstras algorithm will determine d*(j)foreachj,inorderof increasingdistancefromtheoriginnode1.S denotes the set of permanently labelednodes.Thatis

19、,d(j)=d*(j)forjS.T denotes the set of temporarily labelednodes.Thatis,d(j)d*(j)forj T.Dijkstras AlgorithmbeginS:=1;T=N1;d(1):=0andpred(1):=0;d(j)=forj=2ton;update(1);whileSNdobegin(node selection,also called FINDMIN)letiTbeanodeforwhichd(i)=mind(j):j T;S:=Si;T:=Ti;Update(i)end;end;Why Does Dijkstras

20、 Algorithm Work?Astandardmethodforprovingcorrectness.1.Determinethingsthataretrueateachiteration.Thesearecalledinvariants.2.Proveinvariantsusinginduction3.Provethatthealgorithmisfinite4.Chooseinvariantssothatthealgorithmscorrectnessfollowsdirectlyfromtheinvariantsandthefactthatthealgorithmterminates

21、.Why Does Dijkstras Algorithm Work?nInvariantsforDijkstrasAlgorithmqIfjS,thend(j)istheshortestdistancefromnode1tonodej.qIfiS,andjT,thend(i)d(j).qIfjT,thend(j)isthelengthoftheshortestpathfromnode1tonodejinSj.Note:S increases by one node at a time.So,at the end the algorithm is correct by invariance 1

22、.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.123456242 1342 321024 Consider S=1 and after update(1)Verifying invariants Inductively12462

23、42 1342 a2032364 562.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 Inductively1246242 1342 a2032364 56To show

24、: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 prov

25、e 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 Inductively1246242 1342 a2032364 56To show:3.If j T,then d(j)is the length of the

26、 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).W

27、e 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 invariantsnItisthestandardwaytopr

28、ovethatalgorithmswork.nFindingthebestinvariantsfortheproofisoftenchallenging.nAreasonablemethod.Determinewhatistrueateachiteration(bycarefullyexaminingseveralusefulexamples)andthenusealloftheinvariants.nThenshortentheprooflater.Complexity Analysis of Dijkstras AlgorithmnUpdateTime:update(j)occursonc

29、eforeachj,upontransferringjfromTtoS.ThetimetoperformallupdatesisO(m)sincethearc(i,j)isonlyinvolvedinupdate(i).nFindMinTime:Tofindtheminimum(inastraightforwardapproach)involvesscanningd(j)foreachjT.qInitiallyThasnelements.qSothenumberofscansisn+n-1+n-2+1=O(n2).nO(n2)timeintotal.Thisisthebestpossibleo

30、nlyifthenetworkisdense,thatismisaboutn2.nWecandobetterifthenetworkissparse.图13.10最短路径举例13.3.6最小生成树n具有n 个顶点的连通的无向图G,图的每条边e有一非负权值c(e),也称为成本,求有最小成本的生成树.n每个生成树刚好具有n-1条边，所以问题是用某种方法选择n-1条边使它们形成G的最小生成树。n我们采用以下二种不同的贪心策略来选择这n-1条边。n这二种贪心策略对应求解最小生成树的二个算法：Kruskals算法，Prims算法。Kruskals算法n贪心策略:每次选择权值c(e)最小且与以前选择的边不

31、构成cycle的边e.n上述策略要求按权值从小到大对边排序.图13.12构造最小生成树图13.12构造最小生成树（续1）图13.12构造最小生成树（续2）图13.13 Kruskals算法的伪代码正确性证明n利用类似装载问题所用的变换技术可以证明图13.13的贪心法总能建立一棵最小生成树.n需要证明：q只要图是连通的,Kruskals算法总能产生一棵生成树;q产生的生成树具有最小成本.证明n设T是贪心法产生的解，U是优化解n设e是属于T但不属于U的成本最小的边;换言之,T中成本小于c(e)的边都在U中.n设f是e+U产生的环路上不在T中的一条边,这样的f一定在,否则T将包含一个环路.nc(f)

32、的不小于c(e):n因T中比e成本小的边都在U中,所以f与T中成本小于e的成本的边(这些边都在U里)不构成环路;如果f的成本小于e的成本,贪心法会先于e将f加入到T中,矛盾.n从U中删除f并加入e,得到的树U仍是优化的.数据结构n使用UNIONFIND数据结构n初始为单个顶点的集合n对每条边做2次FIND找到边的端点所在的集合;如果在同一集合中则舍弃该条边,否则将2个集合合并(UNION)n算法可在O(n+eloge)找出最小生成树:边排序:O(eloge)initializing:O(n)union-find:O(e)Prims算法n设A为算法执行过程中产生的生成树中的顶点.初始化A包含图中

33、任一顶点;nV-A作成一个优先级队列Q,关键字值取为连接该顶点和A的边的最小权值.n每步从Q中取出关键字值最小的顶点u,将其加入A;n修改Q中与u相邻的顶点的关键字值.n该算法不要求对边排序。n算法的伪代码如下:Prims 算法图13.5图13.15 Prims算法的步骤Prims算法的步骤（续）Analysis Analysis nExtractminneedsatmost(log|V|)nDecreasekeyneeds(|E|)nTotaltimeis(|V|log|V|+|E|)小结n贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。