DP广泛用于求解组合最优化问题。动态规划(Dynamic Tabling)不是递归调用自身，但是问题的基础解通常以递归函数的形式予以说明的。递归是自顶向下，动态规划是自底向上。

• 用来引出递归和归纳的最常见的例子是 斐波那契数列问题

每一个数都是前两个数的和

1
2
3

procedure f(n)
	if(n==1) or (n==2): return 1
	else: return f(n-1) + f(n-2)

但是如果自底向上明显能够在n的时间和常数空间

• 另一个类似的例子是二项式系数 $$(_k^n) = (_{k-1}^{n-1}) + (_k^{n-1})$$ 如果自顶向下需要的时间复杂度为指数时间复杂度 $O(2^n)$,但是通过构造帕斯卡三角形，能够很快地计算出来。

7.2 LCS 最长公共子序列

在字母表Σ上，分别给出两个长度为m和n的字符串A 和 B，确定在A和B中最长公共子序列的长度。A=”a1a2…Am” B=’b1b2..bn’

为了使用动态规划技术，我们首先寻找一个最长公共子序列长度的递推公式

L[i, j] = L[i-1, j-1] + 1 if ai==bj

L[i,j] = max{L[i-1, j], L[i, j-1]} if ai!=bj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

algorithm 7.1 LCS
inputs: A, B (n, m)
outputs: A B的LCS的长度

for i = 0->n:
	L[i, 0] = 0
for j = 0->m:
	L[0, j] = 0
for i = 1->n:
	for j = 1 -> m:
		if ai == bj:
			L[i, j] = L[i-1, j-1] + 1
		else:
			L[i, j] = max(L[i-1, j], L[i, j-1])
return L[n, m]

如何输出 最长公共子序列？

最长公共子序列可能是有多种长度相同的子序列！！！，如何找出所有的子序列。一个子序列也可能以不同的下标序列出现！

如何找出所有的LCSs?

Side Notes

在DP问题中，也可以利用递归的形式达到DP的时间复杂度。这种递归使用了一张备忘录以记录已被计算过的情况，以避免重叠case的重复调用，因此被称为带备忘录的递归。 —-《算法导论》

贪心算法也用于求解最优化问题，不同的是贪心算法通常包含一个寻找局部最优解的迭代过程，在某些实例中 这些局部最优解转变为了全局最优解。而在另外的一些情况下，则无法转变为全局最优解。贪心算法在少量计算的基础上做出正确猜想而不急于考虑以后的情况，这样一步一步来构筑解，每一步均是建立在局部最优解的基础之上，每一步又扩大了部分解的规模。

设计贪心算法的困难部分就是要证明该算法确实求解了它所要解决的问题，而与之相比 递归算法拥有十分简单的归纳证明。考虑一下证明以下几个问题的难度，1）单源最短路径 2）最小耗费生成树 3）Huffman编码。

图中 G(V, E) 单源最短路径(迪杰斯特拉)

1
2
3
4
5
6
7
8
9
10
11
12

dijkstra alg
U = {v} # U是已经寻找到最短路径的节点 
S = V - {v} # 待寻找的节点
D 一个从源点到其他节点的最短距离
while S 不为空:
	从S中选择一个距离最小的节点 u
	U = U ∪ {u}
	S = S - {u}
	for u所有邻边 (u, w):
		if w∈S and D[u]+length(u, w) < D[w]:
			D[w] = D[u] + length(u, w)
return D

maximum v.s maximal matching

maximal matching: 极大匹配？

maximum match: (also known as maximum-cardinality matching)最大匹配是要找出一个E的子集M，它具有最大数量的不交叠边，即在M中任何两条边没有一个共同顶点。

交替路径：一条由匹配边和未匹配边交替组成的简单路径。

交替路径被称为增广路径，当p中所有的匹配边都在M中并且端点是自由的。

问题定义

寻找二分图的最小顶点覆盖算法：Kőnig’s theorem)

Let’s say you have G = (V, E) a bipartite graph, separated between X and Y.

