算法设计与优化

广度优先搜索

1.注意事项：infinity表示无穷大，emptySet表示空集，NIL表示空，u.color表示结点s的颜色，u.d表示结点s相对于起点的距离，u.pi表示结点s的前驱结点

2.伪代码

BFS(G, s)
for each vertex u in (G.V-{s})
	u.color = WHITE
	u.d = infinity
	u.pi = NIL
s.color = GRAY
s.d = 0
s.pi = NIL
Q = emptySet
ENQUEUE(Q, s)
while Q != emptySet
	u = DEQUEUE(Q)
	for each v in G.Adj[u]
		if v.color == WHITE
			v.color = GRAY
			v.d = u.d + 1
			v.pi = u
			ENQUEUE(Q, v)
	u.color = BLACK 

3.时间复杂度

每个结点及其边都进行扫描且只扫描一次，因此为theta(|V|+|E|)
注：BFS算法生成的树是一棵最短路径树（shortest path tree）

深度优先搜索

1.注意事项：u.d表示结点u刚被发现的时间，u.f表示结点u处理完的时间

2.伪代码

DFS(G)
for each vertex u in G.V
	u.color = WHITE
	u.pi = NIL
time = 0
for each vertex u in G.V
	if u.color == WHITE 
		DFS-VISITE(G, u)

DFS-VISITE(G, u)
time = time + 1
u.d = time
u.color = GRAY
for each vertex v in G:Adj[u]
	if v.color == WHITE
		v.pi = u
		DFS-VISITE(G, v)
u.color = BLACK
time = time + 1
u.f = time

3.时间复杂度

DFS中的初始化theta(|V|)和对每个白色结点进行算法theta(|V|)，DFS-VISITE中遍历结点的相邻的边为theta(|adj[u]|)，所有的边总和为theta(|E|)，因此总时间复杂度为theta(|V|+|E|)

4.定理、引理和推论证明

（1）定理：括号化定理：在对有向或无向图G = (V, E)进行的任意深度优先搜索中，对于任意两个结点u和v来说，下面三种情况只有一种成立
区间[u.d, u.f]和区间[v.d, v.f]完全分离，在深度优先森林中，结点u不是结点v的后代，结点v也不是结点u的后代
区间[u.d, u.f]完全包含在区间[v.d, v.f]内，在深度优先森林中，结点u是结点v的后代
区间[v.d, v.f]完全包含在区间[u.d, u.f]内，在深度优先森林中，结点v是结点u的后代
证明：根据祖孙和后代之间的关系以及时间来分析

（2）推论：后代区间的嵌套：在有向或无向图G的深度优先森林中，结点v是结点u的真后代当且仅当u.d < v.d < v.f < u.f
证明：由上述括号化定理易证

（3）定理：白色路径定理：在有向或无向图G = (V, E)的深度优先森林中，结点v是结点u的后代当且仅当在发现结点u的时间u.d，存在一条从结点u到结点v的全部由白色结点所构成的路径
证明：
=>：如果v是u的后代，且从u到v只有1个点，即u等于v，那么显然成立。如果v是u的真后代，那么根据后代区间的嵌套推论有u.d < v.d，即在发现u时，v还没发现，此时v是白色的，而且v可以是任意后代，因此从u到v路径上的每个后代都是白色的，即存在一条白色路径。
<=：存在从u到v是一条白色路径，此时是在u刚被发现时的情况。那么，u.d < v.d。而此时u.f或在u.d和v.d之间或在v.d之后，u和v之间存在路径说明u和v存在祖先后代的关系，根据括号化定理，v.f在v.d和u.f之间，此时满足后代区间嵌套的推论，即v是u的后代。

（4）定理：在对无向图G进行深度优先搜索时，每条边要么是树边，要么是后向边
证明：假定任意一条边(u, v)，有u.d < v.d，那么如果在扫描u的邻接结点时发现了v即(u, v)，那么(u, v)是树边，如果在扫描v的邻接结点时发现的u即(u, v)，那么(u, v)是后向边。

拓扑排序

1.注意事项：算法对象有向无环图

2.伪代码

TOPOLOGICAL-SORT(G)
（1）call DFS(G) to compute finishing times f[v] for each vertex v
（2）as each vertex is finished, insert it onto the front of a linked list
（3）return the linked list of vertices

3.时间复杂度
调用DFS为theta(|V|+|E|)，生成链表为theta(|V|)，返回链表为theta(1)
总共为theta(|V|+|E|)

4.定理、引理和推论证明

（1）引理：一个有向图G=(V, E)是无环的当且仅当对其进行的深度优先搜索不产生后向边
证明：
=>：假设有向图无环并产生了一条后向边(u, v)，那么v是u的祖先，此时v是灰色的，根据白色路径定理，当发现v时，有一条从v到u的白色路径，因此出现了一个环路。矛盾，假设不成立。
<=：假设不含后向边的图G含有环路，环路中有两个点u和v，假设v是第一个发现的，即v.d<u.d根据白色路径定理，在发现v时，环路中的点都是白色的，因此从v到u存在一条白色路径，因此u是v的后代。因为u和v在环路中，因此有一条从u指向v的边，且是后代指向祖先的后向边。矛盾，假设不成立。

