贪心算法详解

た入场券 2023-10-17 16:14 17阅读 0赞

贪心算法在解决问题的策略上目光短浅，只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。也就是说贪心对于算法的每一个决策点，每一次的选择，做一个当时看起来是最佳的选择。它并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。贪心算法对于大部分的优化问题都能产生最优解，但不能总获得整体最优解，通常可以获得近似最优解。
    	我们先从DP来过渡到贪心，先来看一个例子，活动选择问题。
    	假设有一个需要使用某个资源（教师等场地）的n个活动组成的集合S= {a1，a2，···，an }，该资源每次只能由一个活动占用。每个活动a[i]都有一个开始时间s[i]和结束时间f[i]，且0<= s[i] < f[i] <∞。一旦被选择后，活动a[i]就占据半开时间区间[s[i],f[i]）。若时间区间[s[i], fi)与区间[sj, fj)互不重叠，则称活动a[i]与活动a[j]是兼容的。也就是说，当s[i]≥f[j]或s[j]≥f[i]时，活动a[i]与活动a[j]相容。活动选择问题就是要选择一个由兼容活动构成的最大集合。
    例子
    
    	活动都按结束时间非递减排序了（后面会讲why），这个例子的最大集合就是{a[1],a[4],a[8],a[11]}和{a[2],a[4],a[9],a[11]}。

很容易看出来这是一个DP问题，跟之前的求数组中最长递增子序列是类似的。状态转移方程就是LIS[i]=max{1,LIS[k]+1}   (a[i]和a[k]是兼容的for any k < i)。而且更重要的是我们还可以根据结束时间给每一个活动排序，这样代码就更容易写出来，这里就不贴了。

如果是这个DP方程的话，我们是没法从DP过渡到贪心的。我们再来看一个更好的DP算法。
    	既然是DP，肯定要找状态转移方程。不过我们先来寻找子问题，什么是这个原问题的子问题呢？我们刚才说到，活动选择问题就是要选择一个由兼容活动构成的最大集合。子问题是什么，兼容活动集合，这样的子问题有2^n。所以我们才用DP来优化它，如果子问题的最优解可以构造成原问题的最优解，那么此问题就具有最优子结构。
    	定义S[i,j]={a[k]∈S:f[i]<=s[k]<f[k]<=s[j]}(S是所有活动集合)。S[i,j]就是原问题集合S的子问题，其中的每个活动都是在活动a[i]结束之后开始，且在a[j]开始之前结束。更重要的是S[i,j]中的活动都要相互兼容。为了表示完整的问题结合，虚构两个活动a[0],a[n+1],f[0]=0,s[n+1]=∞。这样S=S[0，n+1]。

为了减少问题的处理量，给所以的活动按结束时间递增的顺序排序。这样的话如果i>=j,S[i,j]=∅。为啥呢？因为这是不可能的，假设有一个a[k]∈S[i,j],则f[i]<=sk<fk<=sj。说明a[i]活动排在a[j]活动前面，也即是i<j。这与i>=j矛盾。所以来说，如果将活动按结束时间非递减排序的话，则子问题就是S[i,j]，0<=i<j<=n+1,其他的S[i,j]是空集。
    	针对于S[i,j]中的a[k]，我们把子问题分成S[i,k],S[k,j]和a[k]。则S[i,j]的最优解就是S[i,k]的最优解加上S[k,j]的最优解捎带一个a[k]的并集。证明子问题的最优解能构造原问题的方法就是剪贴法，不多说了。
    	这样状态转移方程就有了，设C[i,j]是S[i,j]的最优解，即是S[i,j]中最大兼容活动数。当S[i,j]=∅(i>=j)，此时C[i,j]=0。则状态转移方程就是C[i,j]=C[i,k]+C[k,j]+1
    	虽然有了状态转移方程，但是对于每一个子问题都有k个选择，k=j-i-1(j-i+1-2),k=i+1....j-1。所以状态方程变了
    
    	状态转移方程有了，这样很容易写出代码来，自底向上。

可是我们发现一个问题，那就是对于任何一个k将S[i,j]划分成两个子问题。可是如果有一个子问题是空的，那不是减少了我们的工作量吗？
    定理:对于任何非空S[i,j]，设a[m]是S[i,j]中最早结束的一个活动，f[m]=min{f[k]:a[k]∈S[i,j]}，则
          1 活动a[m]被包含在S[i,j]的一个（可能有多个）最大兼容活动的子集中；
          2 子问题S[i,m]是空集，a[m]使S[m,j]成为仅有的非空子问题。
     	简要证明一下：对于1，假设a[k]是S[i,j]最优解C[i,j]的第一个活动（排序之后），如果a[m]=a[k],结论得证.如果a[m],a[k]不相等，那么就用a[m]替换a[k]（因为a[m]是最早结束的活动，替换之后肯定和其他的兼容），原问题的最大兼容活动数目没变，结论得证。对于2，很简单，一看就明白了。
    	这个定理给我们带来了什么好处呢？好处就是两个子问题其中一个为空了，减少工作量了。还有就是最早结束的活动肯定就是当前子问题的最优活动！在之前的DP，我们每次要做j-i-1次选择，而现在我们只需要选择当前最早结束的活动即可。而且你选择了a[m]，那么剩余问题的最优解就是S[m,j]的最优解。
    	这样状态转移方程就是C[i,j]=C[m,j]+1(a[m]是S[i,j]中最早结束的活动，而且a[m]与最优解中之前的活动是兼容的，因为最早结束的 活动是当前子问题的一个最优活动，但是如果跟之前的已经找到的最优活动不兼容的话就没什么意义了吧)。这样还有一个好处就是代码不用在自底向上了，直接采用自顶向下来做就好了。我们找到了a[m]，直接找S[m,j]的最优解就好了。
    	这就是贪心算法，每次都选择当前最好的选择。对于原问题来说，a[1]肯定是原问题S[0，n+1]最优解的第一个，而a[2]就不一定是S[1,n+1]的最优解的一个，因为a[2]不一定与a[1]兼容。意思就是已经选定是最优活动，那么之后选择的最优要和之前选定的活动兼容。这样每次选择的活动都是和之前兼容，那所有的活动也就是只是考虑一次而已。

伪代码，每次选择的a[m]都要和a[i]兼容,而且是第一个和a[i]兼容的。

求解过程图解

递归解法很容易变成迭代算法，尤其是这种尾递归（几乎是）。

时间复杂度都是O(n)。
    	说完了这些，我们来总结一些贪心算法的特点以及解题步骤。
    	贪心算法是通过一系列的选择来给出某一问题的最优解的。对于算法中的每一个决策选择都是做一个当时看起来最佳的选择，这种方法使我们常常能够得到最优解，但不是绝对的。DP才是绝对的。有人说每一个贪心算法的背后都有一个DP，这话一点没错。能用贪心解决的问题都可以用DP来解决。但是有些问题用贪心来解决更方便，更简单。
    根据刚才的例子，我们可以总结出一些步骤，步骤都是灵活运用的，不是死的。
        1 决定问题的最优子结构
        2 设计出一个递归解。
        3 证明在递归的任一阶段，最优选择之一总是贪心选择，So贪心选择是安全的。
        4 证明通过贪心选择，所有子问题都是空（除了一个）
        5设计出一个实现贪心策略的递归算法。
        6 将递归算法转换成迭代算法。
    简化步骤
        1 将优化问题转化成一个先做出选择，再解决剩下的一个子问题。
        2 证明原问题总是有一个最优解是贪心选择得到的，从而说明贪心选择的安全。
        3 说明在做出贪心选择之后，剩余的子问题具有这样一个性质。即如果将子问题的最优解和贪心选择结合起来，总是会得到原问题的一个最优解。
    贪心算法的性质：
           1 最优子结构
    	    对一个问题来说，如果他的最优解包含子问题的最优解，那该问题就就具有最优子结构性质。对于最优子结构的选择贪心和DP是不太一样的，贪心更加侧重于贪心选择和子问题的结合来得到全局最优解。
           2 贪心选择性质
    	    一个全局最优解可以通过局部最优（贪心）选择来得到。也就是说我们做选择的时候是考虑当前问题的最佳选择，而不考虑子问题的结果。

DP和贪心的区别就是做选择的时候贪心所做出的选择是当前最佳，要依赖已经做出的所有贪心选择，而不依赖有待于做出选择的子问题的解。而DP具有无后效性，未来与过去无关，当前的状态是此前历史的一个完整总结，不会依赖已经得到子问题的解，只是和以后的子问题有关系，这点和贪心刚好相反。DP是通过小问题来得到大问题的解，而贪心是一次一次做出贪心选择，然后不断将给定的问题规约为更小的子问题。DP要自底向上，贪心可以自顶向下的解决问题。DP还具有重叠子问题的性质，这点是贪心不具备的。贪心只要满足这两点就可以来做，当然需要证明局部最优解是全局最优解。
     
     	贪心算法的宗旨就是一个字----贪！一定要贪心，否则得不出最优解。
     	贪心算法有很多的应用，比如哈夫曼编码，最小生成树，单源最短路径等，以后会陆续更新的。 
     
     
     
     
     
     
     
     	 出处http://blog.csdn.net/liangbopirates/article/details/10044463