证明反证法

UniversityofScienceandTechnologyofChina主讲人：吕敏Email:{[e-mail]}Spring2012，USTC算法基础UniversityofScienceandTechnologyofChina2020/3/152第十讲贪心算法内容提要：理解贪心算法的概念掌握贪心算法的基本要素理解贪心算法与动态规划算法的差异通过范例学习贪心算法设计策略UniversityofScienceandTechnologyofChina10.1活动安排问题2020/3/153当一个问题具有最优子结构性质时，可用动态规划法求解，但有时用贪心算法求解会更加的简单有效。顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。UniversityofScienceandTechnologyofChina10.1活动安排问题2020/3/154设有n个活动的集合E={1,2,…,n}，每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且sifi。如果选择了活动i，则它在半开时间区间[si,fi)内占用资源。若区间[si,fi)与区间[sj,fj)不相交，则称活动i与活动j是相容的。即当si≥fj或sj≥fi时，活动i与活动j相容.问题：选出最大的相容活动子集合。UniversityofScienceandTechnologyofChina10.1活动安排问题2020/3/155（用动态规划方法）步骤1：分析最优解的结构特征—构造子问题空间:Sij={ak∈S:fi≤skfk≤sj}Sij包含了所有与ai和aj相兼容的活动，并且与不迟于ai结束和不早于aj开始的活动兼容。此外，虚构活动a0和an+1，其中f0=0,Sn+1=∞。原问题即为寻找S0,n+1中最大兼容活动子集。UniversityofScienceandTechnologyofChina10.1活动安排问题2020/3/156—证明原问题具有最优子结构性质。即：若已知问题Sij的最优解Aij中包含活动ak，则在Sij最优解中的针对Sik的解Aik和针对Skj的解Akj也必定是最优的。（反证法即可！）—证明可以根据子问题的最优解来构造出原问题的最优解。一个非空子问题Sij的任意解中必包含了某项活动ak，而Sij的任一最优解中都包含了其子问题实例Sik和Skj的最优解（根据最优子结构性质！）。因此，可以构造出Sij的最大兼容子集。UniversityofScienceandTechnologyofChina10.1活动安排问题2020/3/157步骤2：递归地定义最优解的值设c[i,j]为Sij中最大兼容子集中的活动数。当Sij=φ时，c[i,j]=0。对于一个非空子集Sij，如果ak在Sij的最大兼容子集中被使用，则子问题Sik和Skj的最大兼容子集也被使用。从而：c[i,j]=c[i,k]+c[k,j]+1由于Sij的最大子集一定使用了i到j中的某个值k，通过检查所有可能的k值，就可以找到最好的一个。因此，c[i,j]的完整递归定义为：SijjkckicSijjicjki}1],[],[{max0],[UniversityofScienceandTechnologyofChina10.1活动安排问题2020/3/158问题：k有j-i-1种选择，每种选择会导致2个完全不同的子问题产生，因此，动态规划算法的计算量比较大！！！一个直观想法是直接选择k的值，使得一个子问题为空，从而加快计算速度！这就导致了贪心算法！UniversityofScienceandTechnologyofChina10.1活动安排问题2020/3/159（用贪心算法）贪心策略：对输入的活动以其完成时间的非减序排列，算法每次总是选择具有最早完成时间的相容活动加入最优解集中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：i1234567891011S[i]130535688212f[i]4567891011121314UniversityofScienceandTechnologyofChina10.1活动安排问题2020/3/1510UniversityofScienceandTechnologyofChina10.1活动安排问题2020/3/1511Recursive-Activity-Selector(s,f,i,j){①m←i+1;②whilemjandsmfi③dom←m+1④ifmj⑤thenreturn{am}URecursive-Activity-Selector(s,f,m,j)⑥elsereturnφ}说明：1）数组s和f表示活动的开始和结束时间，n个输入活动已经按照活动结束时间进行单调递增顺序排序；2）算法②~③目的是寻找Sij中最早结束的第一个活动，即找到与ai兼容的第一个活动am，利用am与Smj的最优子集的并集构成Sij的最优子集；3）时间复杂度O(n)。UniversityofScienceandTechnologyofChina10.1活动安排问题2020/3/1512Recursive-Activity-Selector属于递归性贪心算法，它以对自己的递归调用的并操作结束，几乎就是“尾递归调用”，因此可以转化为迭代形式：Greedy-Activity-Selector(s,f){n←length[s];A←{a1}i←1//下标i记录了最近加入A的活动aiform←2ton//寻找Si,n+1中最早结束的兼容活动doifsm≥fithenA←AU{am}i←mreturnA;}UniversityofScienceandTechnologyofChina10.1活动安排问题2020/3/1513贪心算法的正确性证明：定理16.1：对于任意非空子问题Sij，设am是Sij中具有最早结束时间的活动，即fm=min{fk:ak∈Sij}，则：1）活动am在Sij的某最大兼容活动子集中被使用；2）子问题Sim为空，所以选择am将使子问题Smj为唯一可能非空的子问题。UniversityofScienceandTechnologyofChina10.1活动安排问题2020/3/1514定理16.1：对于任意非空子问题Sij，设am是Sij中具有最早结束时间的活动，即fm=min{fk:ak∈Sij}，则：1）活动am在Sij的某最大兼容活动子集中被使用；2）子问题Sim为空，所以选择am将使子问题Smj为唯一可能非空的子问题。证明：先证第2部分。假设Sim非空，因此有活动ak满足fi≤skfk≤smfm。ak同时也在Sij中，且具有比am更早的结束时间，这与am的选择相矛盾，故Sim为空。UniversityofScienceandTechnologyofChina10.1活动安排问题2020/3/1515定理16.1：对于任意非空子问题Sij，设am是Sij中具有最早结束时间的活动，即fm=min{fk:ak∈Sij}，则：1）活动am在Sij的某最大兼容活动子集中被使用；2）子问题Sim为空，所以选择am将使子问题Smj为唯一可能非空的子问题。证明：再证第1部分。设Aij为Sij的最大兼容活动子集，且将Aij中的活动按结束时间单调递增排序。设ak为Aij的第一个活动。如果ak=am，则得到结论，即am在Sij的某个最大兼容子集中被使用。如果ak≠am，则构造子集Bij=Aij–{ak}U{am}。因为在活动Aij中，ak是第一个结束的活动，而fm≤fk，所以Bij中的活动是不相交的，即Bij中活动是兼容的。同时，Bij中活动个数与Aij中活动个数一致，因此Bij是包含am的Sij的最大兼容活动集合。UniversityofScienceandTechnologyofChina作业16.1-116.1-3UniversityofScienceandTechnologyofChina10.2贪心算法的基本要素2020/3/1517基本思想：从问题的某一个初始解出发，通过一系列的贪心选择——当前状态下的局部最优选择，逐步逼近给定的目标，尽可能快地求得更好的解。在贪心算法(greedymethod)中采用逐步构造最优解的方法。在每个阶段，都作出一个按某个评价函数最优的决策，该最优评价函数称为贪心准则(greedycriterion)贪心算法的正确性，就是要证明按贪心准则求得的解是全局最优解。UniversityofScienceandTechnologyofChina10.2贪心算法的基本要素2020/3/1518基本步骤：①决定问题的最优子结构；②设计出一个递归解；③证明在递归的任一阶段，最优选择之一总是贪心选择,那么，做贪心选择总是安全的。④证明通过做贪心选择，所有子问题（除一个以外）都为空。⑤设计出一个实现贪心策略的递归算法。⑥将递归算法转换成迭代算法。UniversityofScienceandTechnologyofChina10.2贪心算法的基本要素2020/3/1519对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质：贪心选择性质和最优子结构性质。一、贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解，否则得到的是近优解。UniversityofScienceandTechnologyofChina10.2贪心算法的基本要素2020/3/1520二、最优子结构性质当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。但是，需要注意的是，并非所有具有最优子结构性质的问题都可以采用贪心策略来得到最优解。UniversityofScienceandTechnologyofChina10.2贪心算法的基本要素2020/3/15210-1背包问题给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?小数背包问题与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。这2类问题都具有最优子结构性质，极为相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。UniversityofScienceandTechnologyofChina10.2贪心算法的基本要素2020/3/152