草草草AV,精品久久人妻无码

歸約是指問題A的任何實例能用問題B的方法來解決（判斷），并且A的解為“是”，當(dāng)且僅當(dāng)B的解也是“是”。因此，證明歸約是雙向的，目前遇到的大多歸約問題（A ≤p B）都可以按以下步驟進行：

構(gòu)造圖G，存在問題A的解集；
在圖G基礎(chǔ)上，構(gòu)造圖G'（常添加邊或點），使得問題A的解集能反應(yīng)在G'中問題B的解集（注意兩個問題解集的規(guī)模k一定要有確定的聯(lián)系）；
Claim：“圖G中存在問題A的解集S，當(dāng)且僅當(dāng)圖G'中存在問題B的解集S' ”；
雙向證明，注意不要弄反方向。

也有不用構(gòu)造新圖的，比如點覆蓋到獨立集的規(guī)約，這種方法叫直接規(guī)約。但大多有些難度的歸約一般都需要構(gòu)造。除了前面筆記寫的一部分歸約證明，下面整理了老師說的需要重點掌握的歸約。

Subset-Sum ≤p Partition

Partition：集合能劃分成和相等的兩部分。
構(gòu)造子集和問題的實例，如集合 $S=\{x_{1}, x_{2}, ..., x_{n}\}$ ，子集和為W，需構(gòu)造集合S'，使得集合S存在一個子集之和為W，當(dāng)且僅當(dāng)集合S'存在一個partition（ $\sum_{x\in A}x=\sum_{x\in \bar{A}}x$ ）
思路：構(gòu)造集合 $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，設(shè)其元素之和為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$ ？
第一步構(gòu)造Knapsack的實例，第二步證明集合X存在一個子集之和為W，當(dāng)且僅當(dāng)構(gòu)造的Knapsack具有可行方案。
對一個子集和問題的實例 $(w_{1}, w_{2}, ..., w_{n}, W)$ ，構(gòu)造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$

證明略（別的不會，略學(xué)得很像樣）。

Subset-Sum ≤p Schedule

Schedule：一個工作序列，每個工作具有到達時間 $r_{j}$ ，處理時間 $t_{j}$ ，最遲完成時間 $d_{j}$ ，問如何安排這些工作，使得完成所有工作所需時間最短（在到達時間之后開始處理、最遲完成時間之前結(jié)束處理）？
思路：對于給定的集合 $\{w_{1}, w{2}, ..., w_{n}\}$ 和W，構(gòu)造一個工作安排實例，證明若存在子集之和為W，當(dāng)且僅當(dāng)存在可行的工作安排。
集合 $X=\{w_{1}, w{2}, ..., w_{n}\}$ ，構(gòu)造n個工作（從1開始編號），有 $r_{j}=0$ , $t_{j}=w_{j}$ , $d_{j}=1+\sum w_{j}$ ，就是對到達時間和最遲完成時間沒有要求；再創(chuàng)建0號工作， $t_{0}=1$ , $r_{0}=W$ , $d_{0}=W+1$ .
這個證明就比較顯而易見，但這個構(gòu)造也太奇怪了，就是通過設(shè)置工作的到達時間和最遲完成時間來固定安排它們的位置。為什么可以構(gòu)造這樣的特例來證明呢？因為X≤pY，Y本身就是一個比X難的問題，那么我們就可以把Y的更多的約束條件舍去，讓它變成和X比較相像或者復(fù)雜度相當(dāng)?shù)腘PC問題。

Subset-Sum ≤p Schedule

Partition ≤p Load-Balance

集合 $X=\{x_{1}, x_{2}, ..., x_{n}\}$ ，構(gòu)造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}$ .
證明略。