（2）定理：拓扑排序算法TOPOLOGICAL-SORT生成的是有向无环图的拓扑排序
证明：（根据拓扑排序的定义，我们只要证明图中的任意一条边(u, v)，有u.f > v.f，图中只有四种边，并且图是无环的，没有后向边，因此只需注意判断其他三种边即可）如果(u, v)是前向边，即u是v的祖先，那么u.f > v.f一定成立；如果(u, v)是树边，u是v的父亲节点，因此必有u.f > v.f；如果(u, v)是横向边，即u和v没有祖先和后代之间的关系，并且v一定已经先处理完，再发现u，因此，u.f > v.f。综上，得证。

强连通分量

1.注意事项：算法对象有向图；算法中的第二次DFS时，转置图按结束时间从大到小排序；证明中的第二个引理是根据原图而不是转置图；G.T表示图G的转置

2.伪代码

STRONGLY-CONNECTED-COMPONENTS(G) 
（1）call DFS(G) to compute finishing times u.f for each vertex u
（2）compute G.T
（3）call DFS(G.T), but in the main loop of DFS, consider the vertices in order of decreasing u.f (as computed in line 1)
（4）output the vertices of each tree in the depth-first forest formed in line 3 as a seperate strongly connected component

3.时间复杂度
两次DFS为theta(|V|+|E|)，求图的转置为theta(|V|+|E|)
总共为theta(|V|+|E|)

4.定理、引理和推论证明

（1）引理：设C和C’为有向图G = (V, E)的两个不同的强连通分量，设结点u, v 属于C，结点u’, v’ 属于C’，假定图G包含一条从结点u到结点u’的路径uu’。 那么图G不可能包含一条从结点v’到结点v的路径v’v。
证明：如果图G包含一条从结点v’到结点v的路径v’v， 则G也将包含路径u u’~ v’和v’~ v~u。因此，u和v’可以互相到达，从而与C和C’是不同的强连通分量的假设矛盾

（2）引理：设C和C’为有向图G = (V, E)的两个不同的强连通分量。假如存在一条(u, v) 属于E，这里u属于C，v属于C’，则f(C ) > f(C’)。（d(U) = min{u.d}、f(U) = max{u.f} 其中U是V的子集，u属于U）
证明：

分为两种情况考虑：a. d(C ) < d(C’) b. d(C ) > d(C’)

a.第一种情况：设x是C中第一个被发现的结点，那么d(C ) = x.d，C中其余结点在刚发现x时都是白色的，C’中的所有结点此时也是白色的，那么x就能从通过结点u和边(u, v)到达C’中。根据强连通分量的性质和白色路径定理，C和C’中的所有结点都是x的后代，那么f(C ) = x.f，因此自然有f(C ) > f(C’)

b. 第二种情况：设y是C’中第一个被发现的结点，那么f(C’) = y.f，d(C’) = y.d，由于d(C ) > d(C’)并且C’中的结点无法到达C中，因此C’中的结点一定先被处理，因此d(C ) > f(C’)，推出f(C ) > f(C’)

（3）推论：设C和C’为有向图G = (V, E)的两个不同的强连通分量，假如存在一条边(u, v) 属于E.T，这里u属于C，v属于C’，则f(C ) < f(C’)
证明：G.T中有一条从u到v的边，那么在G中这条边就是从v到u的，v属C’而u属于C，根据之前的引理，那么f(C ) < f(C’)

（4）定理：算法STRONGLY-CONNECTED COMPONENTS能够正确计算出有向图G的强连通分量
证明：（现在考虑的图是G.T，即第二次的深度优先搜索树和强连通分支对应）采用归纳假设，即第二次深度优先搜索时产生的前k棵树都是强连通分量。当k=0时，此时没有树显然成立。假定前k棵树都是强连通分量。现在考虑第(k+1)棵树，假设结点u是该树中第一个被发现的结点，且u在强连通分量C中，那么在u刚被发现时，C中所有结点都是白色的，根据白色路径定理，C中的所有结点都是结点u在搜索树中的后代，因此可以排除强连通分量的结点不在树中的情况。根据推论（设C和C’为有向图G = (V, E)的两个不同的强连通分量，假如存在一条边(u, v) 属于E.T，这里u属于C，v属于C’，则f(C ) < f(C’)）我们能知道，如果存在一条从C到达其他未发现的强连通分量C’的路径，那么f(C ) < f(C’)，而在第二次深度优先搜索中，我们访问结点的次序是按照完成时间的非递增顺序，有f(C ) > f(C’)，也就是说不可能存在从C到C’的路径，但可能存在从C到已发现的强连通分量的路径并且由于已发现的强连通分量中的结点都是黑色的，不可能对其进行访问，因此可以排除树中的结点不在强连通分量中的情况。综上，以u为结点的树恰好构成强连通分量C，证明结束。

优先级队列

优先级队列是一种使用堆的数据结构，支持高效地插入元素和找到最大元素值。
堆序：对于每个结点的值v，其结点的父结点的值w，有key(w) > key(v)
leftChild(i) = 2i，rightChild(i) = 2i + 1，parent(i) = floor(i/2)
Sift-up：将一个元素向上浮动 O(log n)

