分治

分治问题复杂度计算

网络流

最短路径算法复杂度

• Dijkstra：O(n2)适用于权值为非负的图的单源最短路径，用斐波那契堆的复杂度O(E+VlgV)

• BellmanFord：适用于权值有负值的图的单源最短路径，并且能够检测负圈，复杂度O(VE)

• SPFA：适用于权值有负值，且没有负圈的图的单源最短路径，论文中的复杂度O(kE)，k为每个节点进入Queue的次数，且k一般<=2，但此处的复杂度证明是有问题的，其实SPFA的最坏情况应该是O(VE).

• Floyd：每对节点之间的最短路径。Floyd-Warshall算法的时间复杂度为O(N3)，空间复杂度为O(N2)

最大流算法复杂度

n表示节点数，m表示边数

NPC问题

证明一个问题是 NPC问题。先证明它至少是一个NP问题，再证明其中一个已知的NPC问题能约化到它，这样就可以说它是NPC问题了

问题分类

• P: 能在多项式时间内解决的问题

• NP: 不能在多项式时间内解决或不确定能不能在多项式时间内解决，但能在多项式时间验证的问题

• NPC: NP完全问题，所有NP问题在多项式时间内都能约化(Reducibility)到它的NP问题，即解决了此NPC问题，所有NP问题也都得到解决

• NP hard:NP难问题，所有NP问题在多项式时间内都能约化(Reducibility)到它的问题(不一定是NP问题)

问题难度

Independent Set Problem

Suppose you have n friends, and some pairs of them don’t get along. How to invite at least k of them to dinner if you don’t want any interpersonal tension?

Input: Given a graph G =< V, E >, and an integer k,

Output: is there a set of nodes S⊆V, |S|=k , such that no two nodes in S are joined by an edge?

The three nodes in blue are independent.

Vertex Cover Problem

Given n sites connected with paths, how many guards (or

cameras) should be deployed on sites to surveille all the paths?

Input: Given a graph G =< V, E >, and an integer k,

Output: is there a set of nodes S ⊆ V, |S| = k, such that eachedge has at least one of its endpoints in S?

the complement of an independent set (in blue) forms a vertex cover (in red)

SAT (Satisfiability) Problem

expressing constraints on a set of variables (in AI), verifying whether a circuit has the desired functionality (in VLSI), etc.

Input: Given a CNF φ = C1 ∧C2…∧Ck;

Output: Is there an assignment of all xi such that all clauses Cj.are satisfied?

Example:

CNF: (x1 ∨¬x2)∧(¬x1 ∨¬x3)∧(x2 ∨¬x3)

TRUE assignment: x1 = FALSE, x2 = FALSE, x3 = FALSE;

3SAT Problem

每个 Ci 含有三个变量

Hamilton Cycle Problem

Input: Given a graph G =< V, E >

Output: Is there a cycle visiting every node exactly once?

3 Coloring

Output: Is there a k−coloring of G such that each node has a color, but the two endpoints of an edge have different colors?

SubsetSum problem

Input: Given n numbers S = w1, w2, …, wn, and an objective value W;

Output: is there a subset S′ ⊆ S such that the sum of S′ is W?

Clique problem

Input: Graph G =< V, E >, an integer k;

Output: is there a clique of size k? Here, a clique refers to a subset of vertices that are all connected.

线性规划

原始问题

对偶问题