By Zhang, Cheng

更新日期:

文章目录
  1. 1. 算法（9） 近似算法1--贪心算法
    1. 1.1. 顶点覆盖
    2. 1.2. 基数顶点覆盖
      1. 1.2.1. 紧例子(Tight Example)
    3. 1.3. 集合覆盖
      1. 1.3.1. 基数集合覆盖
      2. 1.3.2. 性能（Performance Ratio）
      3. 1.3.3. 贪心算法
      4. 1.3.4. 紧例子

算法（9） 近似算法1--贪心算法

顶点覆盖

给定一个无向图G(V,E)，对每个点都赋一个权值函数。我们要找到这个花费最小的顶点覆盖(Vertex Cover)，顶点覆盖的意思就是每一条边的至少一个顶点要在集合覆盖中。当花费函数是1的时候，顶点覆盖叫做基数顶点覆盖(Cardinality Vertex Cover)。

一个NP优化问题π既可以是最小值问题也可以是最大值问题。对于π的每一个有效的实例I都有一个非空可行解集，其中的每一个解都可以被赋值一个非负有理数，这个有理数叫做目标函数值。

存在多项式时间的算法来决定解的有效性(Validity)、可行性(feasibility)和目标函数值。

一个能够得到最优目标函数值的可行解被称为最优解。 OPTπ(I)表示在实例I下最优解的目标函数值，在之后的讲解中我们直接用OPT来代替它。计算一个OPT是HP难的。

所有已知的解决NP-难问题算法都有指数型运行时间。但是，如果我们要找一个“好”解而非最优解，有时候多项式算法是存在的。

基数顶点覆盖

为了把问题变得简单我们先研究顶点的花费函数为1的情况，也就是研究基数顶点覆盖。这里我们先要引入一个叫做Matching的问题。

给定图G(V,E)，存在这样一个边的子集M，如果在M中没有两条边是共享一个顶点的，那么我们称M为Matching。下面有两个概念，一个叫做最大Matching，还有个叫极大Matching。最大Matching当然是指符和Matching的条件下可以包含边数的最大值，而极大Matching是指当前情况下不能在包含边的最大值，极大Matching每次都可以不一样，很可能得到的Matching不是这个图的最大Matching。

求解最大Matching我们的算法就需要比较细致来求解，而极大Matching我们可以用更加简单的算法来做到，就是随便取符合条件的边即可。

我们求Matching问题的目的就是为了求基数顶点覆盖的近似算法。那么这个近似算法是什么呢？求出刚刚的极大Matching，接着将Matching中每边的两个顶点输出出来即可。这就是我们的近似算法，这个近似算法的近似因子是2。也就是我们用这个方法得到的结果f <= 2OPT，其中OPT是求解基数顶点覆盖的最优解。听上去很简单，关键是我们怎么证明这个是等价的。

证明：

1
2
3
4
5
6
7
8
|M|表示Matching集合中的边的个数。
f表示我们求解基数顶点覆盖的解。（显然不一定是最优的）
OPT表示基数顶点覆盖的最优解。
在Matching问题和基数顶点覆盖问题之间存在一个固有的关系
|M|<=OPT //固有关系
理由是可以至少取Matching中的边的一个点出来，构造一个顶点集合，而这些顶点集合正好符合“边的一点在集合中”的条件。当然也可以把Matching中边的两点都取出来
那么我们是如何求解的呢？就是将Matching中每边的两点作为我们的解。
所以得到f = 2|M| <= 2OPT，2就是这个近似算法的近似因子。

根据上面的例子我们可以得到求解一个问题的近似算法的核心就是要找一个固有的性质来得到一个M <= kOPT的式子，其中k就是近似因子。接着找出我们的解和这个M的关系，这样就能得到近似算法了。

紧例子(Tight Example)

那么我们这个近似因子，也称为保证因子(guaranteed factor)能不能有更好的值呢？

我们先考虑一族无穷的例子(为什么不考虑单例呢？因为单独的特殊例子，我们可以在算法开始时用多项式的时间来构造出这个例子，接着排除它。)，完全二分图Kn,n。