As you said, first you have to find a maximum matching (which can be achieved with Dinic’s algorithmfor instance). Let’s call M this maximum matching.

Then to construct your minimum vertex cover顶点覆盖:

• Find U the set (possibly empty) of unmatched vertices in X, ie. not connected to any edge in M
• Build Z the set or vertices either in U, or connected to U by alternating paths (paths that alternate between edges of M and edges not in M) 通过交替路径与U中顶点相连。
• Then K = (X \ Z) U (Y ∩ Z) is your minimum vertex cover

二分图和一般图的匹配算法研究

• 交替路径树：每一条从根节点到叶子节点的路径均为交替路径

• 匈牙利树：从自由顶点r开始生长交替路径树，如果树被阻塞，则该被阻塞的树为匈牙利树。

  从自由顶点r开始，加上每一条连接r和y顶点y的未匹配边(r, y)。对于y，如果有匹配边(y, z)存在，则将其加入T。重复此过程直到遇到自由的y顶点或被阻塞。

二分图

二分图：不含奇数长度的回路。

1. 网络流方法

2. 匈牙利树方法

   1. 无向图G的一个匹配M是最大的，当且仅当G不包含关于M的增广路径。
   2. M为一个匹配，p是关于M的一条增广路径，则M+p可以构造一个更大的匹配。

   (匈牙利树的方法利用了匹配的特定性质，这个性质可以帮助我们解决扩大匹配这个问题)

1
2
3
4
5
6
7
8
9
10

BiMatch2
Input: 二分图 G = (X ∪ Y, E)
Output: G中最大匹配M
初始化M为任意匹配（可能为空）
while存在自由顶点x和自由y顶点
	设r为一个自由x顶点，采用广度优先搜索，生成一棵以r为根的交替路径树T
	if T为匈牙利树： 
		let G <- G - T
	else:
		在T中找到一条增广路径p，并设M = M + p

• 算法的时间复杂度？构造交替树$O(m)$，最多构造$O(n)$棵树 => $O(nm) = O(n^3)$
• 为什么匈牙利树可被移除而不影响搜索匹配过程？
  • 匈牙利树中无顶点能在增广路径中出现
    • 如果($x, y)$为一条边，使得$x$在$T$中而$y$不在$T$中，那么$x$肯定被标记为内部
  • 交替路径不经过$T$
    • 如果经过$T$，则必然以内部顶点进入、内部顶点穿出，矛盾。

一般图

1. 匈牙利树

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

GMATCH
Input: undirected graph G(V, E)
Output: maximum match M of G

M = {}
maximum = false
while not maximum
	确定与M相关的自由顶点集Ｆ
	augment = false
	while F ≠ {} and not augment
		清空栈、未标记边，从顶点删除标记
		设x为下一个顶点； F = F - {x}; T = x
		标记x为外部的 {初始化交替路径树}
		
		hungarian = false
		while not augment:
			选择一个外部顶点x和一条未标记的边(x, y)
			if (x, y)存在： 标记(x, y)
			else:
				hungarian = true
				break
			if y是内部的: doNothing {找到偶数长的回路}
			elif y是外部的: {找到花}
				将花放到栈顶，收缩花
				用顶点w替换花，标记w是外部的
				如果花包含根，则标记w是自由的
			elif y是自由的：
				augment = true
				F = F - {y}
			else:
				设(y, z)在M中，将(x, y) 和(y, z)加入T中
				标记y是内部的，z为外部的
			
			if hungarian: 从G中移除T
			elif augment:
				构造增广路径:从栈中弹出花，展开它们，增加偶数长部分
				用p增广G
	if not augment:
		maximum = true

外层while循环寻找最大匹配，每一次迭代，增广路径被发现并由这条路径匹配扩展集

中层while循环对所有的自由顶点循环，直到发现增广路径为止。

每次迭代中选取一个自由顶点左右交替路径树的根，从这个根出发在内层循环中对图探查，内循环的功能是每次加两条边增长交替路径树。每次迭代中，它取任意一个外部顶点x和相应的边(x,y)，如果这样的边存在，有以下几种情况：

