贪心算法

一、概念

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对一些问题它能产生整体最优解或者是整体最优解的近似解。

贪心算法没有固定的算法框架，算法设计的关键是贪婪策略的选择。一定要注意，选择的贪婪策略要具有无后向性，即某阶段状态一旦确定以后，不受这个状态以后的策略影响，也就是说某个状态以后的过程不会影响以前的状态，只与当前状态有关，也称为这种特性为无后效性。因此，适应用贪婪策略解决的问题类型较少，对所采用的贪婪策略一定要仔细分析其是否满足无后效性。

 

二、贪心算法的基本要素

1、贪心选择性质

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 

对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。

2、最优子结构性质

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 

3、贪心算法与动态规划算法的差异

贪心算法和动态规划算法都要求问题具有最优子结构性质，这是2类算法的一个共同点。但是，对于具有最优子结构的问题应该选用贪心算法还是动态规划算法求解?是否能用动态规划算法求解的问题也能用贪心算法求解?下面研究2个经典的组合优化问题，并以此说明贪心算法与动态规划算法的主要差别。

 

 

三、贪心算法的基本思路：

从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。

该算法存在问题：

1. 不能保证求得的最后解是最佳的；

2. 不能用来求最大或最小解问题；

3. 只能求满足某些约束条件的可行解的范围。

实现该算法的过程：

从问题的某一初始解出发；

while 能朝给定总目标前进一步 do

　　  求出可行解的一个解元素；

由所有解元素组合成问题的一个可行解；

 

用背包问题来介绍贪心算法：

背包问题：有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。

物品 A  B  C D E F G

重量 35  30  60  50  40  10  25  

价值  10  40  30 50  35  40  30

 

分析如下

目标函数： ∑pi最大

约束条件是装入的物品总重量不超过背包容量：∑wi<=M( M=150)。

（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？

（2）每次挑选所占重量最小的物品装入是否能得到最优解？

（3）每次选取单位重量价值最大的物品，成为解本题的策略。

值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。

贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。

可惜的是，它需要证明后才能真正运用到题目的算法中。

一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。

对于背包问题中的3种贪心策略，都是无法成立（无法被证明）的，解释如下：

贪心策略：选取价值最大者。反例：

W=30

物品：A  B  C

重量：28 12 12

价值：30 20 20

根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。

（2）贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。

（3）贪心策略：选取单位重量价值最大的物品。反例：

W=30

物品：A  B  C

重量：28 20 10

价值：28 20 10

根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。

所以需要说明的是，贪心算法可以与随机化算法一起使用，具体的例子就不再多举了。（因为这一类算法普及性不高，而且技术含量是非常高的，需要通过一些反例确定随机的对象是什么，随机程度如何，但也是不能保证完全正确，只能是极大的几率正确）。

 

四、几种常见的贪心算法

有人说贪心算法是最简单的算法，原因很简单：你我其实都很贪，根本不用学。有人说贪心算法是最复杂的算法，原因也很简单：这世上贪的人太多了，那轮到你我的份？

 

1.线段覆盖（lines cover）

 题目大意：

   在一维空间中告诉你N条线段的起始坐标与终止坐标，要求求出这些线段一共覆盖了多大的长度。

 

解题思路：

   将线段按其坐标进行排序（排序的具体方法:按起始坐标排，起始坐标相同的按终止坐标排，都是小在前大在后）,使之依次递增，并按顺序分别编号为X(i),X(i).a代表其起始坐标，X(i).b代表其终止坐标。

然后按排好的顺序依次处理：定义一个变量last记录考虑到当前线段之时被线段覆盖的最大的坐标值，再定义一个变量length记录当前线段覆盖的长度。对于后面的线段，我们把它看成由两个部分组成，即把它分成last之前的线段和last之后的线段。（如果线段全部处在last之后，其last之前的部分不存在。）由于我们排过序，我们可以肯定当前考虑的线段X(i)其处在last之前的部分不会对length造成影响（因为X(i-1).b=last，X(i).a>=X(i-1).a,即X(i)在last之前的部分所处位置肯定被线段X(i-1)覆盖过），所以会对length产生影响的即是X(i)处在last之后的部分。

所以我们可以依次对每条线段做如下处理：（初始化length为零，last为负无穷）

length+=X(i).b-last      (X(i).a<=last 且 X(i).b>=last)

length+=X(i).b-X(i).a    (X(i).a>last)

last=X(i).b;

最后length就为我们所需要的答案。

 

2.最优数对（best pair）

题目大意：

按递增的顺序告诉你N个正整数和一个实数P，要求求出求出该数列中的比例最接近P的两个数（保证绝对没有两个数使得其比值为P）。

 

 

  解题思路：

 定义两个指针i和j，先初始化i=j=1，然后进行如下操作：

       当code[j]/code[i]>p时，inc（j）；

       当code[j]/code[i]<p时，inc（i）。

       记录其中产生的最优值即为答案。

 

3.连续数之和最大值（max sum）

  题目大意：

给出一个长度为N的数列（数列中至少有一个正数），要求求出其中的连续数之和的最大值。（也可以加入a和b来限制连续数的长度不小于a且不大于b）。

解题思路：

