《贪心算法-ppt》由会员分享，可在线阅读，更多相关《贪心算法-ppt（77页珍藏版）》请在金锄头文库上搜索。
1、第四章.贪心算法(Greed method),例 题,算法设计与分析 贪心算法,顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。 目的：用以求解最优化问题,将问题的求解过程看作是一系列选择,每次选择一个输入,每次选择都是当前状态下的最好选择(局部最优解).每作一次选择后,所求问
2、题会简化为一个规模更小的子问题.从而通过每一步的最优解逐步达到整体的最优解。,4.1 基本思想,算法优点求解速度快,时间复杂性有较低的阶.,算法缺点需证明是最优解.,常见应用,背包问题,最小生成树,最短路径,作业调度等等,适用问题 具备贪心选择和最优子结构性质的最优化问题 贪心选择性质：整体的最优解可通过一系列局部最优解达到，即贪心选择到达。 贪心算法通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每做一次贪心选择就将所求解的问题化简为规模更小的问题 对于一个具体问题，要确定它是否具有贪心选择的性质，我们必须证明每一步所作的贪心选择最终导致问题的最优解。通常可以首先证明问题的一个整体
3、最优解，是从 贪心选择开始的，而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步作贪心选择，最终可得到问题的一个整体 最优解。 最优子结构性质：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。,某一问题的n个输入,该问题的一种解（可行解）,是A的一 个子集,满足一定 的条件,约束条件,目标函数,取极值,最优解,算法设计与分析 贪心算法,4.2.活动安排问题,算法设计与分析 贪心算法,活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪
4、心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。,问题陈述设有n个活动的集合E=1,2,n，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si fi 。如果选择了活动i，则它在半开时间区间si, fi)内占用资源。若区间si, fi)与区间sj, fj)不相交，则称活动i与活动j是相容的。也就是说，当sifj或sjfi时，活动i与活动j相容。,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
5、 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与已选择的活动相容,则添加此活动到相容活动子集.,活动安排问题贪心算法,template void GreedySelector(int n, Type s , Type f , bool A ) A 1 = true; int j = 1; /从第二个活动开始检查是否与前一个相容 for (int
6、i=2;i=fj) Ai = true; j=i; else A i = false; ,算法设计与分析 贪心算法,各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非减序排列,算法greedySelector 的计算过程如左图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。,由于输入的活动以其完成时间的非减序排列，所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排
7、时间段极大化，以便安排尽可能多的相容活动。 算法greedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。,T(n)=O(nlogn) (未排序时),算法分析,T(n)=O(n) (排序时),算法证明 算法达到最优解.,问题描述 输入:(x1,x2,.xn), xi=0,货箱i不装船; xi=1,货箱i装船 可行解: 满足约束条件 c 的输入 优化函数: 最优解:使优化函数达到最大值的一种输入.,4.3 最优装载,算法设计与分析 贪心算法,
8、算法思路 将装船过程划为多步选择，每步装一个货箱，每次从剩下的货箱中选择重量最轻的货箱.如此下去直到所有货箱均装上船或船上不能再容纳其他任何一个货箱。,例 设n=8，w1，w8=100, 200, 50, 90, 150, 50, 20, 80，c=400。 所考察货箱的次序为 :7, 3, 6, 8, 4, 1, 5, 2。货箱7, 3, 6, 8, 4, 1的 总重量为390个单位且已被装载, 剩下的装载能力为10 ,小于任意 货箱.所以得到解x1,.x8= 1, 0, 1, 1, 0, 1, 1, 1,1、最优装载的贪心算法,算法设计与分析 贪心算法,template void Load
9、ing(int x, Type w, Type c, int n ) int *t = new int n + 1; Sort(w, t, n) ; /按货箱重量排序/ for (int i = 1; i = n; i +) xi = 0; for (int i = 1;i= n /调整剩余空间 ,2、贪心选择性质 可以证明最优装载问题具有贪心选择性质。 3、最优子结构性质 最优装载问题具有最优子结构性质。 算法证明:由最优装载问题的贪心选择性质和最优子结构性质，容易证明算法loading的正确性。 算法分析:算法loading的主要计算量在于将集装箱依其重量从小到大排序，故算法所需的计算时间
10、为 O(nlogn)。,最优化描述 找一个n元向量(x1,xn) 0 xi 1 使得 且 .其中 C, Wi, vi0 , 1 i n,4-4 背包问题 (Knapsack Problem),问题描述设有n个物体和一个背包,物体i的重量为wi ,价值为vi ,背包的容量为C.若将物体i的xi部分(1in, 0xi1)装入背包,则具有价值为vi xi. 目标是找到一个方案,使放入背包的物体总价值最高.,约 束 条 件,优化函数,算法设计与分析 贪心算法,背包问题实例,考虑下列情况的背包问题 n=3,M=20,(v1,v2,v3)=(25,24,15), (w1,w2,w3)=(18,15,10)
11、 其中的4个可行解是：,算法设计与分析 贪心算法,贪心方法的数据选择策略(1),1、用贪心策略求解背包问题时，首先要选出最优的度量标准。可以选取目标函数为量度标准，每装入一件物品就使背包获得最大可能的效益值增量。在这种量度标准下的贪心方法就是按效益值的非增次序将物品一件件放到背包中。 如上面的实例所示，可将物品按效益量非增次序排序： (v1,v2,v3)=(25,24,15)。先装入物品1重量为18，即x1=1；然后再装物品2，由于约束条为wi xi M=20，所以物品2只能装入重量为2的一小部分，即x2=2/15。 按上述的数据选择策略，装入顺序是按照物品的效益值从大到小的输入，由刚才的方法
12、可得这种情况下的总效益值为vixi = 25+24*2/15=28.2，显然是一个次优解，原因是背包容量消耗过快。,算法设计与分析 贪心算法,贪心方法的数据选择策略(2),2、若以容量作为量度，可让背包容量尽可能慢地被消耗。这就要求按物品重量的非降次序来把物品放入背包，即(w3,w2,w1)=(10,15,18)。 先装入物品3, x3=1, p3x3 =15，再装入重量为10的物品2， vixi =15+24*10/15=31。 由刚才的方法可得这种情况下的总效益值为31，仍是一个次优解，原因是容量在漫漫消耗的过程中，效益值却没有迅速的增加。,算法设计与分析 贪心算法,贪心方法的数据选择策略
13、(3),3、采用在效益值的增长速率和容量的消耗速率之间取得平衡的量度标准。即每一次装入的物品应使它占用的每一单位容量获得当前最大的单位效益。这就需使物品的装入次序按vi/wi比值的非增次序来考虑。 这种策略下的量度是已装入物品的累计效益值与所用容量之比。 (v2/w2 , v3/w3 , v1/w1 )=(24/15,15/10, 25/18) 先装入重量为15的物品2，再装入重量为5的物品3， pixi =24+15*5/10=31.5。此结果为最优解。,算法设计与分析 贪心算法,算法思路1).将各物体按单位价值由高到低排序. 2).取价值最高者放入背包. 3).计算背包剩余空间. 4).在
14、剩余物体中取价值最高者放入背包. 若背包剩余容量=0或物体全部装入背包为止,例 n=3,c=20 (v1,v2,v3)=(25,24,15),(w1,w2,w3)=(18,15,10),x1,x2,x3, 0,2/3,1,0,1,1/2,.,1,2/15,0,20,20,20,28.2,31,31.5,.,.,算法设计与分析 贪心算法,void Knapsack(int n,float M,float v ,float w ,float x ) Sort(n, v, w,t); /按单位价值排序/ int i; for (i =1;i c) break; xti= 1; c-= wti; if
15、(i= n) xti = c/wti; ,背包问题的贪心算法,算法设计与分析 贪心算法,算法分析:,排序为主要算法时间,所以 T(n)=O(nlogn),背包问题中的物体不能分拆,只能整个装入称为0-1背包问题.,算法证明:该算法能得到在最优解,用贪心算法能得到0-1背包的最优解吗?,首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。 具体算法可描述如下页：,void Knapsack(int n,float M,float v,float w,float x) Sort(n,v,w); int i; for (i=1;ic) break; xi=1; c-=wi; if (i=n) xi=c/wi; ,算法knapsack的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为 O（nlogn）。 为了证明算法的正确性，还必须证明背包问题具有贪心选择性质。,对于0-1背包问题，贪心选择之所