Input: An array H[1...n] and an index i between 1 and n.
Output: H[i] is moved up, if necessary, so that it is not larger than its parent.
done <- false
if z = 1 then exit {node i is the root}
repeat
	if key(H[i]) > key(H[lower(i/2)]) then interchange H[i] and H[lower(i/2)]
	else done <- true
	i <- lower(i/2)
until i = 1 or done

Sift-down：将一个元素向下浮动 O(log n)

Input: An array H[1...n] and an index i between 1 and n.
Output: H[i] is percolated down, if necessary, so that it is not smaller than its children
done <- false
if 2i > n then exit {node is a leaf}
repeat
	i <- 2i
	if i+1 <= n and key(H[i+1]) > key(H[i]) then i <- i + 1
	if key(H[lower(i/2)]) < key(H[i]) then interchange H[i] and H[lower(i/2)]
	else done <- true
	end if
until 2i > n or done

MakeHeap(n)：建立一个含有n个元素的堆O(n)

Input: An array A[1...n] of n elements
Output: A[1...n] is transformed into a heap
for i <- lower(n/2) downto 1
	Sift-down(A, i)
end for

Insert(H, x)：向堆H中插入值为x的元素O(log n)

Input: A heap H[1...n] and a heap element x.
Output: A new heap H[1...n+1] with x being one of its elements.
n <- n+1 {increase the size of H}
H[n] <- x
Sift-up(H, n)

FindMax(H)：堆顶元素即为最大值O(1)

Delete(H, i)：删除指定位置的元素O(log n)

Input: A nonempty heap H[1...] and an index i between 1 and n.
Output: A new heap H[1...n-1] after H[i] is removed.
x <- H[i]; y <- H[n]
n <- n-1 {decrease the size of H}
if i = n + 1 then exit {done}
H[i] <- y
if (key(y) >= key(x)) then Sift-up(H, i)
else Sift-down(H, i)
end if

ExtractMax(H)：删除最大元素O(log n)

Input: A heap H[1...n]
Output: An element x of maximum key is returned and deleted from the heap
x <- H[1]
Delete(H, 1)
return x

贪心算法

一个算法是贪婪的，如果它建立了通过每一个小步骤的解决方案，在每一小个步骤选择一个决定，以优化一些潜在的标准。

贪心算法通常被设计来解决最优化问题，即最小化或最大化一个量。它通常由一个迭代过程组成，该过程试图找到一个局部最优解。在某些实例中，这些局部最优解转变为全局最优解。在其他实例中，它们不能给出最优解。贪心算法在很少计算的基础上做出选择，并且不关心未来。因此，它逐步构建了一个解。每一步都基于局部优化增加了部分解的规模。所做出的选择，是在保持可行性的同时产生最大的即时收益。由于每一步都由基于少量信息的少量工作组成，因此产生的算法通常是有效的。贪心算法设计中的困难部分是证明该算法确实解决了它被要求解决的问题。

迪杰斯特拉算法

注意事项：单源最短路径问题（Single-source shortest paths problem）
先看一道题

一个加权有向图G，采用下面哪个选项，在改动之后能保证最短路径不变。

• A.每条边都加上17
• B.每条边都乘以17
• C.A和B
• D.既不是A也不是B

答案是B，考虑一种情况最短路径是2条边权值分别为2和3，还有一条边是6，那么最短路径为2+3=5，如果是A那么(2+17)+(3+17) > 6+17，最短路径改变，而B选项是同时扩大，因此最短路径不变。也就是如果最短路径边数很多，那么选A，则会处于明显劣势。
“What’s the shortest way to travel from Rotterdam to Groningen? It is the algorithm for the shortest path, which I designed in about 20 minutes. One morning I was shopping in Amsterdam with my young fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path. ”— Edsger Dijsktra

在介绍迪杰斯特拉算法之前，先说一下需要用到的函数“松弛操作”中包括2个函数INITIALIZE-SINGLE-SOURCE(G, s)和RELAX(u, v, w)在第377页,松弛是唯一导致最短路径和前驱结点发生变化的操作

伪代码：

DIJKSTRA(G, w, s)
INITIALIZE-SINGLE-SOURCE(G, s)
S = emptySet
Q = G.V
while Q != emptySet
	u = EXTRACT-MIN(Q)
	S = S union {u}
	for each vertex in G.Adj[u]
		RELAX(u, v, w)

DIJKSTRA(G, w, s)
for each vertex v in G.V-{s}
	alpha[v] = infinity // s到v的距离
	pi[v] = NIL // v的前驱结点
alpha[s] = 0
Create an empty priority queue PQ // 创建优先队列PQ
for each vertex v in G.V
	INSERT(PQ, v, alpha[v]) // 关键值为alpha[v]
while PQ != empty
	u = EXTRACT-MIN(PQ) // 从优先队列中找到最小的，把u作为出发点
	for each edge e = (u,v) leaving u
		if alpha[v] > alpah[u] + le // le是边的长度
			alpha[v] = alpha[v] + le
			pi[v] = u
			Reset-Key(PQ, v, alpha[v]) // 修改以调整优先队列

