Contributors

• 三、近似算法
  • 3.1 NP-完全性理论
  • 3.2 相关问题总结
  • 3.3 近似算法
    • 3.3.1 多机调度问题
    • 3.3.2 装箱问题 BP
    • 3.3.3 旅行商问题 TSP

转载自 cnblogs/学科笔记/中科大-算法分析与设计-近似算法复习知识点.md at main · BamLubi/cnblogs 中科大-算法分析与设计-近似算法复习知识点 - 小陆斑比 - 博客园[TOC]

三、近似算法

3.1 NP-完全性理论

图灵机：

• 确定性图灵机 DTM：执行的动作唯一
• 非确定性图灵机 NTM：执行的动作有多个可选

P 类问题：$P=L:L能在多项式时间内被DTM接受$

用确定性算法在多项式时间内可解

多项式时间内可解的问题$=$P

NP 类问题：$P=L:L能在多项式时间内被NTM接受$

用非确定性算法在多项式时间内可解

多项式时间内可验证的问$=$NP

多一规约：$L_1和L_2是两个判定问题，实例I_2=f(I_1)$

$$\begin{gathered} \forall I\in U_1,I是L_1输出yes的实例\iff f(I)是L_2输出yes的实例 \\ L1{\le }_m{L}_2 \end{gathered}$$

多项式时间多一规约：$f$是多项式时间可计算的

NPC 问题：对于判定问题 q，满足$1)q\in NP;2)NP{\le }_m^{p}q;$

NP-hard 问题：对于判定问题 q，满足$2)NP{\le }_m^{p}q;$

$NPC⊑NP-hard$

解题思路：

• $一个问题不可判定\Rightarrow 该问题\notin NP\Rightarrow 该问题\notin NPC$
• 证明$q\in NPH$，找到$q^{\prime }\in NPC/NPH$，再将$q^{\prime }$多项式归约到$q$。
• 如果继续证明$q\in NP$，则$q\in NPC$
• NPC 问题：SAT 可满足性问题、最大独立集问题、背包问题、覆盖问题、路径问题
• NPH 问题：停机问题

规约策略：

• $X{\le }_{p}Y,Y{\le }_{p}X\Rightarrow X{\equiv }_{p}Y$，$最大独立集问题{\equiv }_p最小顶点覆盖问题$

• 特殊到一般，$最小顶点覆盖问题{\le }_p最小集合覆盖问题$

3.2 相关问题总结

1. 独立集问题(Independent-Set)：图的顶点集合的子集中，所有顶点两两没有边。
2. 团问题：图的顶点集合的子集中，所有顶点两两均有边。
3. 顶点覆盖问题(Vertex-Cover)：图的顶点集合的子集中，边集中至少有一个顶点在该子集中。
4. 集合覆盖问题(Set-Cover)：非空集合的若干非空子集合的并集等于原有集合。
5. 3-SAT 问题：**3-CNF(合取范式)**组成的布尔公式存在真值解。
6. 哈密尔顿圈问题：图中通过每一个顶点恰好一次的回路。

上述问题均是 NPC 的。

单源最短路径和欧拉环是 P 问题。

3.3 近似算法

三种放宽要求的可能性：

• 超多项式时间启发：存在一个伪多项式时间的算法，如背包问题。（缺点：只对弱 NPC 问题有效）
• 概率分析：不再要求问题的解满足所有输入实例。（缺点：选取一个特殊的输入分布不容易）
• 近似算法：不再要求总是找到最优解。设计一个算法找出所有情况下的次优解来解 NP-hard 问题、

近似解分类：

• 容易近似：背包问题、调度问题、装箱问题
• 中等难度：顶点覆盖问题、欧式 TSP 问题、Steiner Trees
• 难于近似：着色问题、TSP、Clique(团)

性能保证：在最优解和近似解之间建立某种联系。

绝对性能度量：绝对近似算法是优化问题的多项式时间近似算法 A，$\exists k>0$，使得

$$\forall I\in D,|A(I)-OPT(I)|\le k$$

含义：近似解和最优解相差某一小的常数。

对于大多数的 NPH 问题，不存在绝对近似算法，除非$P=NP$。

两种绝对近似算法：

• 图是否可以 3 着色：

  • G 为二部图，即可 2 着色
  • G 一定可以 4 着色，四色定理
  • $|A(G)-OPT(G)|\le 2$

• 图边着色最小颜色数：

  • 最大度 / 最大度+1
  • $|A(G)-OPT(G)|\le 1$

前提：已知最优解 或 值所在的小范围

对于大多数 NPH 问题，存在绝对近似算法当且仅当存在多项式精确算法。

反证不存在绝对近似算法：

