算法(13)-近似算法

• 很多实际问题是NP完全问题, 那么求解有三种策略: (1)如果实际输入数据规模较小, 用指数级算法直接求解 (2)对于一些能在多项式时间内解决的特殊情况, 可以单独列出来求解 (3)寻找在多项式时间内得到近似最优解的算法

近似算法的性能比

• 规模为n的任意输入, 近似算法获得的近似解C与精确最优解的代价C*只差一个因子ρ(n):
  max(C/C*, C*/C) <= ρ(n)
  ρ(n)是该算法的近似比.

近似模式(一般与完美)

对一个近似模式来说, 如果误差参数e>0是一个固定值, 且该模式都以其输入实例规模n的多项式时间运行, 则称此模式为多项式时间近似模式, 比如O(n^(1/e))
对于一个近似模式来说, 如果其运行时间表达式为1/e的多项式, 又是输入实例n的多项式, 那么这就是完全的(也可以说是完美的)多项式时间的近似模式. 近似模式的运行时间可能是O(1/e^2*n3)

顶点覆盖问题VertexCover

Approx-Vertex-Cover(G):
C = ∅
E' = G.E
while E' ≠ ∅:
    let (u, v) be an arbitrary edge of E'
    C = C∪{u, v}
    remove from E' every edge incident on either u or v
return C

证明: 这是一个2近似算法
|C|>=|A| #A是被标成红色的边, C是最优的覆盖需要的顶点数
|C|=2|A| #C是近似的覆盖需要的顶点数
|C| = 2|A| <= 2|C*|

旅行商问题

• 求旅行商问题, 在增加一个三角不等式的条件后, 可以得到一个近似算法;
  －三角不等式: c(u, v) <= c(u, m) + c(m, v) (其中m是一个中间结点)
• 输入:

Approx-TSP(G, C)
choose a r∈G.V as the root of MST
use MST-Prim(G, C, r) to get a MST
root-first order to traverse the MST tree and get a list L of vertexes 
#先根遍历意味着Root-Left-Right的顺序
follow L and form a Ham-Cycle

• 时间复杂度分析: MST-Prim按道理是O(E+logV), 此处是完全图, 因此E=V^2, 因此整个算法最后是O(V^2)
• 解的精确度:
  Approx-TSP具有性能比2. 先序遍历解H删掉一条边, 就是一个过所有点的生成树, 而所有的生成树的边的总代价肯定都大于等于最小生成树MST, 所以有C(T)<=C(T')<=C(H).
  再者, 先序遍历中如果不允许跨越的话, 直接严格在MST上走的路线W, 恰好是把最小生成树MST上的每条边走了两次, 因此C(W)=2C(T).
  最后, C(W)>=C(H), 这是因为三角不等式被作为一个前提条件, 换句话说, 借助中间点没有两点直接连接的代价小.
  综合看, 2C(T)>=C(H), 2C(H*)>=2C(T), --> 2C(H*)>=C(H), C(H)/C(H*) <= 2, 因此我们解的性能比值为2.

集合覆盖问题

• 算法是一个贪心算法, 每次选一个尽可能大地多覆盖一些未触及点的集合.

Greedy-Set-Cover(X, F) #F是X的子集族
U = X   #Undiscovered dots
e = ∅  #e collects sets.
while U ≠ ∅:  #仍然有未发现的点
    select an S∈F that maximizes |S∩U|  #S∩U代表S集合能够覆盖的Undiscovered dots, 此处选能覆盖最多的S
    U = U-S  #remove those covered by S
    e = e∪{S}  #bring S in
return e  #返回这些集合

算法时间:多项式时间的ρ（ｎ）近似算法, ln|X|+1.