时间复杂度

迪杰斯特拉算法的时间复杂度依赖于最小优先队列的实现。我们这里采用的是最小二叉堆。初始化即构建最小二叉堆O(n)，将每个结点从Q中删除是O(log n)那n个点是O(nlog n)，for each共执行m次，由于是二叉堆修改的时间复杂度为O(log n)，那么总共就是O(nlog n + mlog n)，由于连通图中 m >= n-1，因此总共就是O(mlog n)

定理、引理和推论证明

（1）（Dijsktra算法的正确性）Dijsktra算法运行在带权重的有向图G = (V, E)时，如果所有权重为非负值，则在所有算法终止时，对于所有结点u属于V，我们有u.d = 最短距离(s, u)。

证明：采用数学归纳法。当|S| = 1时，因为S = {s}并且d[s] = 0，成立。假设当|S| >= 1时也成立。令v为下一个将要被加入到S中的结点，令u是v的在S中的前驱结点，alpha(v) = d[u] + w(u, v)。我们只需证明没有任何一条路径的长度小于alpha(v)。考虑另外一条从s到v的路径P，令x是P中最后一个在S中的结点，令y的前驱结点为x。由于算法中是将alpha（估计值）最小的结点加入S中，因此一定有alpha(v) <= alpha(y)，那么P = alpha(y) + P(y, v) >= alpha(y) >= alpha(v)，则d[v] = alpha(v)一定是最小值。综上，算法是正确的。

注：
迪杰斯特拉算法生成的是最短路径树（shortest path tree）
为什么迪杰斯特拉算法要求权值非负呢？
先举一个反例，如果存在两组边分别为10和-8，3和3，那么算法就会优先选择3和3的一组边，而实际最短的是10和-8。如果权值为负，那么在上面的证明中就无法推出alpha(y) + P(y, v) >= alpha(y)，因为P(y, v)可能为负。综上，权值必须为非负的，才能保证正确性。
为什么迪杰斯特拉算法是一种贪心算法？
算法在运行时，每次都将估计值最小的结点加入集合S中。

最小生成树

注意事项：Kruscal算法和Prim算法都是贪心算法，Kruscal算法每次加入到A中的安全边永远是连接A和A之外某个结点的边中权重最小的边，Prim算法每次加入的边都必须是使树的总权重增加量最小的边。

伪代码：

（1）Kruscal算法：

MST-KRUSCAL(G, w)
A = emptySet
for each vertex v in G.V
	MAKE-SET(v)
sort the edges of G.E into nondecreasing order by weight w
for each edge(u, v) in G.E, taken in nondecreasing order by weight
	if FIND-SET(u) != FIND-SET(v)
		A = A union {(u, v)}
		UNION(u, v)
return A

（2）Prim算法：

MST-PRIM(G, w, r)
for each vertex v in G.V-{s}
	alpha[v] = infinity 
	pi[v] = NIL // v的前驱结点
alpha[s] = 0
Create an empty priority queue PQ // 创建优先队列PQ
for each vertex v in G.V
	INSERT(PQ, v, alpha[v]) // 关键值为alpha[v]
while PQ != empty
	u = EXTRACT-MIN(PQ) // 从优先队列中找到最小的
	for each edge e = (u,v) 且v在PQ中
		if w(u, v) < alpha[v] 
			alpha[v] = w(u, v)
			pi[v] = u
			Reset-Key(PQ, v, alpha[v]) // 修改以调整优先队列

3.时间复杂度

Kruscal算法和Prim算法都为O(mlog n)

4.定理、引理和推论证明

（1）定理：设G = (V, E)是一个在边E上定义了实数值权重函数w的连通无向图。设集合A为E的一个子集，且A包括在图G的某棵最小生成树中，设(S, V-S)是图G中尊重集合A的任意一个切割，又设(u, v)是横跨切割(S, V-S)的一条轻量级边。那么边(u, v)对于集合A是安全的。

证明：设T是一棵包含A的最小生成树，如果T包含(u, v)，那么该边对A集合一定是安全的。如果T不包含(u, v)，那么由于切割(S, V-S)尊重A，而A又是T的一部分，因此一定存在从S到V-S横跨切割的一条边(x, y)，该边不在A中且是T的一部分。设u在S中，v在V-S中，那么一定存在一条从u到v的经过(x, y)的简单路径。如果形成了一棵包含(u, v)的最小生成树T’，那么(u, v)对于A一定是安全的。如果直接将(u, v)加入其中，那么会与之前从u到v经过(x, y)的简单路径形成环，因此我们必须将(x, y)删除，T会形成两个连通分量，而加入(u, v)则可以将这两个连通分量连起来形成一棵新的生成树T’，我们要证明T’是最小生成树。因为T是一棵最小生成树，因此T中边的权重之和w(T) <= w(T’)，由(u, v)是轻量边，因此有边的权重w(u, v) <= w(x, y)，则有w(T’) <= w(T)，推出w(T’) = w(T)，即T’也是一棵最小生成树。A是T的一部分，(x, y)不是T的一部分，因此A是T’ 的一部分，所以A并上(u, v)也是T’ 的一部分，而T’ 是一棵最小生成树，那么(u, v)对于A来说一定是安全的。