先说不加限制的那种，定义一个统计变量tot，然后用循环进行如下操作：inc（tot，item）其中如果出现tot<0的情况，则将tot赋值为0。在循环过程之中tot出现的最大值即为答案。

如果加入了限制条件的话，问题就变得难一些了（这句真的不是废话）。为此我们先定义数组sum[i]来表示code[1]到code[i]之和（这样的话code[a]~code[b]的和我们就可以用sum[b]-sum[a-1]来表示了）。

  再维护一个数组hash[i]来表示满足条件的sum[a-1]的下标，并使之按递增顺序排列，这样当前以第i的数为终止的数列的最大值肯定就是sum[i]-sum[hash[1]]。

 

现在我们来讨论hash数组之中的数据需要满足的条件和如何维护的具体问题：

当考虑到以第i个数为结尾时，hash[i]所表示的下标需要满足的第一个条件就是题目规定的长度限制，我们需要实时的加入满足长度规定的下标，删除不符合要求的下标。其次，与不加限制条件时相同，若sum[i]-sum[hash[1]]的值小于零，则清空数组hash。

维护时可以这样，当考虑到第i个数时，我们就将下标i-a+1加入到hash中，因为hash中原来已经排好序，因此我们我们可以用插入排序来维护hash的递增性，然后我们考察hash[1]，若hash[1]<i-b+1，则证明其已超出长度限制，我们就将其删除，接着再考虑更新后的hash[1],如此重复直至找到一个满足条件的hash[1]为止。

我们可以用链表来表示hash，这样就可以减少数据加入和删除时频繁数据移动的时间消耗。

记录下sum[i]-sum[hash[1]]的最大值即为答案。

 

动态规划和贪心算法相同与不同：

相同点：

动态规划和贪心算法都是一种递推算法；

均有局部最优解来推导全局最优解；

 

不同点：

贪心算法：

 1.贪心算法中，作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留。

 2.由（1）中的介绍，可以知道贪心法正确的条件是：每一步的最优解一定包含上一步的最优解。

动态规划算法：

1.全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解。

2.动态规划的关键是状态转移方程，即如何由以求出的局部最优解来推导全局最优。

3.边界条件：即最简单的，可以直接得出的局部最优解。

 

贪心算法的理论基础：

借助于拟阵工具，可建立关于贪心算法的较一般的理论。这个理论对确定何时使用贪心算法可以得到问题的整体最优解十分有用。

1. 拟阵

    拟阵M定义为满足下面3个条件的有序对(S,I)：

    (1)S是非空有限集。

    (2)I是S的一类具有遗传性质的独立子集族，即若BÎI，则B是S的独立子集，且B的任意子集也都是S的独立子集。空集Æ必为I的成员。

    (3)I满足交换性质，即若AÎI,BÎI且|A|<|B|，则存在某一元素xÎB-A，使得A∪{x}ÎI。

例如，设S是一给定矩阵中行向量的集合，I是S的线性独立子集族，则由线性空间理论容易证明(S,I)是一拟阵。拟阵的另一个例子是无向图G=(V,E)的图拟阵。

给定拟阵M=(S,I)，对于I中的独立子集AΠI，若S有一元素xΠA，使得将x加入A后仍保持独立性，即A∪{x} Î I,则称x为A的可扩展元素。

当拟阵M中的独立子集A没有可扩展元素时，称A为极大独立子集。

下面的关于极大独立子集的性质是很有用的。

定理1：拟阵M中所有极大独立子集大小相同。

    这个定理可以用反证法证明。

    若对拟阵M=(S,I)中的S指定权函数W，使得对于任意xÎS，有W(x)>0，则称拟阵M为带权拟阵。依此权函数，S的任一子集A的权定义为               。

 

 2. 关于带权拟阵的贪心算法

许多可以用贪心算法求解的问题可以表示为求带权拟阵的最大权独立子集问题。

给定带权拟阵M=(S,I)，确定S的独立子集AÎI使得W(A)达到最大。这种使W(A)最大的独立子集A称为拟阵M的最优子集。由于S中任一元素x的权W(x)是正的，因此，最优子集也一定是极大独立子集。

例如，在最小生成树问题可以表示为确定带权拟阵   的最优子集问题。求带权拟阵的最优子集A的算法可用于解最小生成树问题。

下面给出求带权拟阵最优子集的贪心算法。该算法以具有正权函数W的带权拟阵M=(S,I)作为输入，经计算后输出M的最优子集A。

Set greedy (M,W)

{A=Æ;

   将S中元素依权值W（大者优先）组成优先队列；

   while (S!=Æ) {

     S.removeMax(x);

     if (A∪{x}I) A=A∪{x};

     }

   return A；

}

算法greedy的计算时间复杂性为                 。

引理1 (拟阵的贪心选择性质)

设M=(S,I)是具有权函数W的带权拟阵，且S中元素依权值从大到小排列。又设xÎS是S中第一个使得{x}是独立子集的元素，则存在S的最优子集A使得xΠA。

算法greedy在以贪心选择构造最优子集A时，首次选入集合A中的元素x是单元素独立集中具有最大权的元素。此时可能已经舍弃了S中部分元素。可以证明这些被舍弃的元素不可能用于构造最优子集。