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

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

算法设计与分析复习笔记之归约整理
算法分析与设计复习
算法设计与分析复习
算法分析与设计复习目录
算法设计与分析（第3版）
考研766设计史论专业课之尹定邦《设计学概论》真题及答案整理
算法1
句柄与移入-归约分析的关系
算法设计与分析笔记之近似算法
如何学习数据结构与算法

归约是指问题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}$ .
证明略。

算法设计与分析复习笔记之归约整理
归约是指问题A的任何实例能用问题B的方法来解决（判断），并且A的解为“是”，当且仅当B的解也是“是”。因此，证明归...
算法分析与设计复习
1、排序算法 QuickSort 快速排序 MergeSort 归并排序 HeapSort 堆排序 BubbleS...
算法设计与分析复习
[toc] 题型判断题，对了得分，错了倒扣简答题概念、什么是平衡二叉树、什么是有向连通图给一个AVL树、SPl...
算法分析与设计复习目录
更新完成 2019/1/15 22:30 笔记方便你我他，复习还得靠大家（自己） ? 如果遗漏考点或内容出现错误...
算法设计与分析（第3版）
《算法设计与分析（第3版）》系统地介绍了算法设计与分析的概念和方法，共4篇内容。第1篇介绍算法设计与分析的基本概念...
考研766设计史论专业课之尹定邦《设计学概论》真题及答案整理
考研766设计史论专业课之尹定邦《设计学概论》真题及答案整理精选复习笔记考点：设计的理论阐述★★★ 设计作为一...
算法1
前言：重新复习算法相关内容，随便找了本算法书，记录一下心得，书名是《算法设计与分析——C++语言描述》，陈慧南编著...
句柄与移入-归约分析的关系
相关概念移入-归约分析关于该分析的介绍可以查看移入-归约分析句柄此概念在进行移入-归约分析时很重要，能否正确...
算法设计与分析笔记之近似算法
为什么使用近似算法无法找到一个NP难问题的多项式时间普适算法，因此我们思考牺牲算法的精确度，以在可计算时间内找到...
如何学习数据结构与算法
算法学习经验推荐：入门：数据结构启蒙：《数据结构与算法分析——C 语言描述》算法启蒙：《算法设计与分析基础...