算法设计与分析 课件 第五章 贪心法 5.2.1 活动安排问题.ppt

计算机算法设计与分析第5章贪心法5.2.1活动安排问题学校有n个分工会需要进行节目彩排活动安排，学校彩排舞台只有一个。每个分工会都有自己的一个空闲时间段，即每个分工会都给出自己可以进行彩排活动的一个起始时间和结束时间。而学校的舞台同一时间只能安排一个分工会入场进行活动。如何安排这次彩排活动，使得被安排的分工会尽可能多，没有能安排的分工会只能放到下次安排。活动安排问题设学校分工会节目彩排活动编号的集合为E={1,2,...,n}，第i个分工会节目彩排活动的起始时间为si，结束时间为fi，且sifi。如果安排了第i个分工会进行彩排，则它在半开时间区间[si，fi)内占用舞台资源。当两个活动区间[si，fi)与[sj，fj)不相交，则称活动i和活动j是相容的，即si≥fj或sj≥fi，i≠j，活动i和活动j相容。活动安排问题是求解两两相容的最大活动子集S。活动安排问题分工会i1234567891011起始时间si130535688212结束时间fi4567891011121314贪心策略1：更早的活动起始时间优先策略，这样可以增大舞台资源利用率。按照活动的起始时间先后顺序选择活动。如表所示的11个活动，先安排活动3，则活动1、2、4、5、6、10与活动3均不相容；之后安排与活动3相容的具有更早起始时间的活动7，则活动8、9与活动7均不相容；之后安排与活动7相容的具有更早起始时间的活动11，安排结束。贪心策略1安排的相容活动集合S={3,7,11}。分工会i1234567891011起始时间si130535688212结束时间fi4567891011121314活动安排问题贪心策略2：更早的活动结束时间优先策略，这样可以下一个活动尽早得到安排。按照活动结束时间从小到大顺序选择活动，表中的活动已经按活动结束时间顺序从小到大排序。选择活动1，之后选择与活动1相容活动4，之后选择与活动4相容的活动8，最后选择与活动8相容的活动11，安排结束。贪心策略2安排的相容活动集合S={1,4,8,11}。分工会i1234567891011起始时间si130535688212结束时间fi4567891011121314活动安排问题活动安排问题贪心策略2的正确性证明：将n个活动按照其结束时间fi从小到大排序，排序后的活动序列还是按E={1,2,...,n}编号。第一次先选1号活动，然后接下来的每一步，从E中按顺序选出下一个相容的活动，直到E中所有活动都被检查过一遍。证明贪心策略2能得到活动安排问题的最优解，即考察如下问题：该算法执行到第k步时，选择了k个活动：i1,i2,...,ik，则存在最优解S包含这k个活动，即该算法执行的每一步的结果都是最优解的一部分。活动安排问题（1）设S是E的一个最优解且S={i1,...,im}。若最优解S的第一个活动i1≠1，由于活动1的结束时间是活动集合E中最前面的，因此。这样，就将S中的i1换成1，得到S：由于，因此S中的活动也是相容的，而且活动数量与S中一致，故S也是一个最优解。也即E中的第1步选择活动1肯定可以在一个最优解中。活动安排问题（2）采用数学归纳法证明，若第k步选择的活动ik在最优解中，则第k+1步选择的活动ik+1也在最优解中。归纳假设第?k步选择的活动ik在最优解中，可以表述为：前?k?步已经选择的活为i1,i2,...,ik，存在一个最优解S：第k+1步时，选择只能在待选活动集合E中选取，所谓待选活动集合，即原集合E中去除已判为冲突的活动和已选择的活动后剩下的集合。活动安排问题①那么，B是E（子问题）的一个最优解。若不是，假设E的有解是B*，且B*B，那么用B*替换B以后得到，则SS，与S是最优解矛盾。故②根据（1）的证明，贪心策略2的第一步选择结束时间最早的活动总是导致问题的一个最优解，故对于子问题E存在一个最优解B，包含子问题E的第一个活动ik+1。因B和B都是E的最优解,B=B，所以：S和S是包含的活动数量一样的原问题的最优解，因此得证第k+1步选择的活动ik+1在最优解中。即按贪心策略2进行选择的活动必将导致问题的一个最优解是成立的。活动安排问题效率分析:问题的输入规模为n，按活动结束时间从小到大高效排序的时间复杂度为O(nlogn)，贪心算法选择活动n步即可完成，故T(n)=O(nlogn)。