- 很多实际问题是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/e2*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.
