Lec 11: Approximation⚓︎

Introduction⚓︎

设计算法的时候需要考虑以下几方面的问题：

• Optimality: 算法能找到确切的最优解
• Efficiency: 算法能高效（通常是多项式时间）运行
• All instances: 算法是通用的，能够解决全部问题

我们对这几个方面进行组合，可以得到不同的算法类型：

• A+C：针对全部实例的精确算法
• A+B：对于特殊情况的精确且快速的算法
• B+C：近似算法

即使 \(P = NP\)，我们仍然无法保证存在 A+B+C 的算法解决此类问题。

本讲我们延续 P/NP 问题的话题，探讨如何解决此类问题。对于 NPC 问题，虽然无法在多项式时间内得到最优解，但是我们希望：

• 如果数据规模 \(N\) 很小，即使时间复杂度为指数级也是可以接受的
• 如果某些特殊情况能够在多项式时间内完成，那就先处理这些情况
• 设计一种算法，保证能够在多项式时间内得到接近最优解——这一类算法便是接下来要介绍的近似算法(approximation algorithm)

我们一般通过近似比(approximation ratio)\(\rho(n)\) 来衡量近似算法的好坏，称这样的近似算法为\(\rho(n)\)- 近似算法。它的意义是：对于任意规模为 \(n\) 的输入，算法得到一个解所花的成本 \(C\) 不会超过得到最优解所花成本 \(C^*\) 的 \(\rho(n)\) 倍，即：

最优解的近似方案(approximation scheme)：一种近似算法，满足对于给定的输入实例，\(\forall \varepsilon > 0\)，它是一个 \((1 + \varepsilon)\) 近似算法。下面给出几种常见的近似方案：

• 多项式时间近似方案(polynomial-time approximation scheme, PTAS)：对于任意给定值 \(\varepsilon > 0\)，当输入实例规模为 \(n\) 时，该方案能在多项式时间内完成计算，时间复杂度可记为 \(O(n^{f(\frac{1}{\varepsilon})})\)
  • 高效多项式时间近似方案(efficient polynomial-time approximation scheme, EPTAS)：在 PTAS 的基础上，要求该方案的运行时间是与 \(\varepsilon\) 无关，关于 \(n\) 的多项式时间，即时间复杂度为 \(O(n^{O(1)} f(\frac{1}{\varepsilon}))\)
  • 满多项式时间近似方案(fully polynomial-time approximation scheme, FPTAS)：在 PTAS 的基础上，要求该方案的运行时间关于 \(n\) 和 \(\varepsilon\) 都是多项式级的，时间复杂度可记为 \(O(n^{O(1)} (\dfrac{1}{\varepsilon})^{O(1)})\)

Examples⚓︎

Bin Packing⚓︎

问题描述

给定 \(N\) 个大小分别为 \(S_1, S_2, \dots, S_N\) 的物品，满足 \(\forall\ 1 \le i \le N, 0 < S_i \le 1\)，并假设有若干个容量为 1 的桶。现在请你求出能够装下所有物品的最小桶数。

例子

题目答案

\(N = 7; S_i = 0.2, 0.5, 0.4, 0.7, 0.1, 0.3, 0.8\)

最优解为：

然而，这个看似简单的问题实际上是一个NP 困难问题。

• 该问题的变种（决策版本）：给定 \(K\) 个桶，我们能否装下 \(N\) 个物品——这是个NPC 问题。

下面给出几种解决该问题的近似算法。

Online Algorithms⚓︎

void NextFit() {
    read item1;
    while (read item2) {
        if (item2 can be packed in the same bin as item1)
            place item2 in the bin;
        else
            create a new bin for item2;
        item1 = item2;
    } // end-while
}

void FirstFit() {
    while (read item) {
        scan for the first bin that is large enough for item;
        if (found)
            place item in that bin;
        else
            create a new bin for item;
    } // end-while
}

一些例题

例 1 例 2 例 3 例 4

题目答案

同“问题描述”部分给出的题目，现在要求你用上面讲到过的三种近似算法给出近似解。

题目答案