1. y是内部的
2. y是外部的
3. y被标记为自由的
4. 其他情况下

图中各边都有一个容量，在图G中从源点s开始到汇点t的流的最大值就是最大流问题。

预备知识

图G上的流是一个顶点对上的实函数f，具有以下4个条件。

1. 斜对称。
2. 容量约束
3. 流守恒
4. f(v, v) = 0

定义：一个割{S, T}是把顶点集分成两个子集S T的一个划分，使得$s\in S, t\in T$。割的容量c(S, T) 定义为

图的存储方式(邻接矩阵 & 邻接表)

1. 邻接矩阵

   顶点间的关系存储在一个$n*n$矩阵M中。若u, v 两个顶点有边，对于无向图有权图，则M[u, v] = M[v, u] = weight[u, v]，对于有向图则有 M[u, v] = weight[u, v]

2. 邻接表

   图的顶点存储在一个线性表中，每个顶点的邻接边都以链表的形式依附在线性表该顶点上。对于有向图，需要θ(n+m)的空间，对于无向图，需要θ(n+2m)的空间。

• Dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14

Dijkstra Algorithm: 单源最短路径
Input	含权有向图G=(V, E), V={1, 2,..., n}
Output	G中顶点1到其他顶点的距离
1    X = {1}, Y = V - {1}； λ[1] = 1
2    for y = 2->n:
3        if y 与 1 相邻: λ[y] = length[1, y]
4        else: λ[y] = +inf
5    for j = 1 -> n-1:
6    	y = argmin(λ[y])  (y∈Y)
7    	X = X ∪ {y}
8    	Y = Y - {y}
9    	for y邻近的每条边 (y, w):
10    		if w ∈ Y and λ[y] + length[y, w] < λ[w]:
11    			λ[w] = λ[y] + length[y, w]

可以看到，在第6步，选择Y集合中离X集合最近的点需要O(n)的时间，总共需要循环n-1次。对于邻接表存储形式，第9步在整个算法执行过程中需要θ(m)次。算法总时间复杂度为$O(n^2 + m)$.

==对于具有非负权的有向图G和一个源点s，算法Dijkstra在$O(n^2)$的时间内找到s到图中所有顶点的最短距离。==

贪心算法一章通过把Y集合构建为最小堆进而把时间复杂度减少到O(mlgn)，对于稠图，时间复杂度为O(m)。

图的遍历(DFS/BFS)

对于邻接表存储的形式

1. DFS 时间复杂度为O(m)
2. BFS 时间复杂度为O(m)

Ford-Fulkerson 福特弗克森方法

福特福克森方法每次选择一条增广路径，并用该增广路径的瓶颈容量来扩大网络流。add some introduction to residence graph(R)

1
2
3
4
5
6
7
8
9
10
11
12
13
14

Alg 161 Ford-Fulkerson
Input 	网络(G, s, t, c)
Output: G 中的一个流
    初始化剩余图 R = G
    for (u, v) 属于 E
        f(u, v) = 0
    end for
    while 在R中有一条增广路径 p = s,.., t:
        设Δ为p的瓶颈容量
        for p 中的每条边(u, v):
            f(u, v) = f(u, v) + Δ
        end for
        更新剩余图R
    end while

最大容量增值 (MCA)

最大容量增值 在福特福克森方法的基础上，每次扩大网络流时选择容量最大的一条增广路径进行增值。

最短路径长度增值 (MPLA)

层次图：给定有向图 G(V, E)，它的层次图L (V, E’), E’={(u, v) | level(v) = level(u) + 1}。level(v)是顶点v的层次，即从s到v的路径中边的最小数。

算法从零网络流开始，初始化剩余图R为原图。然后逐阶段增大网络流，每个阶段分成两个步骤

1. 根据剩余图R计算层次图，如果ｔ不在层次图中则终止，否则继续
2. 只要在层次图L中有从ｓ到ｔ的路径ｐ，就用ｐ的瓶颈容量对路径ｐ进行增值。修改层次图L和剩余图R（删除饱和边以及增加某些边）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

