【算法分析与设计】贪心算法（上）_用数学归纳法对算法正确性做出证明活动安排的问题提出是,设在活动安排中,每个活动

---

一、学习要点

  理解贪心算法的概念。
  掌握贪心算法的基本要素
  （1）最优子结构性质
  （2）贪心选择性质
  理解贪心算法与动态规划算法的差异
  理解贪心算法的一般理论
  通过应用范例学习贪心设计策略。
  （1）活动安排问题；
  （2）最优装载问题；
  （3）哈夫曼编码；
  （4）单源最短路径；
  （5）最小生成树；
  （6）多机调度问题。

---

二、找硬币问题

  有四种硬币，二角五分、一角、五分和一分，求找六角三分钱时，使用硬币最少的方法。
  自然会想到2个二角五分，1个一角和3个一分，总是在当前条件下使用硬币最少的那个选择，结果一般就是最优方法。
  有三种硬币，一角一分、五分和一分，求找一角五分时，使用硬币最少的方法。

---

2.1 概述

  顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说 贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路径问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。

---

三、活动安排问题

  活动安排问题就是要 在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。

  设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而 在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si <fi 。如果选择了活动i，则它在半开时间区间[si, fi)内占用资源。若区间[si, fi)与区间[sj, fj)不相交，则称活动i与活动j是相容的。也就是说，当sj≥fi时，活动i与活动j相容。

  例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：

---

3.1 策略选择

  策略一：开始时间早的优先；证明这种方法不可行
  策略二：占用时间少的优先；举出反例，推翻此策略
  策略三：结束时间早的优先；使用贪心算法，可以得到最优解！

  由于 输入的活动以其完成时间的非减序排列，所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。
  算法greedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。

  算法greedySelector 的计算过程如左图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。

---

3.2 活动安排问题程序代码

template<class Type>
void GreedySelector(int n, Type s[], Type f[], bool A[])
{
       A[1]=true;
       int j=1;
       for (int i=2;i<=n;i++) {
          if (s[i]>=f[j]) { A[i]=true; j=i; }
          else A[i]=false;
          }
}
1
2
3
4
5
6
7
8
9
10

  各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非减序排列。

  若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fi，则不选择活动i，否则选择活动i加入集合A中。
  贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法却总能求得整体最优解，即它最终所确定的相容活动集合A的规模最大。
  贪心算法是否正确，能否得到最优解，必须进行证明！

---

3.3 一般使用数学归纳法进行证明

  例：证明对于任何自然数n，
  1+2+…+n=n(n+1)/2
  证：n=1时，左=1，右=1(1+1)/2=1
  假设对任何自然数n等式成立，则
  1+2+…+n+(n+1)=n(n+1)/2+(n+1)
  =(n+1)(n/2+1)
  =(n+1)2(n/2+1)/2
  =(n+1)(n+2)/2

---

3.4 活动选择算法的命题

  算法执行到第k步，选择k项活动，i1=1,i2,…ik；则存在最优解A包含活动i1=1,i2,…ik
  根据上述命题，对于任何k，算法前k步的组合都将导致最优解，最多到第n步，将得到问题实例的最优解。

---

3.4.1 先看k=1时是否正确

  证明存在最优解包含活动1
  任取最优解A，A中活动按截止时间递增排序，如果A中第一个活动为j≠1，用1替换A中的活动j得到A’，即A’=(A-{j})∪{1}，
  由于f1<=fj， A’也是最优解，且含有1。

---

3.4.2 归纳步骤，k->k+1

  算法执行到第k步，选择了活动i1=1,i2,…ik
  根据归纳假设存在最优解A包含i1=1,i2,…ik
  A中剩下的活动选自集合S’
  S’={i|i∈Si>=fk}
  A={i1,i2,…ik}∪B

---

3.4.3 归纳步骤（续）

  B是S’的最优解（若不然，S’的最优解为B*， B的活动比B多，那么B∪{1,i2,…ik}是S的最优解，且比A的活动多，与A的最优性相矛盾）
  将S’看成子问题，根据归纳基础，存在S’中的最优解B’，有S’中的第一个活动ik+1，且| B’ |=| B|，于是{i1,i2,…ik}∪B’={i1,i2,…ik,ik+1}∪(B’-{ik+1})也是原问题的最优解

---

四、贪心算法的基本要素

  本节着重讨论 可以用贪心算法求解的问题的一般特征。
  对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。
  但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质：贪心选择性质和最优子结构性质。

