《贪心法(TheGreedyMethod).ppt》由会员分享，可在线阅读，更多相关《贪心法(TheGreedyMethod).ppt（74页珍藏版）》请在三一办公上搜索。
1、贪心法（The Greedy Method）,宫秀军天津大学计算机科学与技术学院http:/,提纲,最优化问题(Optimization problem)贪心算法基本原理(The principle of greedy method)贪心算法应用货箱装船问题（Container Loading)背包问题（Knapsack Problem）拓扑排序问题(Topological Sorting)最短路径问题(Shortest Path)最小代价生成树(Minimum Spanning Tree)本章小结,13.1优化问题,一个优化问题可以描述如下:问题的解可表示为一复杂的结构，例如元组形式约束条件
2、(结构性的约束条件使约束条件为true的元组称为可行解（feasible solution）目标函数 优化解即指使目标函数极大化(或极小化)的可行解，对应的目标函数值称为优化值。很多优化问题是NP难度问题，迄今找不到它们的多项式算法。所以计算上可行的方法就是求其近似解。贪心法是求近似算法的主要途径之一。,例13.1Thirsty Baby,有一个聪明的婴儿，她可能得到的饮料包括一桶水、一桶牛奶、多罐不同种类的果汁、许多不同的装在瓶子或罐子中的苏打水。假定婴儿可得到n 种不同的饮料。根据以前关于这n 种饮料的不同体验，婴儿知道其中那些饮料更合自己的胃口。因此，婴儿为每一种饮料赋予一个满意度值si
3、：饮用1盎司第i 种饮料，满意度si。设第i种饮料有ai盎司，婴儿共需喝t盎司饮料,例13.1Thirsty Baby,设xi 为第i种饮料的饮用量，假定满意程度是可加的，则最满意的选择是极大化 该优化问题可表示如下约束条件目标函数,例13.2loading Problem,一艘船准备用来装载货物,所有货物都放在集装箱中。设第i 个集装箱的重量为wi（1in），船的最大载重量为c，试设计一装载方法使得装入的集装箱数目最多。,例13.2 Loading Problem,用n维布尔向量代表一种装箱方案约束条件 目标函数极大化目标函数,例13.3 最小成本通信网络,城市之间的通信网络应是以这些城市为
4、顶点的连通图,图的每条边代表一条通信线路.给每条边赋予一个权值,等于建设这条通信线路所要花费的成本,最小成本通信网络问题就是找这样一个连通图,其总成本最小.设所有的权值都非负,则最小成本通信网络问题的可行解可限制为连接这些城市的生成树,而最优解是其中具有最小成本的生成树.,例13.3 最小成本通讯网络,n-1 条边的元组约束条件：这些边构成生成树目标函数：边权之和原则上所有上述问题需在很大的范围内搜索优化解；但这常常导致指数复杂度的算法；是计算上不可接受的。贪心法退而求其次求所谓的“次优”解。,13.2 贪心法,贪心法指每步(stage)按所谓的“贪心标准(策略)”选择(元组的)一个分量，逐步
5、构造出问题解的方法。贪心法的主要特点是：分阶段完成：按一定的步骤，每步决定一个分量（自顶向下）不回溯：选定一个分量后,不重试其它可能贪心标准：指每次选择一个分量时使用的“优化”策略。所选策略可能导致优化解，但更多情形是得到近似解，特别是对NP难度问题。不同的人可能有不同的“优化”策略。常常采纳使目标函数有最大增量的策略为贪心策略。基本要素贪心选择性质:所求问题的整体最优解可以通过一系列局部最优选择(贪心选择)来达到最优子结构性质：问题的最优解包含其子问题的最优解,例13.4找零钱,一个小孩买了价值少于1美元的糖，并将1美元的钱放入取款机。取款机要用数目最少的硬币将零钱找给小孩。假设取款机内有任
6、意多的面值为25美分、10美分、5美分、及1美分的硬币。贪心策略为：每次给出不超过应找钱数的面值最大的硬币。贪心策略得到优化解:20-25美分之间：选2个10美分最好.25-30美分之间选一个25最好;30美分：一个25加一个5美分等等.硬币面值之间有倍数关系;否则没解:例如,面值14,12,5和1;则17125,用2枚硬币,而贪心法为14加3个1,共4枚硬币.,例13.5 机器调度,现有n 个任务和足够多台处理这些任务的机器。每个任务的开始时间为si，完成时间为fi（sifi）si,fi 为处理任务i 的时间区间。两个任务i，j 重叠是指两个任务的时间区间有重叠。例如：区间1,4与区间2,5
7、重叠，而与区间4,7不重叠。可行的任务分配分配中不会将重叠的任务分配给同一台机器。每台机器在任何时刻最多只处理一个任务。最优分配指占用机器数最少的可行分配。,图13-1 任务及三台机器的调度a)7个任务 b)调度,例13.5(续),贪心算法：步骤：按任务起始时间排序并安排任务贪心准则：尽可能使用旧机器，即以前使用过的机器上述贪心法产生优化解，因为：任何可行解使用的机器数不少于最大重迭任务数贪心解使用的机器数不超过最大重迭任务数实现问题：使用min-堆存放每台旧机器的可用时间,即此时间以后可安排新任务算法的时间复杂度为(nlogn),例题13.6(最短路算法),选择“最近”的且不在路径上的下一节
8、点贪心解不是优化解:,13.3应用,货箱装船问题（Container Loading)背包问题（Knapsack Problem）拓扑排序问题(Topological Sorting)最短路径问题(Shortest Path)最小代价生成树(Minimum Spanning Tree),13.3.1 Container loading,问题目标函数：装载的集装箱数目极大化目标函数贪心策略船可以分步装载，每步装一个集装箱，且需要考虑装载哪一个集装箱。贪心标准：在剩下的集装箱中选择有最小重量的集装箱实现算法首先按重量对物品排序按贪心策略装箱,程序13.1,程序13.1（续）,定理13.1,上述贪心
9、法产生的解是优化解:优化解(y1,yn)可经有限次替换得到贪心解,而且每次替换箱子数不变.如该优化解不会箱子1,将其替换其中一个箱子,仍是优化解.(必须替换,否则不是优化解)反复替换将得到一个优化解,它就是贪心法得到的解.,13.2.2 0/1背包问题,0/1背包问题：设有容量c的背包，和n件物品，物品i的重量为wi，假定装入物品i获得的效益值为pi,试给出一装入物品的方法，使得获得的总效益值最大。集装箱装载问题是0/1背包问题的特例。0/1背包问题是NP难度问题。所以贪心法产生的解是近似解。,13.2.2 0/1背包问题,可行解元组表示xi=1表示物品i 装入背包中，xi=0 表示物品i 不
10、装入背包。问题目标函数：装入物品效益值 约束条件：求解：极大化目标函数，计算xi的值,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
11、贪心策略3：按密度pi/wi，从剩余物品中选择可装入背包的密度值最大的物品，这种策略也不能保证得到最优解:n=3,c=30,w=20,15,15,p=40,25,25贪心解为1,0,0,但优化解为0,1,1,(续),密度贪心法的伪代码:(1)将物品按密度从大到小排序(2)for(i=1;in;i+)if(物品i 可装入到背包内)xi=1(装入)else xi=0(舍弃);例如:c=11,w=(2,4,6,5),p=(6,10,12,9)x=(1,1,0,1).恰是优化解算法的时间复杂度为O(nlogn),(续),贪心法往往不能得到精确解，贪心解与最优解的误差用以下比值的百分比来度量:(优化值-
12、贪心解值)/优化值n=2,c=y,w=1,y,p=10,9y贪心解值10；当y10/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。k2：当k=0时，同于前述的密度贪心法。因此解为x=1,1,0,0，效益值为16。,例13.9(续1）,k=1时。初始子集为
13、1,2,3,4。子集1,2产生与k=0时相同的结果：x=1,1,0,0，效益值为16。考虑子集3，置x3 为1。此时还剩5个单位的容量，按价值密度非递增顺序来考虑如何利用这5个单位的容量。首先考虑物品1，它适合，因此取x1为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，除了考虑k2的子集，还必需
14、考虑子集1,2,1,3,1,4,2,3,2,4和3,4。对于1,2，可行解为1,1,0,0，最优值为16对于1,3，可行解为 1,0,1,0，最优值为18对于1,4，可行解为 1,0,0,1，最优值为19对于2,3，可行解为 0,1,1,0，最优值为22对于2,4，可行解为 1,0,0,1，最优值为233,4是不可行的2-优化解即为0,1,0,1,值为23,n=4,c=11，w=2,4,6,7,p=6,10,12,13,例13.9结论,k-优化方法（k0)得到的解误差不超过(100/(k+1)当k=1时,为50%以内,即如优化值为100,贪心法算出的值不低于50;当k=2时,为33.33%以内
15、.算法的时间复杂度随k 的增大而增加,需要测试的子集数目为O(nk),每一个子集所需时间为O(n),因此当k 0时总的时间开销为O(nk+1)。,13.3拓扑排序,拓扑排序定义：,任务的先后顺序可用有向图表示,称为AOV网络(Activity On Vertex).有向图的顶点代表任务,有向边(i,j)表示先后关系:任务i完成后才能开始任务j.根据上述AOV网络我们要对任务进行排序使得排序序列的先后关系与AOV网定义的先后关系一致.根据任务的有向图建立拓扑序列的过程称为拓扑排序.,13.3拓扑排序,对所有顶点的排列逐个检验的方法是不足取的:O(n!)的时间复杂度.假设从空集开始，每步产生拓扑排
16、序序列中的一个顶点w,怎样选择顶点w？greedy策略:从不在拓扑序列的顶点中选择一顶点w,其所有先行节点v都在已产生的拓扑序列中(或无先行顶点).用减入度的方法确定w:入度变成0的顶点,使用栈的伪代码,(1)计算每个顶点的入度(2)将入度为0的顶点入栈(3)While(栈不空)任取一入度为0的顶点放入拓扑序列中;将与其相邻的顶点的入度减1;如有新的入度为0的顶点出现,将其放入 栈中;(4)如有剩余的顶点则该图有环路,引理13.1,如果伪代码13.5失败，则有向图含有环路。证明：当失败时|V|n,且剩下的顶点不能加入已排好的序列V中，因此至少有一顶点q1不在V中，和一条边(q2,q1)且q2不
17、在V中；否则q1可加入V中。同样，有边(q3,q2）且q3不在V中。若q3=q1 则q1q2q3 是有向图中的一个环路；若q3q1，则必存在q4，（q4,q3）是有向图的边且q4不在V中，否则，q3已在V中。若q4为q1,q2,q3 中的任何一个，则该有向图含有环；因为有向图有有限个顶点，重复上述步骤，一定能找到一个环路。,伪代码13.5 拓扑排序,程序13.2拓扑排序,程序13.2拓扑排序（续1）,程序13.2拓扑排序（续2）,算法的时间复杂度,(n2):使用邻接矩阵;(n+e):使用邻接表;初始入度数组 O(n);计算入度:遍历邻接表O(e)(访问链表的下一节点,入度数组对应项加1合起来视
18、为一步,时间O(1);进出栈次数:O(n);每步修改入度时间为O(相邻的边数);总的修改入度时间为O(e).,单源最短路径,任给一有向图G,它的每条边都有一个非负的权值aij,路径的长度即为此路径上边的权值之和.对于给定的源顶点s,需找出从它到图中其他任意顶点（称为目的）的最短路径.IP路由使用最短路算法(OSPF：Open Shortest Path First).,Dijkstras 最短路算法,Dijkstras 最短路算法是图论算法中应用最为广泛的算法.算法反复使用label update方法.算法的正确性证明-有普遍意义.算法的时间复杂度分析-有普遍性.,A Key Step in
19、Shortest Path Algorithms,In this lecture,and in subsequent lectures,we let d()denote a vector of temporary distance labels.d(i)is the length of some path from the origin node 1 to node i.Procedure Update(i)for each(i,j)A(i)doif d(j)d(i)+cij then d(j):=d(i)+cij and pred(j):=i;Update(i)is used in Dijk
20、stras algorithm and in the label correcting algorithm,Update(7),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 a
21、n 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.,Dijkstras Algorithm,Let d*(j)denote the shortest pa
22、th 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 Algo
23、rithm,beginS:=1;T=N 1;d(1):=0 and pred(1):=0;d(j)=for j=2 to n;update(1);while S N dobegin(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 th
24、at are true at each iteration.These are called invariants.Prove invariants using inductionProve that the algorithm is finiteChoose invariants so that the algorithms correctness follows directly from the invariants and the fact that the algorithm terminates.,Why Does Dijkstras Algorithm Work?,Invaria
25、nts for Dijkstras AlgorithmIf 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.,Verif
26、ying 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,0,2,4,Consider S=1 and after update(1),Verifying invariants Induct
27、ively,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,
28、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 n
29、eed 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,To show:3.If j T,then d(j)is the length of the shortest p
30、ath 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
31、 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 pr
32、ove 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 Algori
33、thm,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 n
34、umber of scans is n+n-1+n-2+1=O(n2).O(n2)time in total.This is the best possible only if the network is dense,that is m is about n2.We can do better if the network is sparse.,图13.10最短路径举例,最小生成树,具有n 个顶点的连通的无向图G,图的每条边e有一非负权值c(e),也称为成本,求有最小成本的生成树.每个生成树刚好具有n-1条边，所以问题是用某种方法选择n-1条边使它们形成G的最小生成树。我们采用以下二种不同的
35、贪心策略来选择这n-1条边。这二种贪心策略对应求解最小生成树的二个算法：Kruskals算法，Prims算法。,Kruskals算法,贪心策略:每次选择权值c(e)最小且与以前选择的边不构成cycle的边e.上述策略要求按权值从小到大对边排序.,图13.12构造最小生成树,图13.12构造最小生成树（续1）,图13.12构造最小生成树（续2）,图13.13 Kruskals算法的伪代码,正确性证明,利用类似装载问题所用的变换技术可以证明图13.13的贪心法总能建立一棵最小生成树.需要证明：只要图是连通的,Kruskals算法总能产生一棵生成树;产生的生成树具有最小成本.,证明,设T是贪心法产生
36、的解，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仍是优化的.,数据结构,使用UNIONFIND数据结构初始为单个顶点的集合对每条边做2次FIND找到边的端点所在的集合;如果在同一集合中则舍弃该条边,否则将2个集合合并(UNION)算法可在O(n+eloge)找
37、出最小生成树:边排序:O(eloge)initializing:O(n)union-find:O(e),Prims算法,设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|),小结,贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。,
