Just so so
1/30
2018

算法课程笔记

分治

分治问题复杂度计算

DC

网络流

最短路径算法复杂度

  • 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表示边数

MaxFlow

NPC问题

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

问题分类

p-np-npc-nphard

  • P: 能在多项式时间内解决的问题
  • NP: 不能在多项式时间内解决或不确定能不能在多项式时间内解决,但能在多项式时间验证的问题
  • NPC: NP完全问题,所有NP问题在多项式时间内都能约化(Reducibility)到它的NP问题,即解决了此NPC问题,所有NP问题也都得到解决
  • NP hard:NP难问题,所有NP问题在多项式时间内都能约化(Reducibility)到它的问题(不一定是NP问题)

问题难度

problem

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?

isp

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?

vcp

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?

3color

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.

线性规划

原始问题

original

对偶问题

dual