---

4.1 贪心选择性质

  所谓贪心选择性质是指 所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
  动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。
  对于一个具体问题，要确定它是否具有贪心选择性质，必须证明 每一步所作的贪心选择最终导致问题的整体最优解。

---

4.2 最优子结构性质

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

---

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

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

---

4.4 0-1背包问题（动态规划）

  给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
  在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。

---

4.5 背包问题（贪心选择）

  与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。
  这2类问题都具有最优子结构性质，极为相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。

---

4.6 用贪心算法解背包问题的基本步骤

  首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则 选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。

void Knapsack(int n,float M,float v[],float w[],float x[])
{
       Sort(n,v,w);
       int i;
       for (i=1;i<=n;i++) x[i]=0;
       float c=M;
       for (i=1;i<=n;i++) {
          if (w[i]>c) break;
          x[i]=1;
          c-=w[i];
          }
       if (i<=n) x[i]=c/w[i];
}
1
2
3
4
5
6
7
8
9
10
11
12
13

  算法knapsack的 主要计算时间 在于将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为
O（nlogn）。
  为了证明算法的正确性，还必须证明背包问题具有贪心选择性质。

  对于0-1背包问题，贪心选择之所以不能得到最优解是因为 在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多 互相重叠的子问题 。这正是该问题可用动态规划算法求解的另一重要特征。
  实际上也是如此，动态规划算法的确可以有效地解0-1背包问题。

---

五、最优装载问题

  有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。

---

5.1 算法描述

  最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。
  数学建模（略）。

template<class Type>
void Loading(int x[],  Type w[], Type c, int n)
{
        int *t = new int [n+1];
        Sort(w, t, n);
        for (int i = 1; i <= n; i++) x[i] = 0;
        for (int i = 1; i <= n && w[t[i]] <= c; i++) {
	x[t[i]] = 1; 
	c -= w[t[i]];
	}
}
1
2
3
4
5
6
7
8
9
10
11

  该问题是 0-1背包问题的子问题，集装箱相当于物品，物品重量是wi，价值vi都等于1，轮船载重量限制C相当于背包装量限制b
  0-1背包问题目前没有多项式时间的算法，但这个特殊的子问题可以！

---

5.2 贪心选择性质

  可以证明最优装载问题具有贪心选择性质。

---

5.3 最优子结构性质

  最优装载问题具有最优子结构性质。
  由 最优装载问题的贪心选择性质 和 最优子结构性质，容易证明算法的正确性。
  算法的主要计算量在于将集装箱依其重量从小到大排序，故算法所需的计算时间为 O(nlogn)。

---

5.4 最优装载问题正确性证明思路

  命题：对装载问题任何规模为n的输入实例，算法得到最优解。设集装箱从轻到重记为1,2,…n
  归纳基础：证明对任何只含一个箱子的输入实例，贪心法得到最优解（显然）。
  归纳步骤：假设对任何n个箱子的输入实例，贪心法得到最优解，那么n+1个箱子的输入实例，贪心法也得到最优解！

---

5.5 正确性证明

  假设对n个集装箱的输入，贪心法都可以得到最优解。N={1,2,…n,n+1}其中w1<=w2<=…<=wn<=wn+1，由归纳假设，对于N’={2,3,…n,n+1}，C’=C-w1，贪心法得到最优解I’，令I=I’∪{1}，要证明I是原问题N={1,2,…n,n+1}的最优解。
  若不然，存在包含1的关于N的最优解I*（如果I* 中没有1，用1替换I* 中的第一个元素得到的解也是最优解），且|I*|>|I|，那么I*-{1}是N’和C’的解且|I* -{1} |>|I -{1} |=|I’|,与I’是关于N’和C’的最优解相矛盾，所以I*不是N的最优解， N的最优解只能是那个I。

---

六、哈夫曼编码

  哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%～90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。
  给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。

---

6.1 前缀码

  对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其它字符代码的前缀。这种编码称为前缀码。
  非前缀码的例子 a:001,b:00,c:010,d:01。
  解码1:01,00,001 d,b,a。
  解码2：010，00,01 c,b,d。

  前缀码的二叉树表示：
  前缀码：{00000,00001,0001,001,01,100,101,11}
  频率：{5%,5%,10%,15%,25%,10%,10%,20%}
  构造树：
  0-左子树
  1-右子树
  码对应一片树叶
  最大位数为树深

  编码的前缀性质可以使译码方法非常简单。
  表示最优前缀码的二叉树总是一棵完全二叉树，即树中任一结点都有2个儿子结点。
  平均码长 定义为：

  使平均码长达到最小的前缀码编码方案称为给定编码字符集C的最优前缀码。

