Cuckoo!
0%

CS216 算法设计与分析 期末复习

Posted on Edited on In
原来算法学了这么多吗(＃°Д°)!

$\huge\text{Outline}$

  1. 稳定匹配
  2. 算法分析
  3. 贪心
    1. 调度
    2. Dijkstra
    3. 最小生成树
    4. 最小树形图
    5. 哈夫曼树
    6. 缓存
  4. 分治
    1. $O(n\log n)$求逆序对
    2. $O(n)$求第k小
    3. $O(n\log n)$求平面最近点对
    4. 整数/矩阵乘法
    5. FFT与卷积
  5. 动态规划
    1. 带权区间调度
    2. 分段最小二乘
    3. 背包问题
    4. 区间DP
    5. 带负环图最短路
  6. 难问题
    1. 归约
    2. P, NP, NPC
  7. 网络流
    1. 最大流与最小割
    2. Ford-Fulkerson
    3. Capacity-Scaling
    4. Edmonds-Karp
    5. Dinitz’s
    6. 二分图匹配
    7. 不相交路径
    8. 多源多汇网络流
    9. 调查设计
    10. 航班调度
    11. 图像分割
  8. 随机化算法
    1. 访问调度
    2. 全局最小割
    3. 最大3-SAT
    4. 负载均衡

Chapter 1 - 稳定匹配

定义(一对一匹配)

输入：两个集合 $A=\{a_1,\cdots,a_n\}, B=\{b_1,\cdots,b_n\}$，以及每个元素对另一集合所有元素的偏好表。

完美匹配：$f:A\rightarrow B$是双射

不稳定对：未出现在匹配中，且双方对对方的偏好程度均高于当前匹配的偏好程度。例如匹配中存在$(a_1,b_1),(a_2,b_2)$，但$a_1$相比$b_1$更偏好$b_2$，且$b_2$相比$a_2$更偏好$a_1$，那么$(a_1,b_2)$被称为不稳定对。

稳定匹配：不存在不稳定对的完美匹配

Gale-Shapley 算法

保证可以找到一个稳定匹配的算法，此处以婚配为例。