1  Alg 最小路径长度增值 MPLA
2  Input	(G, s, t, c)
3  Output	G的最大流
4      for (u, v) in E:
5          f(u, v) = 0
6      end for
7      初始化剩余图，R=G
8      查找R的层次图L
9      while t in L:
10         while 在L中t可以从s到达:
11             let p=L中s->t的一条路径
12             设Δ为p的瓶颈容量
13             用Δ增值当前流
14             沿着路径p更新L和R
15         end while
16         用剩余图R计算新的层次图L
17     end while

更新L：移除饱和边，非饱和边的容量减少？
更新剩余图R：移除饱和边，非饱和边的容量减少，可能还要增加逆向边？

时间复杂度分析：每个阶段计算的层次图路径长度都比前个阶段层次图中路径长度长，因此最多有n个阶段。每个阶段构造层次图需要m的时间(line16)，同时在每个阶段可能最多需要进行m次增值，而每次增值寻找最短增广路径需要m的时间(line10-15)。因此，时间复杂度为$O(nm + nm^2)$

最小路径长度增值(MLPA) 算法能够在$O(nm^2)$内找到有向图的最大流

Dinic阻塞流算法

Dinic算法把时间复杂度进一步减小为$O(n^2m)$，在MPLA中，计算层次图后增广路径逐条找出，而Dinic更加高效地找出所有的增广路径，这也是改进运行时间的原因所在。

阻塞流：设G为一个网络，H是包含s和t的G的子图。H中的流f成为关于H的阻塞流，如果在H中每一条从s到t的路径中都至少有一条边饱和。

Dinic算法和前一个算法一样，算法整个流程被分为最多n个阶段，每个阶段由寻找层次图和关于此层次图阻塞流以及用阻塞流来增大网络流组成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Alg Dinic 阻塞流算法
Input	(G, s, t, c)
Output	G的最大流
for (u, v) ∈ E:
	f(u, v) = 0
初始化剩余图 R = G
搜索层次图 L
while t 为 L中的顶点:
	 u = s
	 p = u
	 while outdegree(s) > 0 and u != t:
	 	while u != t and outdegree(s) > 0：# 前进搜索出一条增广路径
	 		if outdegree(u) > 0:
	 			suppose (u,v)为L中一条边
	 			p = p, v
	 			u = v
	 		else:
	 			删除L中 u 的邻接边
	 			删除p最末尾顶点u，且令p的倒数第二个节点为u
	 	if u == t:  
	 		假设p的瓶颈容量为Δ，沿着p推送一个Δ的流。
	 		修改层次图和剩余图
	 		把u置为修改层次图后s在路径p上能达到的最后一个顶点，注意u可能是s
	 计算新的层次图（根据剩余图）

最外层的循环对应于n-2个层次图（阶段），每个阶段内通过深度优先的方式来寻找增广路径。每寻找到一条增广路径 （语句if u == t）就用路径p的瓶颈容量进行增值。

它的时间复杂性分析如下，n-2个外层循环，每个外层循环内要深度优先遍历整张图并附带删除顶点和边 (m + n)。对于每一条增广路径增值的时间为 n (即沿着路径p推流，修改层次图和剩余图)，最多有m跳增广路径，时间为(nm)。故总的时间复杂性为$O(n^2m)$

阻塞流(Dinic) 算法能够在$O(n^2m)$内找到有向图的最大流

MPM算法

MPM算法相比于Dinic算法寻找到了一个更快的寻找阻塞流的算法$O(n^2)$

顶点v的通过量（throughput），为引入边的总容量和引出边的总容量两者中的小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

Algorithm MPM
Input	(G, s, t, c)
Output	G的最大流
    for (u, v) ∈ E:
        f(u, v) = 0
    初始化剩余图 R = G 
    查找剩余图R的层次图L
    while t 为 L中的层次图顶点:
        while t 在L中从s能到达:
            查找最小通过量的顶点v(设其对应值为g)
            从v到t推下g个单元流
            从s到v拉入g个单元流
            更新 f, L, R
        使用剩余图R计算新的层次图L