---

6.2 构造哈夫曼编码

  哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。
  哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。
  算法以|C|个叶结点开始，执行|C|－1次的“合并”运算后产生最终所要求的树T。

  实例：
  输入：a:45,b:13,c:12,d:16,e:9,f:5
  由此构造哈夫曼树，并求每个字符的编码
  a:1
  b:011
  c:010
  d:001
  e:0001
  f:0000

  在书上给出的算法huffmanTree中，编码字符集中每一字符c的频率是f©。以f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。一旦2棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的2棵树的频率之和，并将新树插入优先队列Q。经过n－1次的合并后，优先队列中只剩下一棵树，即所要求的树T。
  算法huffmanTree用最小堆实现优先队列Q。初始化优先队列需要O(n)计算时间，由于最小堆的removeMin和put运算均需O(logn)时间，n－1次的合并总共需要O(nlogn)计算时间。因此，关于n个字符的哈夫曼算法的计算时间为O(nlogn) 。

---

6.3 哈夫曼算法的正确性

  要证明哈夫曼算法的正确性，只要证明最优前缀码问题具有贪心选择性质和最优子结构性质。
  (1)贪心选择性质
  (2)最优子结构性质

---

6.4 最优前缀码性质（引理1）

  引理1：C是字符集，∨c∈C,f©为频率，x,y ∈C,f(x),f(y)频率最小，那么存在最优前缀码使得x,y码字等长且仅在最后一位不同

---

6.5 最优前缀码性质（引理2）

  引理2：设T是前缀码的二叉树，∨x,y ∈T，x,y是树叶兄弟，z是x,y的父亲，令T’=T-{x,y}且令z的频率f(z)=f(x)+f(y)，T是对应前缀码C’=(C-{x,y})∪{z}的二叉树，那么B（T）=B（T’）+f(x)+f(y)

---

6.6 算法正确性证明思路

  定理：哈夫曼算法对任意规模为n（>=2）的字符集C都得到关于C的最优前缀码的二叉树。
  归纳基础 证明：对于n=2的字符集，哈夫曼算法得到最优前缀码。
  归纳步骤 证明：假设哈夫曼算法对于规模为k的字符集都得到最优前缀码，那么对于规模为k+1的字符集也得到最优前缀码。

---

6.7 归纳基础

  n=2，字符集C={x1,x2}，
  对任何代码的字符至少都需要1位二进制数字。哈夫曼算法得到的代码是1和0，是最优前缀码。
  假设哈夫曼算法对于规模为k的字符集都得到最优前缀码，考虑规模为k+1的字符集C={x1,x2,…xk+1}，其中x1,x2 ∈ C是频率最小的两个字符。令C’=(C-{x,y})∪{z}，f(z)=f(x)+f(y)。
  根据归纳假设，算法得到一颗关于字符集C’,频率f(z)和f(xi)(i=3,4,…,k+1)的最优前缀码的二叉树T’。
  把x1,x2作为z的儿子附到T’上，得到树T，那么T是关于C=（C’-{z}）∪{x1,x2}的最优前缀码的二叉树。
  如若不然，存在更优树T*，B（T*）<B（T），且由引理1，其树叶兄弟是x1,x2。
  去掉T* 中x1,x2，得到T*’，根据引理2 ，B（T*’）= B（T*）-（f(x1)+f(x2)）<B（T）-（f(x1)+f(x2)）=B（T’）。
  与T’是一颗关于C’的最优前缀码二叉树矛盾。

---

6.8 应用：文件归并

  问题：给定一组不同长度的排好序文件构成的集合S={f1,f2,…fn}，其中fi表示第i个文件含有的项数。使用二分归并将这些文件归并成一个有序文件。
  归并过程对应于二叉树：文件为树叶。fi与fj归并的文件是它们的父节点。

---

6.9 两两顺序归并

  实例：S={21,10,32,41,18,70}
  归并代价：最坏情况下的工作量
  （1）全部计算=483。
  （2）（21+10+32+41）*3+(18+70)*2-5=483。
  （3）哈夫曼归并=456。