假设有以下物品：

\[ \begin{align} S_i = & \dfrac{1}{7} + \varepsilon, \dfrac{1}{7} + \varepsilon, \dfrac{1}{7} + \varepsilon, \dfrac{1}{7} + \varepsilon, \dfrac{1}{7} + \varepsilon, \dfrac{1}{7} + \varepsilon, \notag \\ & \dfrac{1}{3} + \varepsilon, \dfrac{1}{3} + \varepsilon, \dfrac{1}{3} + \varepsilon, \dfrac{1}{3} + \varepsilon, \dfrac{1}{3} + \varepsilon, \dfrac{1}{3} + \varepsilon, \notag \\ & \dfrac{1}{2} + \varepsilon, \dfrac{1}{2} + \varepsilon, \dfrac{1}{2} + \varepsilon, \dfrac{1}{2} + \varepsilon, \dfrac{1}{2} + \varepsilon, \dfrac{1}{2} + \varepsilon \notag \end{align} \]

其中 \(\varepsilon = 0.001\)，请比较它们的最优解和近似解（用上面给出的 3 种算法计算）。

• 最优解：6 个桶（每列物品放入一个桶，共 6 列）
• 近似解：10 个桶（三种近似算法得到相同的近似解）

因此对于本题，近似算法的效果并不是很理想。

如果从原物品集 \(L\) 中任意删除一个物品，对于 FF 算法而言，所需的桶数不一定减少，甚至还有可能增加，来看下面的例子：

