算法201304–GREEDY.ppt

活动安排问题 设有n个活动的集合E = {1, 2, …, n}，其中每个活动都要求使用同一资源，且在同一时间里只能有一个活动可以使用该资源。现要求给出一个活动安排，使得利用该资源活动为最多。 每个活动i都有使用该资源的一个启始时间si和一个结束时间fi，si＜fi，其占用资源的时间为半开区间[si , fi)。若区间[si , fi)与区间[sj , fj)不相交，则称活动i与活动j是相容的。 活动安排问题就是求E的最大相容活动子集。 活动安排问题的描述 用数组A分别存放所有活动的启始时间和结束时间以及是否予以安排的标记。 某项活动结束时间愈早，安排其它活动的剩余区间愈大。所以贪心策略为尽量选择结束时间早的活动来安排。 为此，将数组中的活动按结束时间的非减顺序排序，即f1≤f2≤…≤fn。 显然排序需要的时间为O(nlogn)。 活动安排问题的算法 ActionArragement(int n, Type A[][]) //A[i][0], A[i][1], A[i][3]分别为s, f和安排标记 { 将A依照A[i][1]的非减顺序排序； int j = 1; A[j][3] = 1; //先安排活动1 for (int i = 2; i = n; i++) { if A[i][0] = A[j][1] //若活动i与j相容 {A[i][3] = 1; j = i;} // 则安排活动i else A[i][3] = 0 } // 否则不安排活动i } 活动安排问题实例 设待安排的11个活动的始末时间排序如下： 贪心方法的抽象化控制 Procedure GREEDY(A,n) solution?Ф for i?1 to n do x?SELECT(A) if FEASIBLE(solution,x) then solution?UNION(solution,x) endif repeat return (solution) End GREEDY 贪心算法也能获得最优解 设活动集合E={1, 2, …, n}已经按结束时间的非减顺序排列，活动1具有最早结束时间。 首先，必定有一个最优解包含活动1。 贪心方法的数据选择策略(2) 先装入物品3, x3=1, p3x3 =15，再装入重量为10的物品2， ∑pixi =15+24*10/15=31。 0-1背包问题的形式化描述 问题的形式描述是：给定c＞0，wi＞0，vi＞0，1≤i≤n，求n元0-1向量(x1, x2, …, xn)，使得 问题3带有限期的作业排序 问题描述 假定只能在一台机器上处理n个作业，每个作业均可在单位时间内完成；又假定每个作业i都有一个截止期限di0(是整数)，当且仅当作业i在它的期限截止之前被完成时，则获得pi0的效益。 这个问题的一个可行解是这n个作业的一个子集合J，J中的每个作业都能在各自的截止期限之前完成，可行解的效益值是J中这些作业的效益之和∑pj 。具有最大效益值的可行解就是最优解。 带有限期的作业排序实例 例 n=4，(p1,p2,p3,p4) = (100,10,15,20) 和(d1,d2,d3,d4)=(2,1,2,1)，这个问题可能的可行解和它们的效益值为： 带限期的作业排序算法 为了得到最优解，应制定如何选择下一个作业的量度标准，利用贪心策略，使得所选择的下一个作业在这种量度下达到最优。 可把目标函数∑pj作为量度，则下一个要计入的作业将是使得在满足所产生的J是一个可行解的限制条件下使∑pj得到最大增加的作业，这一方法只要将各作业按效益pi降序来排列就可以了。 带限期的作业排序算法 作业按p1≥ p2≥ …≥ pn的次序输入： Procedure GREEDY_JOB(D,J,n) J?{1} for i?2 to n do if J∪{i}的所有作业都能在他们的截止期限前完成 then J?J∪{i} endif repeat End GREEDY_JOB 带有限期的作业排序实例 例 n=4，(p1,p2,p3,p4) = (100,10,15,20) 和(d1,d2,d3,d4)=(2,1,2,1)。利用上面的贪心算法解决此问题的过程如下： 先将各作业按照效益非增次序排列，即(p1 ,p4 ,p3 ,p2) = (100,20,15,10) ，(d1,d4,d3,d2)=(2,1,2,1)。初始化 D(0)=J(0)=0 ; k=J(1)=1; 将第一个