（2）推论：设G = (V, E)是一个连通无向图，并有定义在边集合E上的实数值权重函数w。设集合A为E的一个子集，且该子集包括在G的某棵最小生成树里，并设C = (Vc, Ec)为森林Ga = (V, A)中的一个连通分量（树）。如果边(u, v)是连接C和Ga中某个其他连通分量的一条轻量级边，则边(u, v)对于集合A是安全的。

证明：切割(Vc, V - Vc)尊重集合A，边(u, v)是横跨该切割的一条轻量级边，因此，边(u, v)对于集合A是安全的。

并查集

并查集表示一组不连通集合的一种数据结构

并查集需要支持三种操作：

（1）MAKE-SET(x)：创造一个仅包含x的新连通分支（集合）

（2）FIND(x)：返回包含元素x的集合的代表元（就像是国家有主席、总统一样，代表元是该集合的代表）

（3）UNION(x, y)：将x和y所在的集合取并集，并用新的集合代替他们

令m = 上述三种操作的总的调用次数、n = 元素的数量

四种实现方式：

• naïve linking：自然连接
• link-by-rank：根据秩数连接
• path compression：路径压缩
• link-by-rank with path compression：带有路径压缩的根据秩数的连接

naïve linking方式
将第一个结点所在树的根节点连接到第二个结点所在树的根节点上

MAKE-SET(x)
parent[x] = x

FIND(x)
while (x != parent[x])
x = parent[x]
return x

UNION(x, y) 
r = FIND(x)
z = FIND(y)
parent[r] = z

定理：在最坏的情况下（形成了一个链表），一次find操作花费theta(n)时间，n是元素的数量

link-by-rank方式

每个结点保持一个整数——秩，初始时，所有集合的秩为0，在这里秩数等于树的高度。秩小的集合连接到秩大的集合中。

MAKE-SET(x)
parent[x] = x
rank[x] = 0

FIND(x)
while (x != parent[x])
x = parent[x]
return x

UNION(x, y)
r = FIND(x)
s = FIND(y)
if (r == s)
	return 
else if (rank[r] < rank[s])
	parent[r] = s
else if (rank[r] > rank[r])
	parent[s] = r
else 
	parent[r] = s
	rank[s] = rank[s] + 1  // 秩相同时，将其中一个的秩+1，将另一个连过来

该方法的6个性质：

（1）如果x不是根结点，那么rank[x]不会再发生改变。
证明：算法中只改变根结点的秩，而非根结点不会再变为根结点。

（2）如果x不是根结点，那么rank[x] < rank[parent[x]]。
证明：一个秩为k+1的根结点，只会通过两个秩为k的根结点合并产生。

（3）如果parent[x]改变，那么rank[parent[x]]严格增加。
证明：如果parent[x]改变，那么x一定是根结点，那么改变前有parent[x] == x，在x改变，即被连接到新的结点r时，有rank[parent[x]] = rank[r] > rank[x]。

