首页课程学习算法设计与分析

# Overview

部分问题的解答中，关于怎么逻辑紧密的计算近似比，我实在理解不了、解释不了；

凑合背背应付考试吧

唯一能说的：

我们本节讨论的都是优化问题！！！

判断问题需要转化为优化问题！！！

# 顶点覆盖问题

image-20241224160445524

人话翻译：对于一张图，我要找一群点V′V'。你看一条边两头不是有两个点吗，我要求对 G 图任意一条边ee，都有V′V' 中的一个点是 e 的两头之一

因为你想选最少的点解决问题，所以问题成本 C 就是选了多少个点，即点的数量

# 具体近似算法

随机算法，一开始V′V' 为空，

  1. 在 G 图上任取一条边 e
  2. 将 e 的两端点u,vu,v 并入V′V'
  3. 把EE 中所有以 u 为一头端点的边删掉，再把EE 中所有以 v 为一头端点的边删掉
  4. 循环，直到 E 为空

# 时间复杂度

每次循环都会选出两点一边，所以你的算法时间复杂度为O(C/2)O(C/2)

# 近似率

对于近似率Q(n)Q(n)，由于这是一个求最小问题，俺们的方法应该比最优方法要孬。近似比永远不小于 1，小的放分母，所以把最优CoptC_{opt} 放分母上

那咋算呢，回顾我们的随机算法，我们每轮循环会随机选一条边。到结束，我们选择所有边，是一群没有公共顶点的边，数量为 k。那我们的近似算法就选择了 2k 个点；

对于 k 个没有公共顶点的边，只要满足题设条件，那每条边至少要选一个顶点。所有满足条件的选法，其选点数量C≥kC\ge k，最优选法是 {所有满足条件的选法} 的一员，所以Copt≥kC_{opt}\ge k

那CoursCopt≤2\dfrac{C_{ours}}{C_{opt}}\le 2，近似率为 2

# 集合覆盖问题

image-20241222174401067