• 背包问题，通过 Scaling 放大利润为 k+1 倍，再算解的值
• 最大团问题，构造$G^{k+1}$

相对性能度量：算法 A 在一个输入实例上的性能比为

$$\begin{gathered} R_A(I)=\{\begin{array}{l}\frac{A(I)}{OPT(I)},最小化问题\\ \frac{OPT(I)}{A(I)},最大化问题\end{array} \\ 1\le R_A(I)\le 1+\epsilon ,A为(1+\epsilon )-近似算法 \end{gathered}$$

含义：近似解和最优解比值为某一小的常数。

• 绝对性能比：$R_A=inf\{r|R_A(I)\le r,\forall I\in D\}=性能比上界集合中的最小值$
• 渐近性能比：$R_A^{\infty }=inf\{r|R_A(I)\le r,\forall I\in D且OPT(I)\ge N\}=最优解要足够大$
• 最佳可达性能比：$R_{MIN}(\Pi )=inf\{r\ge 1|\exists 多项式时间算法A,R_A^{\infty }\le r\}$
  • $\{\begin{array}{l}1,最容易近似\\ 有界,△TSP问题\\ 无界,难于近似\end{array}$

$1\le R_A^{\infty }\le R_A<\infty$

对于有 Scaling 性质的问题，$R_A^{\infty }=R_A$

很多问题找不到绝对近似算法。

有些问题找不到有界性能比近似算法。

3.3.1 多机调度问题

List 调度算法：n 个作业依次分配给当前负载最小的机器。

$\frac{A(I)}{OPT(I)}\le 2-\frac{1}{m}$

证明上界：

$$>\begin{array}{rl}>& A(I)=L,作业运行时间最长\\ >& OPT(I)\ge \frac{\sum P_i}{m}\ge \frac{m(L-P_{last})+P_{last}}{m}\\ >& \Rightarrow OPT(I)\ge A(I)+\frac{1-m}{m}{P}_{last}\\ >& \because OPT(I)\ge P_{last}\\ >& \therefore 1\ge \frac{A(I)}{OPT(I)}+(\frac{1}{m}-1)\frac{P_{last}}{OPT(I)}\\ >& \therefore \frac{A(I)}{OPT(I)}\le (2-\frac{1}{m})\frac{P_{last}}{OPT(I)}\le 2-\frac{1}{m}>\end{array}>$$

证明紧确界：有$n=m(m-1)+1$个作业

$$>\begin{array}{rl}>& P_1=\cdots =P_{n-1}=1,P_n=m\\ >& OPT(I)=前n-1个机器每个运行m个作业+第n个机器运行P_n=m\\ >& A(I)=前n个机器每个运行m-1个作业+第1个机器运行P_n=2m-1\\ >& R_A=2-\frac{1}{m}>\end{array}>$$

LPT 调度算法：将作业递序排列，然后 List 策略调度。

$\frac{A(I)}{OPT(I)}\le \frac{4}{3}-\frac{1}{3m}$

3.3.2 装箱问题 BP

n 件物品，每件物品在单位大小之内，按某种策略装入单位大小的箱子中，令箱子数最小。

首次适应算法 FF

$R_{FF}(I)\le 2$，$R_{FF}^{\infty }=1.7$

证明：

最多只有一个箱子是大于半空的。

物品的总大小至少为总箱子的一半，$[\sum S_i]\ge \frac{1}{2}FF(I)$。

最优解至少为物品的总大小，$OPT(I)\ge [\sum S_i]$。

$R_{FF}(I)=2$

递减首次适应 FFD

$R_{FFD}\ge 1.5$，$R_{FFD}^{\infty }=\frac{11}{9}$

3.3.3 旅行商问题 TSP

求最短哈密顿回路 HC，访问所有顶点一次的回路。

这里研究$△TSP$，即输入满足三角不等式

近邻法 NN：从当前顶点访问最近尚未访问的顶点，一次构造哈密尔顿圈 HC。$R_{NN}^{\infty }=\theta (lgn)$

MST 启发：先找一个欧拉环 ET，然后再”Short-Cut“获得哈密尔顿圈。

$R_{NN}^{\infty }=2$

有欧拉环，当且仅当图连通且顶点度数均为偶数。

MST：

1. 构造最小生成树
2. 每条边复制一个
3. 找到欧拉圈
4. 短路欧拉路的方法构造 HC，即遇到重复顶点就跳过。

CH 启发：不需要将所有边都复制，只在每对奇度顶点之间连线。

$R_{CH}^{\infty }=1.5$

CH：

1. 构造最小生成树
2. 每对奇度顶点之间连线
3. 找到欧拉圈
4. 短路欧拉路的方法构造 HC，即遇到重复顶点就跳过。