（4）任何一个秩为k的结点，在以它为根结点的树中，至少含有2^k个结点。
证明：当k=0时，成立。做归纳假设，秩为k-1的节点，以它为根的树至少包含2^ (k-1）个结点。证明对秩为k的根结点依然成立。只有两个秩都为k-1的树合并，才能出现秩为k的树，根据归纳假设，这两课树至少含有2^ (k-1)个节点，合并后，至少含有2^k个结点，所以归纳假设成立。

（5）一个结点的秩的最大值为lower(log n)。
证明：有性质（4）很容易推出

（6）秩为k的结点数量最多为n/2^k。
证明：由性质（4）任何一个秩为k的结点，在其子树中至少含有2^k个结点。秩为k的不同结点不可能含有相同的后代。

定理：在最坏的情况下，UNION和FIND操作，需要花费O(log n)的时间。

证明：这两个操作以树的高度为界，而在性质（5）中，树的高度最高为lower(log n)。

path compression

路径压缩是针对FIND操作的重新组织

FIND(x)
if (x != parent[x])
parent[x] = FIND(parent[x])
return parent[x]

通过递归调用，将从x到根结点的路径上的所有结点的父结点都改为根结点。
路径压缩改变了树的结构。

动态规划

动态规划历史：Bellman 动态规划的先驱
斐波那契数列（Fibonacci Sequence）的例子

// 自顶向下
TOP-DOWN(n)
Initialize M[0...n] with -1 // -1: unfilled
M[0] <- 0; M[1] <- 1;
return fibonacci(n)

fibonacci(j)
if (M[j] == -1)
	M[j] <- fibonacci(j-1) + fibonacci(j-2)
return M[j]

// 自底向上
BOTTOM-UP(n)
Initialize M[0...n] with -1
M[0] <- 0; M[1] <- 1;
for i = 2 to n
	M[i] <- M[i-1] + M[i-2]

有向无环图中的单源最短路径问题（第24章 第2节）
有向无环图（directed acyclic graph DAG）
书中：

DAG-SHORTEST-PATH(G, w, s)
topologically sort the vertices of G
INITIALIZE-SINGLE-SOURCE(G, s)
for each vertex u, taken in topologically sorted order
	for each vertex v in G.Adj[u]
		RELAX(u, v, w)

DAG-SHORTEST-PATH(G, w, s)
topologically sort the vertices of G
for each vertex v in G.V
	v.d = infinity
	v.pi = NIL
s.d = 0
for each vertex u, taken in topologically sorted order
	for each vertex v in G.Adj[u]
		if v.d > u.d + w(u, v)
			v.d = u.d + w(u, v)
			v.pi = u

算法时间复杂度：拓扑排序theta(V+E)，初始化theta(V)，每条边进行了一次松弛为theta(E)，因此总运行时间为theta(V+E)

动态规划可以被使用，如果满足下面的条件

1.由多项式数量的子问题组成

2.原问题的解决可以简单地由子问题计算而来

3.从“最小”到“最大”有一个子问题的简单的顺序

子问题之间有清晰的相互依赖关系，这是动态规划算法的核心。如斐波那契数列、有向无环图中的单源最短路径问题

动态规划技术通常用于解决最优化问题

0-1背包问题（Knapsack problem）

定义：OPT(i, w) = 在重量限制w的情况下，从1到i个物品放入背包中的最大价值。

目标：OPT(n, W)

Bellman equation

KNAPSACK(n, W, w1, w2, ..., wn, v1, v2, ..., vn)
for w=0 to W
	M[0, w] = 0
for i=1 to n
	for w=0 to W
		if (wi > w)
			M[i, w] = M[i-1, w]
		else
			M[i, w] = max{M[i-1, w], vi+M[i-1, w-wi]}
return M[n, W]

算法时间复杂度：O(nW)，但这个不是多项式时间算法。（这个解释如果大家想去了解，可以去网上搜索相关资料）

从(n, W)的方格向上移动，如果两个方格(i, w)与(i-1, w)的值相同，说明物体i没有放入背包；如果不相同说明物体i放入了背包中，根据Bellman equation，移动到上一行(i-1, w-wi)，按照这个规则继续下去。同则向上，不同则移动。

在本例中，右下角为(5, 11)值为40，向上(4, 11)仍为40，说明物体5没有放入背包中，再往上(3, 11)为25，说明物体4放入了背包中，那么11kg-6kg=5kg，所以上一个位置移动到(3, 5)方格值为18，向上(2, 5)值为7，说明物体3放入了背包中，5kg-5kg=0kg，因此上一个位置移动到(2, 0)方格，接下来一直到(0, 0)值没有变化，即没有新的物体放入背包中。

#include <iostream>
#include <cstdio>
using namespace std;

int max(int, int);

int main()
{
	// 输入部分
	int W; // 背包容量
	int n; // 物体数量
	cout << "请输入背包容量（正整数）：";
	cin >> W;
	cout << "请输入物体数量（正整数）：";
	cin >> n;
	int w[n+1] = {0}; // 每个物体的重量
	int v[n+1] = {0}; // 每个物体的价值
	cout << "请输入物体重量和价值按照"重量 价值"输入：";
	for (int i = 1; i <= n; i++)
		cin >> w[i] >> v[i];

// 求解部分
int table[n+1][W+1]; // 动态规划表
for (int i = 0; i <= W; i++)
	table[0][i] = 0;
for (int i = 1; i <= n; i++)
{
	for (int j = 0; j <= W; j++)
	{
		if (w[i] > j)
			table[i][j] = table[i-1][j];
		else
			table[i][j] = max(table[i-1][j], v[i] + table[i-1][j-w[i]]);
	}
}
bool things[n+1] = {false}; // 装入背包中的物品
int k = W;
for (int i = n; i >= 1; i--)
{
	if (table[i][k] > table[i-1][k])
	{
		things[i] = true;
		k -= w[i];
	}
}

// 输出部分
cout << "动态规划表为：" << endl;
for (int i = 0; i <= n; i++)
{
	for (int j = 0; j <= W; j++)
		printf("%3d ", table[i][j]);
	cout << endl;
}
cout << "应该装入物品：";
for (int i = 1; i <= n; i++)
{
	if (things[i])
		cout << i << " ";
}
cout << endl;
cout << "最优解的值为：" << table[n][W] << endl;

return 0;
}

int max(int i, int j)
{
	return i >= j ? i : j;
}

运行结果：

带有负环的最短路径问题

负环（negative cycle）是一个有向环，环中边的权重之和为负值。

正环（positive cycle）是一个有向环，环中边的权重之和为正值。（不可能出现）

0环是一个有向环，环中边的权重之和为0。（可以出现，但没必要）

引理1：如果存在从s -> v的路径包含负环，那么不存在从s -> v的最短路径

证明：如果存在这样的负环，那么可以无限的经过负环，降低路径上的权重和。

引理2：如果图G不存在负环，那么存在从s -> v的一条简单最短路径。（最短路径不含环）

为了解决一般的单源最短路径问题，我们将这个问题分成两个，一个是不含负环的单源最短路径问题，一个是负环的识别问题。

Def. OPT(i, v) = length of shortest s -> v path that uses at most i edges.
Goal. OPT(n-1, v) for each v.


SHORTEST-PATHS(V, E, l, s)
foreach node v in V:
	M[0, v] <- infinity
M[0, s] <- 0
for i = 1 to n-1
	foreach node v in V:
		M[i, v] <- M[i-1, v]
		foreach edge(u, v) in E
			M[i, v] <- min{M[i, v], M[i-1, u] + luv}

空间复杂度：O(n^2) 一个二维数组

时间复杂度：O(nm)

存储图的数据结构可以采用以入边为依据的邻接链表

作业2：对下图进行填表（s为出发点）

结果：

如何通过表得到顶点s到各个顶点的最短路径长度？表中最后一行就是从s到各个顶点的最短路径长度。
如何通过表得到顶点s到各个顶点的最短路径？其实我认为通过上面的动态规划表也是可以的，和之前的方式一样，如果发生变化就通过计算得到之前的点……。老师说可以改变算法结构，增加一个二维数组pn-1，用来记录前驱顶点，通过这个新的二维数组的最后一行就可以得到路径，但我通过检验其实一维数组p[v]也是完全可以的。但还是通过维护一个记录前驱的一维数组进行回溯方便。

我们可以通过维护两个一维数组，而不是维护一个二维数组
d[v] = length of a shortest s->v path that we have found so far.
predecessor[v] = preceding node on the above s->v path.

引理3：对每一个顶点，d[v]是单调非递增的。

引理4：在第i次迭代后，d[v]是当前从s->v用最多i条边的最短路径长度。

证明：当i = 0时成立。假设第i次后，成立。那么在第i+1次后，令p是另一个从s->v的含有最多i+1条边的路径，令u是v的前驱顶点，那么从s->u最多包含i条边，设从s->u的任意路径为p’，那么根据归纳假设有d[u] <= l(p’)，因此有d[v] = d[u] + luv <= l(p’ ) + luv = l(p )，所以假设成立。（这个证明很重要）

推论：如果最短路径含有k条边，那么算法可以在最多k次迭代后找到最短路径。

定理2：假设没有负环，Bellman-Ford计算从s->v的最短路径，时间复杂度为O(mn)，空间复杂度为theta(n)

证明：引理2+引理4

负环检测问题（Detecting negative cycles）

先用Bellman-Ford算法迭代n-1次，接着再迭代1次，如果最短路径长度继续减小，说明一定含有负环。

引理5：对于每个结点v，如果有OPT(n, v) = OPT(n-1, v)，那么没有负环。

证明：（OPT(n+1, v)的推导中，OPT(n-1, u) + luv = OPT(n, v)，因此得到最后的结果。这是老师给的证明方法，更为直观一些，但用归纳法证明更好。）

引理6：如果对某些结点有OPT(n, v) < OPT(n-1, v)，那么从s->v的长度为n最短路径一定含有环W，且是负环。

证明：如果OPT(n, v) < OPT(n-1, v)，任何s->v的最短路p，最多含有n条边，实际上更准确的是含有n条边，否则OPT(n, v) = OPT(n-1, v)。由鸽巢原理，路径p一定包含重复的结点x，令W为路径p中的环，如果W不是负环，那么删除W，则s->v最多有n-1条边并且有OPT(n, v) = OPT(n-1, v)。此时产生矛盾，因此W是负环。
引理6的逆否命题：引理6’：如果不含负环，那么对于每个结点有OPT(n, v) = OPT(n-1, v)。

定理4：如果对于每个结点v有OPT(n, v) = OPT(n-1, v)，当且仅当不含负环。

证明：引理5 + 引理6’

定理5：能够在theta(mn)的时间内，找到一个负环。

BELLMAN-FORD(V, E, l, s)
foreach node v in V:
	d[v] <- infinity
	predecessor[v] <- null
d[s] <- 0
for i = 1 to n-1:
	foreach node v in V:
		foreach edge(u, v) in E:
			if (d[v] > d[u] + luv)
				d[v] <- d[u] + luv
				predecessor[v] <- u
foreach edge(u, v) in E:
	if (d[v] > d[u] + luv)
		return true // 含有负环
return false // 不含有负环

所有结点对之间的最短距离

给一个nxn的权值矩阵W，表示有向图G = (W, E)边的权值。输出一个距离矩阵D = (dij)，表示顶点i和顶点j之间的距离。

定义：Lij(m) = i -> j 的路径且最多含有m条边

目标：Lij(n-1) 每一对顶点i和j（不能含有负环）

lij(m)表示，从 i 到 j 最多含有m条边的最短路长度

伪代码：

ALL-PAIRS-SHORTEST-PATHS(W)
n = W.rows
L(1) = W 
for m = 2 to n-1
	let L(m) be a new n x n matrix
	L(m) = EXTEND-SHORTEST-PATHS(L(m-1), W) 
return L(n-1)

EXTEND-SHORTEST-PATHS(L, W)
n = L.rows
let L’ = (Lij’) be a new n x n matrix
for i = 1 to n 
	for j = 1 to n
		Lij’ = infinity
		for k = 1 to n
			Lij’ = min(Lij’, Lik + wkj)
return L’

时间复杂度 O(n^4)

Lij(m) = min{Lik(m-1) + wkj | 1 <= k <= n}，这个我感觉很漂亮，很像矩阵相乘

Lij(4) = min{Lik(2) + Lkj(2) | 1 <= k <= n}
当最后一次进入主过程的循环时，2m > n-1，由第十部分动态规划中的Bellman-Ford算法，我们已经知道，此时的Lij(2m)已经收敛等于Lij(n-1)
（不能含有负环）

ALL-PAIRS-SHORTEST-PATHS(W)
n = W.rows
L(1) = W 
m = 1
while m < n - 1
	let L(2m) be a new n x n matrix
	L(2m) = EXTEND-SHORTEST-PATHS(L(m), L(m)) 
	m = 2m
return L(m)

时间复杂度 O(n^3 logn)

Floyd-Warshall Algorithm

定义：dij(k) = i -> j的最短路径长度，其中间结点的下标取自{1, 2, …, k}中（下标）

目标：对于每一对结点i和j计算dij(n)

第k个结点不在路径中，第k个结点在路径中。只有这两种可能。（不能含有负环）

伪代码：

FLOYD-WARSHALL ALGORITHM
n = W.rows
D(0) = W
for k = 1 to n
	let D(k) = (dij(k)) be a new n x n matrix
	for i = 1 to n
		for j = 1 to n
			dij(k) = min(dij(k-1), dik(k-1) + dkj(k-1))
return D(n)

时间复杂度 O(n^3)

可以含有负环的算法：Johnson’s ALgorithm

NP完全性

问题有两种描述方式，优化模式（Optimization Problem）和判别模式（Decision Problem）

归约：一个步骤f，可以将问题A的任何一个实例都转换成问题B的实例并且要满足下面的两个要求。

Transformation：这个转换过程必须在多项式时间内完成。

Equivalence：一个实例或一个项，必须同时为YES或NO。（注意下面的定义，“问题A可以在多项式时间内被归约为问题B”，小p指的是多项式时间）

定理：如果问题B可以在多项式时间内被解决，那么A也可以在多项式时间内被解决。

证明：

（1）给定一个问题A的一个实例alpha，使用多项式时间归约为beita = f(alpha)

（2）运用B的多项式时间算法，解决实例beita = f(alpha)

（3）使用beita的答案作为alpha的答案

定理：相反地，如果A不存在多项式时间算法，那么B也不存在多项式时间算法（该定理是之前定理的逆否命题）

Vertex Cover顶点覆盖问题

输入：一个图G = (V, E)和一个整数k

输出：是否存在一个顶点集合S属于V，|S| = k，使得每条边至少和这k个顶点中的一个相关联，能找到为YES，找不到为NO

Set Cover集合覆盖问题

输入：一个含有n个元素的集合U = {e1, e2, …, en}，给一系列的m个子集S = {S1, S2, …, Sm}，和一个整数k

输出：是否存在一个集合C属于S，使得C中各集合的元素的并集为U并且|C| <= k，存在为YES，不存在为NO

定理：顶点覆盖问题可以在多项式时间内归约为集合覆盖问题

证明：给一个顶点集合实例G = (V, E)和k，我们构造一个集合覆盖实例(U, S, k)，使得S中的k个集合能够覆盖U，当且仅当G有一个大小为k的顶点集合覆盖。

构造（Construction）：

• 令U = E
• 对于V中的每一个v，构造一个集合Sv = {e属于E，e关联于v}

（简单点说，就是E中的每一条边就是U中的每一个元素，V中的每个顶点就是S中的每个集合，V中顶点关联的边就是S中集合的元素）

断言（Claim）：G = (V, E)有一个大小为k的顶点覆盖当且仅当(U, S)有一个大小为k的集合覆盖

证明：

=> 令X是V的子集，是一个在G中大小为k的顶点覆盖
令Y = {Sv : v属于X}是一个大小为k的集合覆盖

<= 令Y属于S，是一个大小为k的集合覆盖
令X = {v : Sv属于Y}是一个在G中大小为k的顶点覆盖

Construction + Claim => 顶点覆盖可以在多项式时间内归约为集合覆盖
（也就是说顶点覆盖比集合覆盖在计算上更容易，因此用式子表示式小于等于号）

3SAT问题（3-SATISFIABILITY Problem）

3SAT Problem是SAT问题的特殊情况，即每一个子句中恰好包含了3个文字

独立集问题（Independent Set Problem）

输入：给定一个图G = (V, E)，和一个整数k
输出：是否存在一组顶点的集合S属于V，|S| = k，使得没有在S中没有两个顶点由一条边相连（即集合S中的k个顶点，两两不相邻）

定理：3SAT问题可以在多项式时间内归约为独立集问题

证明：给定一个3SAT问题的实例，我们构造一个独立集问题(G, k)，其有一个大小为k的独立集，当且仅当3SAT问题的实例是可满足的
构造（Construction）：

• 每个子句中的1个文字对应1个顶点
• 每个子句中的3个文字所对应的3个顶点，两两相邻，构成一个三角
• 不同子句间互为相反的文字连接起来