• 原物品集 \(L = \{0.55, 0.7,0.55, 0.1, 0.45, 0.15, 0.3, 0.2\}\)
• 删除某个物品后的集合 \(L' = L - \{0.1\} = \{0.55, 0.7,0.55, 0.45, 0.15, 0.3, 0.2\}\)

结果对比：

题目答案

在原来题目描述的基础上增加一条限制：如果 \(S_i\) 和 \(S_j\) 位于同一个桶内，那么物品 \(S_{i+1}, S_{i+2}, \dots, S_{j-1}\) 也必须在这个桶内。请问上述哪种算法可以得到最优解？

Next Fit。它的思路很好地适应了题目给出的限制，但具体原因我不太清楚。

上述的三种近似算法实际上是一种在线算法(online algorithm)。对于本题，它的意思是：在处理下一个物品前就要放好当前物品，且不能改变当前的决策。

由于在线算法无法得知输入何时结束，因此始终无法得到最优解。具体来说，有以下定理：对于本题的所有近似算法，得到的近似解桶数至少是最优解桶数 \(\dfrac{5}{3}\) 倍。

Offline Algorithms⚓︎

由于在线算法的精确度不是很高，因此我们采用离线算法(offline algorithm) 来进一步改进，这种算法的思路是：在得到答案前需要检查所有的物品。

• 先找到问题的 trouble maker：尺寸较大的物品
• 解决方案——first/best fit decreasing：先将物品按大小的非递增顺序排序，然后应用 first fit 或 best fit 近似算法（两者近乎等价）求解。不难发现，该方法用到了贪心算法的思想。

例子

题目答案

同“问题描述”部分给出的题目。

动画演示

定理：令 \(M\) 为装下这些物品的最优解桶数，那么该方法（first fit decreasing）所得桶数不超过 \(\dfrac{11 M}{9} + \dfrac{6}{9}\)，并且存在某种输入使得桶数正好为 \(\dfrac{11 M}{9} + \dfrac{6}{9}\)。

Texture Packing⚓︎

算法：

• BL(Bottom-up Left-justified)：物品尽量靠近桶的左下角放置
  • 近似比：3

• NFDH(Next Fit Decreasing Height)：先对物品按高度降序放入桶内，并采用类似 bin packing 的 NFD 算法的策略——若桶的某一层内还能放入该物品则放进该层，否则将物品放入新的一层里。效果大致如下：

  
  • 近似比：2.7
  代码实现

  typedef struct item {
      double width;     
      double height;
      double x;        
      double y;      
  } Item;
  
  int FFDH(double W, int n, Item rect[]) {
      double curHeight = 0;         // current height of the bin
      double curWidth[maxNum];      // contain widths of each level 
      int level;                    // number of levels          
  
      sortByHeight(rect, n);
  
      level = 0;
      for (i = 0; i < n; i++)
          curWidth[i] = 0;
  
      for (i = 0; i < n; i++) {
          for (j = 0; j < level; j++) {
              if (curWidth[j] + rect[i].width <= W) {
                  rect[i].x = curWidth[j];              
                  rect[i].y = levelHeight[j];
                  curWidth[j] += rect[i].width;                                
                  break;
              } 
          }
          if (j < level)                                
              continue;
  
          // If not found
          ++level;                                 
          curWidth[level - 1] = rect[i].width;    
          levelHeight[level - 1] = curHeight;       
          curHeight += rect[i].height;             
          rect[i].x = 0;                         
          rect[i].y = levelHeight[level - 1];                             
      }
  
      return curHeight;
  }   
  

• FFDH(First Fit Decreasing Height)：与 NFDH 很像，也是 FFD 的二维版本

  • 近似比：2.7

• 还有很多算法就不展开介绍了，感兴趣的话可以参考 wiki

Knapsack Problems⚓︎

Fractional Version⚓︎

• 在每个阶段中，我们需要将一类物品放入背包内。
• 对于本题，我们尝试用贪心法来解决，所采取的贪心策略是：按价值密度(profit density) 大小 \(\dfrac{p_i}{w_i}\) 的降序挑选物品，直到背包被填满为止。

int knapsack_frac(int weight[], int val[], int n, int cap) {
    int i, j;
    double res = 0;

    // sort n items by densities of value, i.e. val[i] / weight[i], in descending order
    sort(weight, val, n);           

    for (int i = 0; i < n; i++) {
        // if the knapsack has enough space, put the whole item into the knapsack
        if (weight[i] <= cap) {
            res += val[i];
            cap -= weight[i];
        // if not, put part of the item into the knapsack
        } else {
            res += (double)(value[i] / weight[i]) * cap;
            break;
        }
    }

    return res;
}

注：更详细的解释可参考 Hello 算法。

0-1 Version⚓︎

现在回到 0-1 背包问题 ——它在上面一类背包问题的基础上多了一条限制：\(x_i = 0 \text{ or } 1\)。事实上，这个看似较为简单的问题，它竟是一个 NP 困难问题。下面我们对这类问题进行更进一步的分析。

从上面的例子中，我们可以发现贪心法在 0-1 背包问题中并不能成功找到最优解，因而是一种近似算法。下面来证明它实际上是一个2- 近似算法：

所以，用贪心法解 0-1 背包问题的效果不是很理想。通常的解法便是前面介绍过的动态规划，这里再介绍一种通过分析最小重量求解的 dp 算法：

• 令 \(W_{i, p}\) 为物品 1 到物品 \(i\) 之间的最小质量，而这些物品的总价值为 \(p = \sum\limits_{k = 1}^i p_k\)
• 分类讨论：
  • 取物品 \(i\)：\(W_{i, p} = w_i + W_{i - 1, p - p_i}\)
  • 不取物品 \(i\)：\(W_{i, p} = W_{i - 1, p}\)
  • 不可能得到价值 \(p\)：\(W_{i, p} = \infty\)
• 状态转移方程为：

• 其中，\(i = 1, \dots, n, p = 1, \dots, np_{\text{max}}\)，因此时间复杂度为 \(O(n^2 p_{\text{max}})\)

例子

题目答案

现在就来分析上述的极端情况：以下面给出的数据为例，当 \(n\) 不大，\(p_{\text{max}}\) 非常大（其实 \(p_i\) 都蛮大的）时，你会怎么做呢？

一种（也许）可行的做法是只保留 \(p_i\) 的高位，但保证能够区分这些 \(p_i\) 的大小：

• 但这种做法会损失价值的精度，且如果所有价值的位数一致时，这种做法就不太有效了
• 对于上述方法，有 \((1 + \varepsilon) P_{\text{alg}} \le P\)，其中 \(\varepsilon\) 为精度参数
• 我想到一种改进方法：将这些价值先排个序（升序），然后将这些价值与对应的索引建立一个双射关系，在状态转移方程的计算中用索引替代价值，最后再还原为真实的价值作为最大价值

K-center Problems⚓︎

聚类(clustering) 问题(clustering) 是把相似的对象通过静态分类的方法分成不同的组别或者更多的子集，使得同一子集中的成员对象都有一些相似属性的一种操作，常应用于数据挖掘、机器学习等领域。下面我们主要介绍一类聚类问题——K- 中心问题(K-center problem)。

问题描述

给定 \(n\) 个地址 \(s_1, \dots, s_n\)，在地图上选择 \(K\) 个中心点 \(c\)，使任意地址到离它距离最近的中心点之间的距离中的最大值最小化。

---

这么说可能不太好理解，下面给出符号化的定义：

本问题提到的距离 (distance) 不同于图论中边的权重，实际上它就是数学上本来的意思：

• 同一性 (identity)：\(dist(x, x) = 0\)
• 对称性 (symmetry)：\(dist(x, y) = dist(y, x)\)
• 三角不等式 (triangle inequality)：\(dist(x, y) \le dist(x, z) + dist(z, y)\)

令：

• \(dist(s_i, C) = \min\limits_{c \in C} \{dist(s_i, c)\}\)，即 \(s_i\) 到最近中心点间的距离
• \(r(C) = \max\limits_{i} \{dist(s_i, C)\}\)，即所有中心点中最大的最小覆盖半径，换句话说，就是以中心点为圆心的最小覆盖圆中，最大的那个圆的半径

目标：找到一组中心点集 \(C\)，使得 \(r(C)\) 最小化，且保证 \(|C| = K\)（\(K\) 为常数）

Naive Greedy⚓︎

由于平面是无限大的，穷举法显然是不可能的。下面介绍一种贪心策略：

• 让第一个中心点作为所有地址的中点（就好像只能放一个中心点）
• 随后加入的中心点满足能够减少 \(r(C)\) 值的条件

问题

如图所示，假设整个点集包括两个相距很远的子集，且 \(K = 2\)。此时第一个中心点就会被放在两个子集的中间，但最优解应该是中心点位于子集的中间位置的时候，所以这种贪心策略就失效了。

2r Greedy⚓︎

因此贪心法需要进一步的改进，先给出伪代码：

Centers Greedy-2r(Sites S[], int n, int K, double r) {
    Sites S`[] = S[];  // S` is the set of the remaining sites
    Centers C[] = NULL;
    while (S`[] != NULL) {
        Select any s form S` and add it to C;
        Delete all s` from S` that are at dist(s`, s) <= 2r;
    } // end-while
    if (|C| <= K) 
        return C;
    else
        ERROR("No set of K centers with covering radius at most r");
}

Smarter Greedy⚓︎

这个贪心法还可以再改进！还是先给出伪代码：

Centers Greedy-Kcenter(Sites S[], int n, int K) {
    Centers C[] = NULL;
    Select any s from S and add it to C;
    while (|C| < K) {
        Select s from S with maximum dist(s, C);
        Add s to C;
    }  // end-while
    return C;
}

• 这里的贪心法与上面的贪心法区别在于：后者是任意选取输入点集中的点作为中心点，而前者的策略是：

  • 第一个点还是任意取的
  • 之后选择离中心点集中的点尽可能远的点作为新的中心点，这样的选择方法更加聪明些
  • 循环 \(K\) 遍就结束循环了

• 定理：该算法返回包含规模为 \(K\) 的中心点集 \(C\)，使得 \(r(C) \le 2r(C^*)\)，其中 \(C^*\) 表示最优中心点集

• 很可惜的是，这种做法属于“换汤不换药”，本质上依旧是一个 2- 近似算法。

很遗憾的是，对于 K- 中心问题，除非 P = NP，不存在\(\rho < 2\) 的近似算法，下面给出证明：

评论区