Maxflow Applications

Please refer to this lecture note: https://courses.engr.illinois.edu/cs473/sp2010/notes/17-maxflowapps.pdf

Python Implementation

NetworkX库实现了有关的算法。

随机算法在接受输入的同时还接收一串随机的比特流，并且在运行的过程中使用该比特流。随机算法有两个优点1）相比于我们已知的解决同一问题最好的确定性算法，随机算法的运行时间或空间通常小一些。2）非常易于理解和实现 。

Las Vegas vs Monte Carlo 算法

Las Vegas 算法要么给出正确的解，要么就没有解。与之相反，Monte Carlo算法总是给出解，但是可能是错的。这个是非常容易理解的，Monte Carlo也是一种采样方式的名字，在采样时，它很可能给出正确的采样点，但是也不排除是错的。

随机化快排

快排的期望运行时间非常好 $θ(n)$，基于比较的排序算法的最好时间复杂度。但是快排对它的最坏时间复杂性没有做任何保证，可能到达$θ(n^2)$ 。划分主元的选择使得每次都把n的数组分为1 和n -1两个序列。通过随机选择主元可以使得这种情况发生地概率变得很小。

1
2
3
4
5
6
7
8
9
10
11
12

Alg 14.1 RandomQS
Inputs: A[1...n]
Outputs: sorted A
	rquicksort(A, 1, n)

process rquicksort(A, low, high)
    if low < high:
        v = random(low, high)  #!!! 随机化快排引入了随机性
        swap(low, v)
        w = split(A, low, high) # W是主元的位置
        rquicksort(A, low, w-1)
        rquicksort(A, w+1, high)

随机化选择算法 select

选择数组中第k大或者中项元素。6.5以及证明了算法的运行时间是$θ(n)$ ,但它具有一个很大的常系数，使它对于中小等实例不具有可行性。下面介绍一个Las Vegas算法，它的期望运行时间是一个带有很小常系数的$θ(n)$，但在最坏的情况下它的运行时间也会蜕化至$θ(n^2)$ ,但是这与输入实例本身无关，而是随机数生成器恰巧选择了一个不切实际的序列，它的概率非常小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

alg RandomizedSelect
inputs: A, k
outputs: 数组A中第k小元素
1.	rselect(A, 1, n, k)

过程 rselect(A, low, high, k)
    v = random(low, high)
    x = A[v]
    把数组A分成三个数组 
        A1 = {a| a<x}
        A2 = {a| a=x}
        A3 = {a| a>x}
    case
        |A1| >=k: return rselect(A, 1, |A1|, k)
        |A1| + |A2| >= k: return x
        |A1| + |A2| < k : return rselect(A3, 1, |A3|, k - |A1| - |A2| )

For input with size n, RandomizedSelect alg’s expected comparison time is smaller than 4n.

测试串相等

模式匹配

随机采样

从n个元素中随机选择m个元素 (m<n)。假设n个元素为1…n的正整数。存在一个运行时间为$θ(n)$的简单Las Vegas 算法。即随机从n个元素中选择一个元素，若没有被选择就加入到选择元素集合中，若如果被选择了就重新随机选择一个元素。

1
2
3
4
5
6
7
8
9
10
11
12
13

alg 14.5 RandomSampling
inputs m, n (m<n)
outputs {1...n}中选择的m个元素
    for i =1:n
        S[i] = False # S 为一个表示元素是否被选择的bool数组
    k = 0
    while k < m:
        r = random(1, n)
        if not S[r]:
            k += 1
            A[k] = r
            S[r] = True
    return A

可以证明它的期望运行时间为$θ(n)$。

Prim Number Test 素数性测试

显而易见的方式使用[1, n^0.5]之间的各个数除n以测试能否被整除，这样导致了关于输入大小的指数时间复杂性 (如何理解？)。这种解法中通过寻找证据来证明是合数。

费马小定理：如果n是素数，那么对于满足条件1的a， 必然有条件2满足.