对这个Kn,n跑我们的近似算法，我们会选出连接两边不相交的n条边，这样共有2n个顶点，恰好是基数顶点覆盖的最优解。有了这样的紧例子，我们就可以认为近似因子是当前最小的。

集合覆盖

在近似算法中集合覆盖问题扮演者和最大匹配一样的角色。集合覆盖的概念就是给定一个有n个元素的全集U，全集U的一组子集S={S1,…,Sk}，每组子集上都有个花费函数c。我们要找到最小花费的能够覆盖所有元素的集合。在特殊情况下，这个花费函数就是1，那么我们称这样的问题就是基数集合覆盖。

定义这些元素在集合中出现的频率为f，相当多的集合覆盖的近似算法都是要达到两个保证因子O(logn)或者f。当这个f取2的时候，集合覆盖问题就转化为顶点覆盖的问题了。

基数集合覆盖

有一个村落由多个村庄组成，村落里打算建几所学校。建学校得符合下面两个限制条件： 1. 每个学校必须得在村庄里; 2. 学校与学校之间的距离不得超过30英里。那么问题是符合上面两个条件的学校最少需要几所？

下面的图(a)表示a到k个村庄，图(b)就是将距离在30英里内的村庄连接起来。

这是一个典型的基数集合覆盖问题：

  • 对于每个村庄x，令Sx为与x距离为30英里的村庄集合。
  • 在村庄x上的学校将覆盖这些相连的村庄
  • 那么这个问题就会转化为求有多少个集合Sx需要被选出来覆盖所有村落里的村庄。

再规范的定义下问题就是：

1
2
3
4
Set Cover
Input: 一组元素集合B，S1,S2,...,Sm为B的子集
Output:子集Si的全集是B
Cost:被选中的子集个数

老师接下来的几张ppt的前后关系我没有太搞清楚，为什么会先把性能介绍了。

性能（Performance Ratio）

这里有个结论就是假设全集B包含n个元素，最优覆盖包含k个子集合。那么我们使用的贪心算法最多会选择k*ln n个子集。

证明：

  1. 设nt表示在t次迭代贪心算法后仍然没有被覆盖的元素个数。
  2. 因为剩下元素会被最优k个子集覆盖，那么这些剩余的子集中一定有某个子集中有nt/k个元素（抽屉原则）。
  3. 所以使用贪心算法后，我们可以得到n(t+1) <= nt-nt/k = nt(1-1/k)，可以递推得到nt <= n0(1-1/k)^t。
  4. 存在这样一个式子 1-x <= e^(-x)对所有的x都成立
  5. nt <= n0(1-1/k)^t < n0(e^(-1/k))^t = ne^(-t/k)

当t=kln n，这个结果会等于1，也就是说没有其他的元素剩下了。

贪心算法

我们的贪心算法的策略是每次迭代选取一个“性价比”最高的子集，并将被覆盖的元素移走，直到所有的元素都被覆盖。

设C为在一个迭代开始前已经被覆盖的元素的集合。那么在一次迭代中，我们定义一个子集S的性价比是覆盖新元素的平均花费，这个子集S的花费之和除以剩下没有被覆盖的元素，即cost(S)/|S-C|。

接着我们定义一个元素的price为它被覆盖的平均花费。那么这个贪心算法就是：

令e1,…en表示全集U中的元素，现在我们需要证明对每个元素，它们的花费price(ek) <= OPT/(n-k+1)。

证明：

  1. 在每次迭代中，剩下的子集合的最优策略就是以OPT的代价来覆盖剩下的元素。那么对于这些剩下的子集合，他们的性价比最多是OPT/|S-C|，即price(ek) <= OPT/|S-C|。
  2. 在迭代中，如果ek被覆盖了，那么S-C包含n-k+1个元素。所以price(ek) <= OPT/|S-C| <= OPT/(n-k+1)

紧例子

文章目录
  1. 1. 算法（9） 近似算法1--贪心算法
    1. 1.1. 顶点覆盖
    2. 1.2. 基数顶点覆盖
      1. 1.2.1. 紧例子(Tight Example)
    3. 1.3. 集合覆盖
      1. 1.3.1. 基数集合覆盖
      2. 1.3.2. 性能（Performance Ratio）
      3. 1.3.3. 贪心算法
      4. 1.3.4. 紧例子