人话翻译：对于 n 个元素，我有一系列元素组成的集合{S}={S1,S2,…,Sm}\{S\}=\{S_1,S_2,\dots,S_m\}。这群集合并在一起覆盖了每个元素，但我嫌mm 太多了，我想从这mm 个集合中选一部分{S′}\{S'\}，{S′}\{S'\} 含有 k 个子集。{S′}\{S'\} 里所有子集并起来依然能覆盖所有元素，希望 k 最小

因为你想选最少数量的子集解决问题，所以问题成本 C 就是选了多少个子集，即子集的数量

# 具体近似算法

贪心算法，一开始{S}\{S\} 包含 m 个子集；{x}\{x\} 表示所有还没被覆盖过的元素，初始为{S}\{S\} 并起来的所有元素

  1. 在S{S} 中选择一个SkS_k，SkS_k 中包含的元素和{x}\{x\} 交集最大；换句话，SkS_k 能覆盖最多的还没被覆盖的元素
  2. {S}\{S\} 中删除SkS_k
  3. {x}\{x\} 中删除所有SkS_k 的元素
  4. 循环，直到所有元素被覆盖

# 时间复杂度

每次循环都会选出一个子集，所以你的算法时间复杂度为O(C)O(C)

# 近似率

对于近似率Q(n)Q(n)，由于这是一个求最小问题，近似方法应该比最优方法要孬。近似比永远不小于 1，小的放分母，所以把最优CoptC_{opt} 放分母上

回顾我们的随机算法，假设第 k 轮循环，{xk}\{x_k\} 大小为numknum_k，也就说还有numknum_k 个元素一次都没被覆盖过

对于原{x}\{x\}，CoptC_{opt} 大小的{S′}\{S'\} 可以并起来全部覆盖；{xk}\{x_k\} 是{x}\{x\} 的一部分，所以{S′}\{S'\} 也能覆盖{xk}\{x_k\}，且{S′}\{S'\} 中的每个子集，平均要覆盖{xk}\{x_k\} 中numk/Coptnum_k/C_{opt} 个元素。

那放在这第 k 轮循环里，{Sk}\{S_k\} 中依然有{S′}\{S'\} 中的子集S′S'；不然若没有，说明之前的循环中已经把{S′}\{S'\} 取完了，那已经全覆盖了，不需要看第 k 轮循环了

子集S′S' 至少要覆盖numk/Coptnum_k/C_{opt} 个{xk}\{x_k\} 中的元素：因为numknum_k 被CoptC_{opt} 个子集S′S' 瓜分

  • 要是{S′}\{S'\} 在第kk 轮一个没少，那分母是CoptC_{opt}；
  • 要是第 k 轮之前有的S′S' 被选走过了，但他们一个{xk}\{x_k\} 中的元素没覆盖到，不干活；剩下的S′S' 数量更少了，平均每个要分的{xk}\{x_k\} 中的元素更多了；

在第 k 轮我们选择子集SkS_k，这个选择是贪心的，是能覆盖{xk}\{x_k\} 中元素数量最多的，所以Sk>S′S_k>S'，SkS_k 至少能覆盖numk/Coptnum_k/C_{opt} 个没覆盖过的元素，SkS_k 覆盖新元素数≥numk/Copt\ge num_k/C_{opt}

那对于 k+1 轮循环，numk+1=numk−Sknum_{k+1}=num_k-S_k 覆盖新元素数，得：numk+1≤numk×(1−1/Copt)num_{k+1}\le num_k\times(1-1/{C_{opt}})

递推，得：numk≤num0×(1−1/Copt)knum_{k}\le num_0\times(1-1/{C_{opt}})^k，num0num_0=n = 输入元素个数

令左边 < 1，经过数值计算化简，得到：

kt>ln(n)\dfrac{k}{t}>ln(n)

k 是近似算法的最小值，k=⌈tln(n)⌉k=\lceil tln(n)\rceil，由于Cours=kC_{ours}=k，

所以CoursCopt≤ln(n)+1/t≤ln(n)+1\dfrac{C_{ours}}{C_{opt}}\le ln(n)+1/t \le ln(n)+1

# 分组问题

image-20241222183131991

其中a1>a2>⋯>ana_1>a_2>\dots>a_n

人话翻译：对于 n 个元素的集合，我想切两半，使得集合的总和尽量平分到两个子集里

假设∑A=2L\sum A=2L，题目的目标将AA 划分为X,YX,Y 两集合，求max(∑X,∑Y)max(\sum X,\sum Y) 的最小值

所以问题成本CC 就是max(∑X,∑Y)max(\sum X,\sum Y)，Copt=LC_{opt}=L

# 具体近似算法

随机算法：

  1. 先随机对前 m 个元素随机分配，划入 X，Y

  2. 对{am+1,…,an}\{a_m+1,\dots,a_n\} 中的每一个aka_k，判断∑X\sum X 和∑Y\sum Y，选择较小的一方，将aka_k 加入其中

  3. 循环，直到k=nk=n

# 时间复杂度

时间复杂度O(n−m)O(n-m)

# 近似率

由于这是一个求最小问题，近似方法应该比最优方法要孬。近似比永远不小于 1，小的放分母，所以把最优CoptC_{opt} 放分母上

回顾我们的随机算法，不妨假设最终∑X>∑Y\sum X>\sum Y，Q(n)=∑X/LQ(n)=\sum X/L

考虑集合AA 中最后一个被分到XX 的元素aka_k，它是集合 A 的第kk 个元素，那么元素aka_k：

  • 来自步骤 1，是随机分配时分入XX
  • 来自步骤 2，在分配aka_k 前，∑X<∑Y\sum X<\sum Y

前一种情况暂不考虑（不知道咋考虑……）

考虑后一种情况，其满足：

∑Xk−ak≤∑Yk≤∑A−∑Xk\sum X_k - a_k \le \sum Y_k\le \sum A -\sum X_k

其中∑Xk,  ∑Yk\sum X_k,\;\sum Y_k 表示划分完aka_k 后两子集的元素和

变形可得：

∑Xk≤L+ak2\sum X_k \le L + \dfrac{a_k}2

由a1>a2>⋯>ana_1>a_2>\dots>a_n，我们可以得到：

∑A≥∑Xk+∑Yk=sum(a1,a2,…,ak)≥(m+1)×ak\begin{align*} \sum A&\ge \sum X_k +\sum Y_k\\ &=sum(a_1,a_2,\dots,a_k)\\ &\ge (m+1)\times a_k \end{align*}

所以Q(n)=∑X/L<1+11+mQ(n)=\sum X/L<1+\dfrac{1}{1+m}