Joyce' Blog
0%

算法复习笔记（五）

发表于 更新于

网络流

最大流问题

容量、源点、汇点、流；流f满足容量条件和守恒定理

在边上用剩余的容量向前推（前向边，c(e)-f(e)）， 并且在已经有流的边上向后推（后向边，f(e)，可撤销的容量）， 使它转向一个不同的方向。

剩余图: $G_f$= (V, $E_f$). 具有正的剩余容量的剩余边。$ E_f$= {e} ∪{$e^R$}.

令P是$G_f$中一条简单的s-t路径（增广路径）。bottleneck(P,f)是P上任何边关于流f的最小剩余容量。算法augment(f,P)在G中产生一 个新的流f’.不断调整Gf来获取更大的流量.

1
2
3
4
5
6
Augment(f, P) { 
    b ←bottleneck(P) 
    foreach e ∈P { //宽度优先或者广度优先搜索，代价为 O(m+n)=O(m); 
        if(e ∈E) f(e) ←f(e) + b 
        else f(eR) ←f(e) -b } 
    return f }
1
2
3
4
5
6
7
8
9
Ford-Fulkerson(G,s,t,c){
    foreach e ∈E f(e)←0
    Gf ← residual graph
    while(there exists augmenting path P){
        f ← Augment(f,c,P)
        update Gf
    }
    return f
}

Ford-Fulkerson算法可以在 O(mC)时间内实现

最大流与最小割

v(f)≤c(A,B)，每个流的值是以每个割的容量为上界的。证明：流f的值=A的出度-A的入度≤A的出度=割(A,B)的容量

最大流的值等于最小割

选择好的增广路径

选择了一条瓶颈容量很小的增广路径， 导致收敛很慢！— 选择具有大的瓶颈容量的路径，进展会更大些

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Scaling-Max-Flow(G, s, t, c) { 
    foreach e ∈E  f(e) ←0 
    ∆←largest power of 2 <= Max of Ce out of s 
    Gf←residual graph
	while(∆≥1) { // 外层While循环的迭代次数至多是 1 + ⎡log2 C⎤ 
        Gf(∆)←∆-residual graph 
        while(there exists augmenting path P in Gf(∆)) { 
            //在∆缩放阶段，每次增广增加的流值至少是∆.
            //在一个缩放阶段增广次数至多是2m
            f ←augment(f, c, P) //一次增广用O(m)时间(包括建立图，找到合适路径)
            update Gf(∆) 
        } 
        ∆←∆/ 2 
    } 
    return f
}

二分匹配问题

构造最大流

构造图G’ = (L ∪R∪{s, t}, E’ ). 连接原图L到R的每条边, 每条边赋予单位容 量；增加一个源点s, 从s到L中的每个结点连接一 条边，每条边赋予单位容量；增加一个终点t, 从R中的每个结点到t连接一 条边，每条边赋予单位容量。

G中最大匹配的数目与所定义的G‘中最大流值相同.

令n=|L|=|R|,m是G的边数，一般假定初始问题中每个结点至少存在一条关联边， 因此m>=n/2.

时间复杂度：C=|L|=n,根据以前O(mC)的界——Ford-Fulkerson算法在 O(mn)时间内找到二部图中的一个最大匹配

NP与计算的难解性

贪心算法 区间调度 O(nlogn)
分治策略 FFT O(nlogn)
动态规划 编辑距离 O(n^2)

多项式时间规约

如果对于问题Y：能用多项式个标准的计算步骤，加上多项式次调用解问题X的黑盒子来解问题Y，则：Y多项式时间可归约到X，或X至少想Y一样难（相对于多项式时间）

$Y≤_pX$ （有传递性）

如果X能在多项式时间内求解，则Y也能在多项式时间内求解；如果Y能在多项式时间内求解，则X也能在多项式时间内求解。

独立集问题

G=(V,E)，G包含大小至少为k的独立集吗？G包含大小至多为k的顶点覆盖吗？

S是一个独立集当且仅当它的补图V-S是一个顶点覆盖。

集合覆盖：比顶点覆盖更具一般性，顶点覆盖$≤_p$集合覆盖

使用零件归约

合取范式，可满足性问题SAT，3-SAT：三元可满足性

3-SAT$≤_p$独立集

构造：连接一个三角形的三个顶点（需要同时考虑三个三角形，从三个三角形中各取一个点），并把每个项与它的否定项连接起来。

3-SAT$≤_p$独立集$≤_p$顶点覆盖$≤_p$集合覆盖

寻找问题$≤_p$判别问题

有效证书和NP的定义

对于判定问题： A解问题X

存在多项式时间解法的问题的集合P

判断素性：用2到根号N来判断N是否能被这些数整除，算法的时间复杂度是指数级别的；AKS算法为多项式级别。

证书串t包含s是X的“yes”实例的证据。

存在t使得：|t|≤p(|s|)且B(s,t)=yes，则B是问题X的有效验证程序，t是证书。

NP是所有存在有效验证程序的问题的集合

例

独立集问题：

证书：至少有k个顶点的集合；验证程序B：核实这些顶点中的任何两两之间没有边连接。

NP完全问题

电路可满足性

NP问题要么是P，要么是NP完全问题

难问题的部分分类：

  1. 包装问题：独立集、集合包装
  2. 覆盖问题：顶点覆盖、集合覆盖
  3. 划分问题：三维匹配、图着色
  4. 排序问题：哈密顿图、哈密顿回路、巡回售货员问题
  5. 数值问题：子集和，带开放时间和截止时间的调度问题
  6. 约束满足问题：SAT，3SAT

1559907526582