1
2
3
4
5
6
7
8
9
10
11
12
Initialize each person to be free.
while (some man is free and hasn't proposed to every woman)
{
	Choose such a man m
    w = 1st woman on m's list to whom m has not yet proposed
    if (w is free)
    	assign m and w to be engaged
    else if (w prefers m to her fiancé m')
    	assign m and w to be engaged, and m' to be free
    else
    	w rejects m
}

GS算法 - 正确性证明

Observation.

  1. 主动方按照偏好表降序提出匹配请求
  2. 被动方一旦匹配，就不会回到未匹配状态，只会更换到更偏好的匹配

算法一定终止

Claim. 算法在至多$n^2$轮while循环后终止

Proof. 每次while循环，主动方会向一个新的被动方提出匹配请求，两个大小为$n$的集合至多有$n^2$种匹配，因此算法复杂度$O(n^2)$。

匹配的完美性

Claim. 所有元素在算法终止后都有匹配

Proof. 反证法：假如某个主动方未被匹配，那么一定存在一个未被匹配的被动方。由Observation 2，该被动方一定从未收到匹配请求。但算法终止时主动方已对所有被动方进行了请求且仍未被匹配，引出矛盾。

匹配的稳定性

Claim. 结果中不存在不稳定对

Proof. 反证法：

记结果匹配为$S^\star$，其中存在配对$(a,y), (x,b)$。

假设存在不稳定对$(a,b)$，即$a$相比$y$更偏好$b$，而$b$相比$x$更偏好$a$

  1. $a$未向$b$发起匹配请求

    说明$a$相比$b$更偏好$y$，引出矛盾

  2. $a$向$b$发起过匹配请求

    $b$拒绝了$a$，当即 或是 过了一会儿

    说明$b$相比$a$更偏好$x$，引出矛盾

两种情形均矛盾，因此不存在不稳定对。

算法实现

全局维护一个未匹配的主动方集合，每次选取其中的主动方进行匹配。

对于主动方，维护一个偏好值降序的队列，依次进行匹配请求。

对于被动方，维护一个从主动方到偏好值的映射，用于比对当前匹配是否更优，如有替换则将前任放回全局未匹配主动方集合。

主被动方利益分析

有效对象：如果某个稳定匹配中存在$(a,b)$，那么$a,b$互为有效对象。

主动方最优性

Claim. GS算法得到的解$S^\star$对于主动方是最优的(每个主动方得到最优有效对象)

Proof. 反证法：

假如不是主动方最优的，那么一定有某个主动方未与其最优有效对象匹配。

由于主动方是降序请求的，因此一定是被其最优有效对象拒绝了。

令首个这样的主动方为$a$，其最优有效对象为$b$。在$b$拒绝$a$时，一定更偏好于某个主动方$x$。由于$a$是首个被最优有效对象拒绝的主动方，所以$x$此时没有被任何有效对象拒绝过，即$b$是$x$的最优有效对象。

随后，由于$a$的最优有效对象是$b$，我们找到包含$(a,b)$的稳定匹配$S$，$S$包含$(x,y)$。根据上述分析，$b$相比$a$更偏好$x$，而$x$相比任何其他有效对象更偏好$b$，因此$(x,b)$是匹配$S$的不稳定对，引出矛盾。

被动方最劣性

Claim. GS算法得到的解$S^\star$对于被动方是最劣的(每个主动方得到最劣有效对象)

Proof. 反证法：

假如不是被动方最劣的，那么一定有某个被动方未与其最劣有效对象匹配。

假如$S^\star$包含$(a,b)$，但$a$并不是$b$的最劣有效对象，假设其最劣有效对象为$x$。

我们找到包含$(x,b)$的稳定匹配$S$，$S$包含$(a,y)$。$b$相比$x$更偏好$a$，由主动方最优性，$b$一定是$a$的最优有效对象，即$a$相比$y$更偏好$b$，因此$(a,b)$是匹配$S$的不稳定对，引出矛盾。

一对多匹配

一对多匹配中，集合$A$中的一个元素可以与集合$B$中的多个元素匹配，此处将$A$中元素作为主动方进行讨论。

不稳定对$(a,b)$满足以下所有条件：

  • $a,b$ 相互是可接受的
  • 主动方$a$仍然有匹配容量，或者$a$相比其已经匹配的所有被动方元素更偏好$b$
  • 被动方$b$未被匹配，或者$b$相比其已经匹配的主动方更偏好$a$

扩展GS算法

将具有容量的一方作为被动方，全局维护未匹配主动方的集合。

对于每个主动方，维护一个偏好值降序列表，依次进行匹配请求。

对于每个被动方，维护一个长度为容量的优先队列，存放当前被匹配的所有被动方。如果有更偏好的主动方请求匹配，将队首(偏好值最低)的主动方放回未匹配集合。

扩展GS算法的正确性和利益分析与上文所述类似，证明可参考Assignment 1。

Chapter 2 - 算法分析

运行时间分析

最坏运行时间：给定输入数据规模，在所有不同的输入中，算法最大运行时间

平均运行时间：给定输入数据规模，对于随机的一个输入，算法的运行时间

最坏运行时间为多项式复杂度的算法被认为是高效的

Asymptotic Order of Growth

这玩意咋翻译来着，渐进时间复杂度吗

$O(n),\Omega(n),\Theta(n)$都是老朋友了

传递性，可加性，可乘性

常见算法时间复杂度

类型 时间复杂度 应用
常数(Constant) $O(1)$ 打表
对数(Logarithmic) $O(\log n)$ 二分查找
线性(Linear) $O(n)$ 求极值
算术线性(?)(Linearithmic) $O(n\log n)$ 归并排序，堆排
平方(Quadratic) $O(n^2)$ 暴力最近点对
立方(Cubic) $O(n^3)$ 集合不相容
指数(Exponential) $O(c^n)$ 暴力最大独立集

独立集问题

区间调度：$O(n\log n)$贪心

带权区间调度：$O(n\log n)$动态规划

二分图匹配：$O(n^k)$基于最大流算法

最大独立集：NP-complete

竞争便利店选址问题：PSPACE-complete

均摊分析

这是赵老师的Lab课件内容，不过内容还挺重要的，之后再补吧。

Chapter 3 - 贪心

区间调度

问题：工作用一系列区间表示，工作不可并行，每个工作等权，最大化截止时间前完成的工作数。

贪心算法：按照DDL升序排序，贪心地选择当前尚未错过开始时间且DDL最近的一个完成。

Theorem. 贪心算法是最优的

Proof. 反证法：假如贪心算法结果不是最优，令贪心结果为$\{i_n\}$，最优结果为$\{j_m\}$，且两种方案的前$r$项相同。我们在所有最优解中，找到一个$\{j_m\}$使得其和贪心方案的重叠部分最多，即$r$最大。

由贪心策略，$i_{r+1}$的结束时间一定不会晚于$j_{r+1}$，那么我们将$i_{r+1}$替换$\{j_m\}$方案中的$j_{r+1}$，依然会得到一个最优的可行解，但是此时的重叠部分长度为$r+1$，引出矛盾。

区间划分

问题：课程用一系列区间表示，课程不可在同一教室并行，求安排下所有课程所需的最小教室数量。

贪心算法：按照开课时间升序排列，申请的所有教室按照最后一堂课的结束时间

放进优先队列，对于每节课，看上节下课最早的教室能不能放下，能的话就放，如果放不下那就新开一个教室加入队列。

Theorem. 贪心算法是最优的

记贪心算法申请的教室数为$d$

第$d$个教室是因为贪心算法在规划第$j$节课时，前$d-1$个教室都放不下了，即该$d-1$个教室的最后一堂课的下课时间都比$j$的上课时间晚。

由于贪心按上课时间升序排列课程，所以这$d-1$个教室中的课程开始时间都比$j$的开始时间要晚，因此在第$j$节课开课后有$d$节课在同时上课。

根据题意，要能支持$d$节课同时进行至少需要$d$个教室，即不存在比贪心解更优的解。

最小化迟到

问题：给定工作耗时和DDL，同时只能做一件事，迟到值设定为完成时间与DDL之间的差值，最小化最大的迟到值。

贪心算法：DDL越早越先做

Observation. 存在没有任何空闲间隔的最优解，贪心解也没有任何空闲间隔

Observation. 对于没有空闲间隔的解，如果存在两个任务，DDL早的后完成，DDL晚的先完成，则称为一个逆序对。如果一个解有逆序对，那一定有一对连续规划的逆序对。(why?)

Claim. 交换逆序对不会使最大迟到值增加。

Proof. 记交换前的迟到值为$l$，交换后为$l’$，工作完成时间为$f$，截止时间为$d$。

  • 对于$k\ne i,j$，$l_k’=l_k$
  • $l_i’\le l_i$
  • $l_j’ = \max\{0,f_j-d_j\} = \max\{0,f_i-d_j\}\le \max\{0,f_i-d_i\} = l_i$

Theorem. 贪心解$S$是最优的

Proof. 令$S^\star$为一个没有空闲间隔且逆序对数量最少的最优解。

如果$S^\star$没有逆序对，那么$S=S^\star$；

如果有逆序对，记相邻逆序对为$(i,j)$。交换$i,j$不会得到更劣解，但是将逆序对数量减少了1，引出矛盾。

Dijkstra

这也是老朋友了，每次贪心地挑dis最小的一个点去更新其他所有点。

Invariant. 对于每个已探索集合$S$中的点$u$，$d(u)$即为$s-u$最短路的长度。

Proof. 归纳法：

基态：$|S|=1$时，显然。

归纳假设：假设对于$|S|=1,\cdots,k$的时候结论均成立

记下一个探索的点为$v$，选中的边是$(u,v)$，此时$s-v$路径的长度为$\pi (v) = d(u)+l_{(u,v)}$。考虑任一$s-v$路径$P$，假设$(x,y)$是路径上离开$S$的第一条边，记到$x$的子路径为$P’$，那么有如下不等式：

从左到右四个不等号的原因分别为：边权非负，归纳假设，$\pi(y)$和$\pi(v)$的定义。由此证明了$d(v)=\pi(v)$即为$s-v$最短路的长度，$|S|=k+1$的时候也成立。

$A^\star$

给定起点和终点，引入启发式函数，用$h(v,t)+\pi(v)$作为优先级。

$h(v,t)<d(v,t)$时保证结果正确，有可能比Dijkstra更快

$h(v,t)=d(v,t)$时保证结果正确，最快，但需要完全正确的知识

$h(v,t)>d(v,t)$时，并不总能得到正确结果，不过可能还是快一些

最小生成树

Prim

维护一个已选点的集合，迭代$n-1$次，每次将连接生成树和树外一点的最短边加入树，并且把树外断点加入集合。$O(m\log n)$

Kruskal

将边按边权升序排列依次加入生成树，如果成环了就不加（并查集）。$O(m\log m)$

Reverse-Delete

按照边权降序排列边，如果删边不影响连通性就删，重复m次。$O(m\log n (\log\log n)^3)$

Borůvka

对于每个连通块，选择所有一端在连通块内，另一端在外的边中边权最小的一个加入生成树，迭代直到只剩一个连通块收工。$O(m\log n)$

单链路 K-聚类

问题：给定集合$U$，初始包含$n$个对象，将其分入$k$个非空集合，最大化不同集合之间距离的最小值。

贪心算法：用Kruskal算法，但是只加$n-k$条边。等价于找最小生成树，然后删掉最贵的$k-1$条边。

Theorem. 贪心算法是最优的

待补。

最小树形图

问题：给定有向图$G$和根节点$r$，边权非负，求根节点位于$r$的最小树形图。

对于每个非根节点$v$，$y(v)$表示进入$v$的所有边中最小的边权，边$(u,v)$削减后的边权记为$c’(u,v)=c(u,v)-y(v)\ge 0$。

朱刘算法 / Edmonds’ Algorithm

对于每个非根节点$v$，选择最小入边，构成边集$E^\star$

$E^\star$中的所有边的削减后边权均为0，如果此时$E^\star$不包含环，则找到了最小树形图。

如果包含一个环$C$，那么将$C$收缩为一个超级结点，并删除其自环。

不断执行上述过程直到得到一个最小树形图，随后展开环删边断环即可。

正确性证明

较为复杂，可参考课件，待补。

哈夫曼编码

算法流程

对于一个前缀编码格式$\gamma$，ABL (average bits per letter) 是每个字符的出现频率与其编码位数的乘积的和：

哈夫曼编码：每次贪心选取出现频率最低的两个结点，将其连接到同一个父结点上，定义父节点的出现频率为两个子节点之和。伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Huffman(S)
{
    if |S| == 2
    {
    	return tree with root and 2 leaves
    }
    else
    {
        let x and y be lowest-frequency letters in S
        let S’ be S with x and y removed
        insert new letter ω in S’ with f[ω] = f[x] + f[y]
        T’= Huffman(S’)
        T = add two children x and y to leaf ω from T’
        return T
    }
}

相关证明

时间复杂度：$T(n)=T(n-1)+O(\log n)$，因此$T(n)=O(n\log n)$。

Claim. $ABL(T)=ABL(T’)+f_w$

Proof. $T$是由$T’$的$w$结点下接$x,y$结点形成的。

Observations.

  • 在最优的前缀编码树中，出现频率最低的字符对应的结点应该出现在最底层
  • $n>1$时，最低层总是有至少两个叶子节点
  • 同一层中的顺序并不影响编码最优性

Claim. 存在最优的前缀编码树，使得出现频率最低的两个字符作为树的两个相邻的叶子节点。

Claim. 对于给定字符集$S$，在所有前缀编码中，哈夫曼编码有最小的ABL。

Proof. 归纳法：

基态：对于$|S|=2$，没有比一根两叶更短的编码了

归纳假设：假设对于字符集$S’$，哈夫曼树$T’$给出的编码是最优的。其中$S’$没有加入最小频率的$x,y$而将$w$作为叶节点。

归纳步骤：反证法。

令$T$是哈夫曼树，假设存在树$Z$使得$ABL(Z)<ABL(T)$，不失一般性地假设$Z$中$x, y$是相邻的叶子节点。将$x,y$从$Z$中删除得到$Z’$，记其父节点为$w’$。

由于$ABL(Z)=ABL(Z’)+f_{w’}$，$ABL(T)=ABL(T’)+f_w$，且$ABL(Z)<ABL(T)$，$f_w=f_{w’}$，得到$ABL(Z’)<ABL(T’)$，与假设矛盾。

也可以参考DSAA课程给的证明

最优缓存

离线缓存 vs. 在线缓存：是否已知全部访问序列

贪心替换：LIFO, FIFO, LRU, LFU

最优贪心算法：Farthest-in-future (FF)，替换掉最晚在未来的访问中出现的成员。

最优性证明比较微妙，建议自己看课件过一遍。

Chapter 4 - 分治

逆序对计数

$O(n\log n)$归并排序求逆序对

1
2
3
4
5
6
7
8
9
10
Sort-and-Count(L)
{
    if list L has one element
    	return (0, L)
    Divide the list into two halves A and B
        (rA, A) = Sort-and-Count(A)
        (rB, B) = Sort-and-Count(B)
        (rAB, L) = Merge-and-Count(A, B)
    return (rA + rB + rAB, L)
}

线性求第k小

这位更是印象深刻（✟Bo门✟

随机化方法

随机选个主元(pivot)，将数组分为大于/小于/等于主元的三部分，数数第k大在哪一组，然后递归继续。

1
2
3
4
5
6
7
8
9
10
11
Quick-Select(A, k)
{	// 1 ≤ k ≤ |A|
    Pick pivot p uniformly at random from A
    Partition the list into two three parts L, M and R
    if k ≤ |L|
    	return Quick-Select(L, k)
    else if k > |L| + |M|
    	return Quick-Select(R, k - |L| - |M|)
    else
    	return p
}

记$T(n,k)$为在长度为$n$的数组中求第$k$小的比较次数，记$T(n)=\max_kT(n,k)$。

Claim. $T(n)\le 4n$

Proof. 强归纳：

确定性算法：中位数的中位数，优化版本大概要5.4305次比较，常数太大了实际一般不用，不过借鉴选主元的思路倒是不错。

平面最近点对

分治典中典。

问题：平面上$n$个点，找到点对间最小欧氏距离。

分治算法：按$x$坐标排序，分为数量相等的左右两部分。拆分：递归地分成两部分求子区域的最近点对距离；合并：左半边，右半边，以及左右两部分之间的点对距离。

记左右两部分内部的最近点对距离为$\delta$，合并时，只需要考虑横坐标在中点$±\delta$的点就足够了。对于中心区域的每个点$i$，我们也只需要考虑$y_i-\delta<y_j\le y_i$的点$j$，因为每个点都要考虑所以只保证半边就行。为了方便比较$y$坐标，按$y$坐标再进行排序，这里排序可以用类似归并的方法，将低层递归排序后的点集归并即可，复杂度是$O(n)$的。

对于点$i$，记它需要比较的点集为$C_i$，$C_i$可能的分布范围是一个长为$2\delta$

宽为$\delta$的矩形，且$i$位于上长边的中点。将该矩形切分为8个${\delta\over2}*{\delta\over2}$的小正方形，那么每个小正方形内至多只能有一个点，除去$i$之后最多只有7个点。反证：每个小正方形内如果存在两个点，那么它们的距离最大值是$\delta\over\sqrt 2$，比之前设定的单边最小距离$\delta$还要小，引出矛盾。所以对于每个点$i$，我们只需要比对至多$7$个点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Closest-Pair(p1, ..., pn)
{
    Compute vertical line L such that half the points
    are on one side and half on the other side.
    
    δ1 = Closest-Pair(left half)
    δ2 = Closest-Pair(right half)
    δ = min(δ1, δ2)
    
    Delete all points further than δ from line L.
    
    Sort remaining points by y-coordinate.
    
    Scan points in y-order and compare distance between
    each point and next 7 neighbors. If any of these
    distances is less than δ, update δ.
    
    return δ
}

整数乘法

竖式乘法：$\Theta(n^2)$

基础分治乘法：$x\cdot y =(2^ma+b)\cdot(2^mc+d) = 2^{2m}ac+2^m(ad+bc)+bd$。$T(n)=4T({n\over 2})+O(n)$，依然$\Theta(n^2)$

Karatsuba分治：$x\cdot y = 2^{2m}ac+2^m(ac+bd-(a-b)(c-d))+bd$。$T(n)=3T({n\over2})+O(n)$，降到了$\Theta(n^{\log_23})=\Theta(n^{1.585})$

分块矩阵乘法

$\begin{bmatrix}
C_{11} & C_{12}\\
C_{21} & C_{22}
\end{bmatrix}=\begin{bmatrix}
A_{11} & A_{12}\\
A_{21} & A_{22}
\end{bmatrix}\times\begin{bmatrix}
B_{11} & B_{12}\\
B_{21} & B_{22}
\end{bmatrix}$

基础乘法：$C_{ij}=(A_{i1}\times B_{1j})+(A_{i2}\times B_{2j})$。$T(n)=4T({n\over2})+O(n^2)$，$T(n)=O(n^3)$

Strassen分治：用7次矩阵乘法计算$P_1\sim P_7$，再用于计算$C_{ij}$。$T(n)=7T({n\over 2})+O(n^2)$，$T(n)=O(n^{2.81})$

卷积与FFT

多项式表示

系数表示：$A(x) = \sum\limits_{i=0}^{n-1}a_{i}x^{i}$，$B(x) = \sum\limits_{i=0}^{n-1}b_{i}x^{i}$

多项式乘法(线性卷积)：$A(x)\times B(x) = \sum\limits_{i=0}^{2n-2}c_ix^i$，其中$c_i=\sum\limits_{j=0}^{i}a_jb_{i-j}$。暴力$O(n^2)$

点值表示：$A(x)=\{(x_i,y_i)|i\in[0,n-1]\}$，$B(x)=\{(x_i,z_i)|i\in[0,n-1]\}$

多项式乘法：$A(x)\times B(x) = \{(x_i,y_i\times z_i)|i\in[0,2n-1]\}$，$O(n)$但需要$2n$个点表示$A(x)$和$B(x)$

系数转点值

对于$n-1$次多项式$A$，给定系数$\{a_i\}$，输出多项式在$n$个点处的值。

我们选取$n$阶单位根$w^0,\cdots,w^{n-1}$，其中$w=e^{2\pi i/n}$，那么$(w^k)^n=(e^{2\pi i/n})^n=(e^{\pi i})^{2k} = 1$。并且有$n\over 2$阶单位根为$v^0,\cdots,v^{n/2-1}$，其中$v=w^2=e^{4\pi i/n}$。

将多项式拆成奇数次幂和偶数次幂两部分：

则有：

代入$n$阶单位根，有：

那么我们就把求长度为$n$的多项式$A$在$w^k$和$w^{k+n/2}$两处的点值的问题$O(1)$转移到了求$v^k$点处两个长度为$n\over 2$的多项式的点值。对于求$n$个单位根的问题，我们在$O(n)$时间将其拆分成了两个规模折半的问题，$T(n)=2T(n/2)+O(n)$，即$T(n)=O(n\log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
FFT(n, a0, a1, …, an-1)
{
    if (n == 1)
    	return a0
    
    (e0,e1,…,en/2-1) = FFT(n/2, a0,a2,a4,…,an-2)
    (d0,d1,…,dn/2-1) = FFT(n/2, a1,a3,a5,…,an-1)
    
    for k = 0 to n/2 - 1
    {
        ω[k] = exp(2πik/n)
        y[k] = ek + ω[k] dk
        y[k+n/2] = ek - ω[k] dk
    }
    
    return y
}

点值转系数

只需要将$w^{-1}$作为单位根的底数即可，同样是$O(n\log n)$的。

Chapter 5 - 动态规划

这个就比较灵性，考课件原题也不难，考其他的推不出来就寄，待补。

Chapter 6 - 难问题

多项式时间归约

如果问题$X$可以通过以下步骤解决，那么认为问题$X$可以多项式时间归约到问题$Y$：

  • 使用多项式数量的标准计算步骤
  • 使用多项式数量的解决问题$Y$的算法

问题$X$可以多项式时间归约到问题$Y$，记作$X\le_P Y$。

  • 如果$X\le_P Y$，且$Y$多项式可解，则$X$多项式可解
  • 如果$X\le_P Y$，且$X$多项式不可解，则$Y$多项式不可解
  • 如果$X\le_P Y$且$Y\le_P X$，记作$X\equiv_P Y$，$X$多项式可解当且仅当$Y$多项式可解

简单等价归约

独立集问题：给定图$G$和整数$k$，是否存在大小至少为$k$的点集，使得其中的每个点互不相邻？

顶点覆盖问题：给定图和整数$k$，是否存在大小不超过$k$的点集，使得所有边至少和点集中的一个点相连？

Claim. 独立集问题 $\equiv_P$ 顶点覆盖问题

Proof. 证明$S$是一个独立集当且仅当$V-S$是一个顶点覆盖。

特殊到一般的归约

集合覆盖问题：给定一个集合$U$，以及集合$U$的一系列子集的集合$S$，问是否能选出$S$中不超过$k$个成员，使得其并集等于$U$？

Claim. 顶点覆盖问题 $\le_P$ 集合覆盖问题

Proof. 对于任一顶点覆盖问题，将其边集$E$作为集合覆盖问题的全集$U$，对于每个顶点，记录与其相连的边的集合，所有顶点各自相连的边集作为$S$的成员，将顶点数量限制$k$作为集合数量限制$k$，这样就构造了一个集合覆盖问题。

利用Gadgets的归约

3-SAT：合取范式，每个子句由三个文字(分别对应一个变量)进行或运算得到，问可满足性。

Claim. 3-SAT $\le_P$ 独立集问题

Proof. 对于给定3-SAT问题，将每个变量映射到图上的两个顶点，表示$x_i$和$\overline x_i$并建边$(x_i,\overline x_i)$；对于每个子句，在其三个文字对应的变量对应的顶点间建边，得到图$G$。子句数量为$|\Phi|$，则令图$G$上所求独立集的大小设为$|\Phi|$。3-SAT有解当且仅当图$G$存在一个大小为$|\Phi|$的独立集。

由于独立集大小和子句数量一致，那么$G$中的每个三角都会有恰好一个点被选入独立集，将该点对应的变量设为真，就得到了一个3-SAT的解。

三类问题的归约

决定问题：是否存在大小不超过$k$的顶点覆盖？

搜索问题：找到一个大小不超过$k$的顶点覆盖

优化问题：找到最小的顶点覆盖

Theorem. 顶点覆盖问题 $\equiv_P$ 搜索顶点覆盖问题

Proof.

$\le_P$：决定问题是搜索问题的特例，搜索问题有解说明决定问题为真

$\ge_P$：为了找到一个大小不超过$k$的顶点覆盖：

  • 确定是否存在大小不超过$k$的顶点覆盖
  • 用$O(n)$时间找到点$v$，使得$G/\{v\}$有一个大小不超过$k-1$的顶点覆盖
  • 将$v$纳入顶点覆盖
  • 在$G/\{v\}$中递归寻找一个大小不超过$k-1$的顶点覆盖。

Theorem. 搜索顶点覆盖问题 $\equiv_P$ 最小顶点覆盖问题

Proof.

$\le_P$：搜索问题是优化问题的特例，优化问题解可作为搜索问题解

$\ge_P$：二分答案

P与NP

P：存在多项式时间算法的决定性问题的集合

NP：存在多项式时间校验器(certifier)的决定性问题的集合(非确定多项式时间)

校验器：并不直接说明问题是否有解，而是检验给定的证书(certificate)是否能说明原问题有解

证书：用于说明原问题可能有解的输入

Claim. $P⊆NP$

Proof. $\forall X\in P$，$\exists$多项式算法$A(s)$可解$X$，证书为空，校验器为$A(s)$

EXP：存在指数时间算法的决定性问题的集合

Fact. $P\ne EXP ⇒ (P\ne NP)\vee(NP\ne EXP)$

NP-Complete

P, NP, NPC

如果问题$X$可以通过以下步骤解决，那么认为问题$X$可以多项式时间(Cook)归约到问题$Y$：

  • 使用多项式数量的标准计算步骤
  • 使用多项式数量的解决问题$Y$的算法

如果对于任意问题$X$的实例$x$，我们都能构造问题$y$的实例$Y$，使得$x$有解当且仅当$y$有解，则认为问题$X$可以多项式时间(Karp)转化到问题$Y$。

NP-Complete：满足对于任意$NP$问题$X$，都有$X\le_P Y$的$NP$问题$Y$的集合

Theorem. $NP$完全问题$Y$满足$Y\in P$当且仅当$P=NP$。

Proof.

  1. 当$P=NP$时，$Y\in P$因为$Y\in NP$。
  2. 假设$Y\in P$，对于任何$X\in NP$，由于$X\le_P Y$，得到$X\in P$，即$NP⊆P$，由于$P⊆NP$，得到$P=NP$。

NP-hard：每个$NP$问题都能多项式时间归约到的问题集合。

如何证明NPC

电路可满足性问题：与或非门构成的组合电路，是否可以调整输入使输出为1？

Theorem. 电路可满足性问题是$NP$完全问题

Proof.

任何拥有定长输入，输出真/假的确定性算法可以用这样的电路表示，如果算法是多项式时间的，电路也是多项式尺寸的。

考虑$\forall X\in NP$，以及多项式时间校验器$C(s,t)$，为确定$s\in X$是否成立，只需要知道是否有一个长度为$p(|s|)$的证书$t$使得校验器输出真。

将$C(s,t)$视作一个输入长度$|s|+p(|s|)$的算法，并且将其转换为多项式尺寸的电路$K$，前$s$位固定输入为$s$，后$p(|s|)$位输入证书$t$，电路$K$可满足当且仅当$C(s,t)$输出真。

证明问题$Y$是$NP$完全问题的方法：

  1. 说明是$NP$问题
  2. 选一个$NP$完全问题$X$
  3. 证明$X\le_P Y$

Theorem. 3-SAT 是 $NP$完全问题

Proof. 已知3-SAT$\in NP$，仅需证明电路可满足性问题$\le_P$3-SAT

对于任意电路$K$，对于每个电路元素$i$创建一个3-SAT变量$x_i$

对于与或非三种运算分别构建子句：

随后将$K$硬编码的输入赋值给变量$x_i$，并将输出结点对应的变量$x_0$赋值为1。

最后，添加恒0变量来补全每个子句到三个文字，转化完成。

一些NPC问题的例子

集合覆盖，顶点覆盖，独立集，电路可满足性，SAT，3-SAT，哈密尔顿路径，哈密尔顿环路，TSP，三维匹配，三染色，子集和，背包

有很多$NP$问题要么是$P$要么是$NPC$，但也有反例： FACTOR, DISCRETE-LOG, GRAPH-ISOMORPHISM……

Theorem. 除非$P=NP$，不然就存在既不是$P$也不是$NPC$的$NP$问题。

Chapter 7 - 网络流

流量网络$G=(V,E,s,t,c)$

流和割的定义：略

Ford-Fulkerson算法

正向边容量减去流量，反向边全权值设为流量

残量网络：边集为 有剩余容量的边 和 流量非零的反向边

增广路：残量网络中$s-t$的一条简单路径，处理后每条边容量都减去瓶颈容量，反向边都加上瓶颈容量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Augment(f, c, P)
{
    b = bottleneck(P)
    foreach e ∈ P
    {
        if (e ∈ E) f(e) = f(e) + b
        else f(eR) = f(eR) - b
    }
    return f
}
Ford-Fulkerson(G, s, t, c)
{
    foreach e ∈ E: f(e) = 0
    Gf = residual network of G with respect to flow f
    
    while (there exists an augmenting path P)
    {
        f = Augment(f, c, P)
        update Gf
    }
    return f
}

时间复杂度$O(mnC)$，因为每次增广至少提升一个流量，找到一个增广路需要$O(m)$时间。由于和容量相关，FF算法对于输入规模而言并不是多项式的。

输入规模：$m,n,\log C$，算法可能需要进行$2C$次迭代。

最大流与最小割

流量引理

$f$是任意流，$(A,B)$是任意割，那么流的大小等于割之间的流的合成量

弱对偶性

$f$是任意流，$(A,B)$是任意割，那么流的大小至多是割的容量

最优性的推论

$f$是任意流，$(A,B)$是任意割，如果$v(f)=c(A,B)$，那么它们分别是最大流和最小割。

  1. 存在一个割$(A,B)$使得$v(f)=c(A,B)$
  2. $f$是最大流
  3. 对于$f$，没有增广路

1→2：弱对偶性的推论

2→3：逆否命题：如果对于$f$有增广路，那么可以增加$f$，所以$f$不是最大流

3→1：$f$没有增广路，$A$是残量网络中$s$可以到达的点的集合，因此$s\in A$而$t\notin A$

Capacity-Scaling算法

设置一个阈值$\Delta$，初始值为$2^{\lfloor\log C\rfloor}$，每次只考虑瓶颈容量在$\Delta$以上的增广路，随后将$\Delta$折半直到为0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Capacity-Scaling(G, s, t, c)
{
    foreach e ∈ E: f(e) = 0
    Δ = largest power of 2 ≤ C
    Gf = residual network with respect to flow f
    
    while (Δ ≥ 1)
    {
        Gf(Δ) = Δ-residual network of G with respect to flow f
        while (there exists an augmenting path P in Gf(Δ))
        {
            f = Augment(f, c, P)
            update Gf(Δ)
        }
        Δ = Δ / 2
    }
    return f
}

Lemma. 外层循环$1+\lfloor\log_2C\rfloor$次终止

Lemma. $f$是每次$\Delta$缩减循环后的流，最大流的值不会超过$v(f)+m\Delta$

Lemma. 每次缩减循环中，至多有$2m$条增广路

因此该算法时间复杂度$O(m^2\log C)$

Edmonds-Karp 算法

利用BFS找边数最少的增广路

1
2
3
4
5
6
7
8
9
10
11
12
13
Edmonds-Karp(G, s, t, c)
{
    foreach e ∈ E: f(e) = 0
    Gf = residual network of G with respect to flow f
    
    while (there exists an augmenting path P in Gf)
    {
        P = Breath-First-Search(Gf)
        f = Augment(f, c, P)
        update Gf
    }
    return f
}

Lemma. 最短增广路的长度不会减少

Lemma. 至多$m$次最短路增广后，最短增广路的长度严格上升

找最短增广路$O(m)$，至多有$n-1$种不同的长度，对每种长度至多增广$m$次。因此该算法时间复杂度$O(m^2n)$

Dinitz’s 算法

  • 建立分层图$L_G$
  • 从$s$开始在$L_G$中搜索，直到卡住或者到达$t$
  • 如果到达$t$，增广，更新分层图，从$s$再开始
  • 如果卡住，那就从分层图中删除该结点，跳回到上个结点重来
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
Dinitz-Normal-Phase(Gf, s, t)
{
    LG = level graph of Gf
    P = empty path
    Advance(s)
}

Advance(v)
{
    if (v = t)
        f = Augment(f, c, P)
        remove bottleneck edges from LG
        P = empty path
        Advance(s)
    if (there exists (v, w) ∈ LG)
        add edge (v, w) to P
        Advance(w)
        Retreat(v)
}

Retreat(v)
{
    if (v = s) return
    else
        delete v and incident edges from LG
        remove last edge (u, v) from P
        Advance(u)
}

Dinitz(G, s, t, c)
{
    foreach e ∈ E: f(e) = 0
    Gf = residual network of G with respect to flow f
    
    while (there exists an augmenting path P in Gf)
    {
    	Dinitz-Normal-Phase(Gf, s, t)
    }
    return f
}

每个阶段初始化需要$O(m)$的BFS；增广至多$m$次，耗时$O(mn)$；回溯至多$n$次，耗时$O(m+n)$；至多$mn$次前进，耗时$O(mn)$。

每个阶段耗时$O(mn)$，至多有$n-1$个阶段，因此该算法时间复杂度$O(mn^2)$

二分图匹配

原图所有边容量设为$\infty$，将二分图的一方用容量为1的边全部连接到源点，另一方用容量为1的连到汇点得到图$G’$，$G’$的最大流就是最大匹配数。

赫尔婚姻定理：二分图$G$两点集$L,R$大小相同。$G$有完美匹配当且仅当对于所有$L$的子集$S$都有$|N(S)|\ge|S|$。

不相交路径

两条不共用任何边的路径是不相交路径。

设置每条边容量为1，也就是最多只能被一条增广路通过，最大流就是不相交的路径数量，但并不一定是简单路径。

$s-t$割：每条$s-t$路径都用到了其中的至少一条边

Menger定理：最大的$s-t$不相交路径数等于最小$s-t$割所包含的边数。

如果是求无向图上的不相交路径数，那就每条无向边建两条有向边代替即可。

多源多汇

把一个超级源点用$\infty$容量的边连到所有源点上，汇点同理。

供需网络

图$G$中，边有容量，点有需求/产出，在circulation中为每条边赋流量，使得每个点的入流量与出流量的差值为需求/产出。

在图$G’$中，把超级源点用产出值为容量的边连到所有产出的点上，需求点同理。图$G$有一个circulation当且仅当图$G’$最大流为所有需求的和。

图$G$不存在circulation，当且仅当图的一个点分割$(A,B)$中，$A$到$B$的容量和小于$B$中点的合需求量。

如果有下限要求，那一开始就把供方需求+2，接收方需求-2，再拆成两条边建，权值分别为(下限)和(上限与下限的差)

调查设计

从超级源点到受访者建边，容量上下限是受访者可以接受的问题数量；

从产品到超级汇点建边，容量上下限是产品调查结果的需求数量；

从受访者到产品建边，容量上限为1，同一个人对同一产品只能填写一次问卷；

从超级汇点到超级源点建边，容量无限制。所有点的供需均为0。

如果找到了integer circulation，说明有可行的调查方案

航班调度

每个航班拆成两个点，两点之间建立一个容量上下限均为1的边。

源点连接每个航班的入点，源点提供$c$组乘务人员，每个航班的出点用$[0,1]$的边连接汇点，需求$c$组乘务人员。从源点到汇点连接一条$[0,c]$的边，表示闲置乘务组。

如果航班可以首尾相连，将前一班的出点连接到后一班的入点，容量为$[0,1]$。

最小化所需乘务组数量时，可以二分$c$。航班数为$k$时，时间复杂度$O(k^3\log k)$。

图像分割

看看就好，现在也不用网络流做图像分割。

相邻格点间建双向边，容量为其一为前景另一为背景的罚值；

从源点到每个点建边，容量是该点和前景的相似度；

从每个点到汇点建边，容量是该点和背景的相似度。

在这个图上跑最小割就OK。

Chapter 8 - 随机化

随机化真的是一门具有极高美学价值的艺术。

访问调度

如果同时有多个进程请求访问资源，那就都不能访问资源。两个和尚没水喝

$n$个进程，每个进程每个时刻有$1/n$概率可以访问资源，那么不存在race condition的概率随$n$增加从$1/2$收敛到$1/e$。

所有进程都能在$2en\ln n$轮中完成访问的概率至少为$1-1/n$。

全局最小割

无向图，不给源点汇点，求全局的最小割。

网络流解法：选一些源点，对其他所有点$v$求最小$s-v$割

收缩算法：随便选一条边，收缩这条边并将两个端点合并为超级顶点，删掉自环保留其他边(包含重边)，重复该过程直到只剩两个超级结点，返回此时的割。

Theorem. 收缩算法以不低于$2/n^2$的概率给出最小割的正解

为了提高正确率，多跑几遍：当运行了$n^2\ln n$次时，还找不到正解的概率不超过$1/n^2$。

实际上，全局最小割的随机算法可以达到$O(m\log^3 n)$，甚至比最大流算法还快。

最大3-SAT

Claim. 给定一个有$k$个子句的3-SAT问题，随机赋值可以满足的期望子句数是$7k/8$。

由于是期望值，所以我们总是能通过随机生成一个满足高于$7k/8$个子句的解。于是我们持续随机，直到找到一个满足不低于$7k/8$个子句的解。

已被证明：除非$P=NP$，否则没有比$7/8-$渐进更高的随机渐进算法了。

蒙特卡洛与拉斯维加斯

蒙特卡洛：能在多项式时间内跑完，但不一定给出正确结果

e.g. 全局最小割

拉斯维加斯：能保证给出正确结果，但不一定能在多项式时间内跑完

e.g. 随机快排，最大3-SAT算法

负载均衡

中心化控制：Round-Robin给每个处理器均衡安排任务

分布式控制：每个任务都以一定概率随机给任何处理器

问题：有多大概率某个处理器过载了？

利用切诺夫界和布尔边界等工具分析，没有处理器接受超过$\Theta(\log n/\log \log n)$个任务的概率不低于$1-1/n$。

(切诺夫界示意图，从图片搜索引擎拿的，我也不知道对不对)

如果总任务数$m=16n\ln n$，那么每个处理器的负载在一半到两倍平均值的概率不低于$1-2/n$。

不知道处理器会不会过载，反正我写到这里已经过载了