算法设计与分析复习笔记之归约整理

作者: 小菜变大菜 | 来源:发表于2019-11-21 17:22 被阅读0次

归约是指问题A的任何实例能用问题B的方法来解决（判断），并且A的解为“是”，当且仅当B的解也是“是”。因此，证明归约是双向的，目前遇到的大多归约问题（A ≤p B）都可以按以下步骤进行：

构造图G，存在问题A的解集；
在图G基础上，构造图G'（常添加边或点），使得问题A的解集能反应在G'中问题B的解集（注意两个问题解集的规模k一定要有确定的联系）；
Claim：“图G中存在问题A的解集S，当且仅当图G'中存在问题B的解集S' ”；
双向证明，注意不要弄反方向。

也有不用构造新图的，比如点覆盖到独立集的规约，这种方法叫直接规约。但大多有些难度的归约一般都需要构造。除了前面笔记写的一部分归约证明，下面整理了老师说的需要重点掌握的归约。

Subset-Sum ≤p Partition

Partition：集合能划分成和相等的两部分。
构造子集和问题的实例，如集合 $S=\{x_{1}, x_{2}, ..., x_{n}\}$ ，子集和为W，需构造集合S'，使得集合S存在一个子集之和为W，当且仅当集合S'存在一个partition（ $\sum_{x\in A}x=\sum_{x\in \bar{A}}x$ ）
思路：构造集合 $S'=\{x_{1}, x_{2}, ..., x_{n}, x_{n+1}, x_{n+2}\}$ ，其中 $x_{n+1}=2\sum_{i\in S}x_{i}-W$ , $x_{n+2}=\sum_{i\in S}x_{i}+W$

Subset-Sum ≤p Partition

=>
S存在一个子集 $A=\{a_{1}, a_{2}, ..., a_{k}\}, a_{i}\in S, k\leq n$ ，有 $\sum_{i\in A}a_{i}=W$
那么集合S'中，有 $\sum_{i\in A}a_{i}+x_{n+1}=\sum_{i\in \bar A}a_{i}+x_{n+2}=2\sum_{i\in S}x_{i}$
所以集合S'存在一个划分 $A\bigcup \{x_{n+1}\}$ 和 $\bar A\bigcup \{x_{n+2}\}$
<=
集合S'能被划分为两个和相等的集合，可知 $x_{n+1}$ 和 $x_{n+2}$ 不在一个划分子集里
那么，存在一个集合A，设其元素之和为Y，有 $Y+x_{n+1}=\sum_{i\in S}x_{i}-Y+x_{n+2}$
解出 $Y=W$ ，即...

Subset-Sum ≤p Knapsack

Knapsack：给定物品的集合X，每个物品有重量 $u_{i}$ 和价值 $v_{i}$ ，背包最多承重 $U$ ，目标价值 $V$ 。问是否存在物品的一个子集S，使得 $\sum_{i\in S}u_{i}\leq U$ , $\sum_{i\in S}v_{i}\geq V$ ？
第一步构造Knapsack的实例，第二步证明集合X存在一个子集之和为W，当且仅当构造的Knapsack具有可行方案。
对一个子集和问题的实例 $(w_{1}, w_{2}, ..., w_{n}, W)$ ，构造Knapsack实例 $X$ ，满足
$\qquad w_{i}=u_{i}$ , $\sum_{i\in X}u_{i}\leq U$
$\qquad w_{i}=v_{i}$ , $\sum_{i\in X}v_{i}\geq V$

证明略（别的不会，略学得很像样）。

Subset-Sum ≤p Schedule

Schedule：一个工作序列，每个工作具有到达时间 $r_{j}$ ，处理时间 $t_{j}$ ，最迟完成时间 $d_{j}$ ，问如何安排这些工作，使得完成所有工作所需时间最短（在到达时间之后开始处理、最迟完成时间之前结束处理）？
思路：对于给定的集合 $\{w_{1}, w{2}, ..., w_{n}\}$ 和W，构造一个工作安排实例，证明若存在子集之和为W，当且仅当存在可行的工作安排。
集合 $X=\{w_{1}, w{2}, ..., w_{n}\}$ ，构造n个工作（从1开始编号），有 $r_{j}=0$ , $t_{j}=w_{j}$ , $d_{j}=1+\sum w_{j}$ ，就是对到达时间和最迟完成时间没有要求；再创建0号工作， $t_{0}=1$ , $r_{0}=W$ , $d_{0}=W+1$ .
这个证明就比较显而易见，但这个构造也太奇怪了，就是通过设置工作的到达时间和最迟完成时间来固定安排它们的位置。为什么可以构造这样的特例来证明呢？因为X≤pY，Y本身就是一个比X难的问题，那么我们就可以把Y的更多的约束条件舍去，让它变成和X比较相像或者复杂度相当的NPC问题。

Subset-Sum ≤p Schedule

Partition ≤p Load-Balance

集合 $X=\{x_{1}, x_{2}, ..., x_{n}\}$ ，构造Load-Balance实例 $Y=\{y_{1}, y_{2}, ..., y_{n}\}$ ，且每个工作的处理时间 $t_{j}=x_{j}$ ， $A\subseteq Y$ ，有 $\sum_{i\in A}t_{i}=\sum_{i\in \bar A}t_{i}$ .
证明略。