算法设计与分析讲义chapter7.doc

第七章 近似算法很多实际应用中问题都是NP-完全问题NP-完全问题的多项式算法是难以得到的求解NP-完全问题的两种方法： 如果问题的输入很小，可以使用指数级算法圆满地解决该问题 使用多项式算法求解问题的近似优化解近似算法：能够给出一个优化问题的近似优化解的算法本章将介绍几个NP-完全问题的多项式时间算法7.1 近似算法的性能分析本节讨论的问题是优化问题问题的每一个可能的解都具有一个正的代价问题的优化解可能具有最大或最小代价最大化或最小化问题我们希望寻找问题的一个近似优化解1. Ratio Bound 定义1(Ratio Bound) 设A是一个优化问题的近似算法，A具有ratio bound p(n)，如果, 其中n是输入大小，c是近似算法所产生的解的代价，c*是优化解的代价。 *若问题是最大化问题，则，*若问题是最小化问题，则，*由于c/c*1, 近似算法的Ratio Bound不会小 于1，即*求解准确优化解的优化算法的Ratio Bound一定是1*具有较大Ratio Bound的近似算法给出的近似解一定比优化解坏 的多 Ratio Bound表示了近似算法的性能2. 相对误差定义2 对于任意输入, 近似算法的相对误差定义为, 其中c是近似算法所产生的解的代价，c*是优化解的代价。 *相对误差总是非负的。定义3 一个近似算法的相对误差界为如果。 结论1 。 证. 对于最小化问题= 对于最大化问题=. *对于某些问题，和独立于输入n，我们用p和表示之*对于另一些问题，很难找到具有固定ratio bound的多项式时间 算法，我们可以令ratio bound是输入大小n的函数*某些NP-完全问题的近似算法满足：当运行时间增加时，ratio bound和相对误差将减少 定义4 一个优化问题的近似模式是一个算法，是一个具有相对误差界的近似算法，其中I是问题实例，是任意一个固定的数。 定义5 近似模式称为一个多项式时间近似模式，如果对于，的运行时间是的多项式。 定义 6 一个近似模式称为完全多项式时间近似模式，如果它的运行时间是关于和输入实例大小n的多项式。 例1. 设模式s的运行时间是，则s是完全多项式时间近似模式。7.2 优化结点覆盖问题1. 问题定义输入：无向图G=（V，E）输出：，满足 (1).，、或u,vV (2).是满足条件(1)的最小集合。 *理论上已经证明优化结点覆盖问题是NP-完全问题。2. 近似算法APPROX-Vertex-Cover (G)1.2.3.while DO4. 任取5. 6. EE-(u,v)|u=u或v=v7. Roturn C3. 时间复杂性 T(G)=O(|E|).4. 性能 定理1 Approx-Vertex-Cover 具有Ratio Bound 2 证: 令A=是算法第4步选中的边。 若(u,v)A，则所以与（u,v）邻接的边皆从中删除。 于是, A中无相邻接边. 于是，第五步的每次运行增加两个结点到C，|C|=2|A| 设C*是优化解，C*必须覆盖A。 由于A中无邻接边，C*至少包含A中每条边的一个结点。 于是，|A|C*|，|C|=2|A|2|C*|，即|C|/|C*|2.7.3 最小集合覆盖问题1. 问题的定义 输入：有限集X，F是X的所有子集合集族，X=输出：CF，满足 (1). X=， (2). C是满足条件(1)的最小集族，即|C|最小。 *最小集合覆盖问题是很多实际问题的抽象。 *最小集合覆盖问题是NP-完全问题。2. Greedy近似算法 Greedy-Set-Cover(X,F)1.UX;2.Cq;3. While Uq Do /* U表示X中尚未被覆盖的元素的集合 */4. select SF 使得|SU|最大; /* Greedy选择选择能够覆盖最多X元素的子集合S */5. UU-S6. CCS; /* 构造X的覆盖 */7. Return C.3. 复杂性3-6的循环次数至多为min(|X|,|F|) |SU|需要时间O(|X|) 第4步需要时间O(|F|X|) T(X,F)=O(|F|X|min(|x|,|F|)4. 性能定理1 令H(d)=。Greedy-Set-Cover具有Ratio Bound H(max|S|: SF)。证：设C*是优化的集合覆盖, C*的代价是|C*|。令Si是由Greedy-Set-Cover选中的第i个子集。设当把Si加入C时, C的代价加1。把选择Si的代价均匀地分配到由Si首次覆盖的所有结点。对于xX，令cx是分配到x的代价。若x被Si首次覆盖,则cx=. 显然，算法给出的解C的代价为|C|，|C|平均地分布到x的所有点.由于C*也覆盖X，我们有|C|=.注意：上式的小于成立是因为C*中各子集可能相交，在中，某些cx被加了多次，而在中每个cx只加一次。 如果SF，H(|s|)成立，则|C|C*|H(max|S|: SF),即|C|/|C*|H(max|S|: SF), 定理成立。 现在我们来证明：对于SF，H(|S|)。对于SF和i=1,2,.|C|, 令ui=|S-(S1S2.Si)|是S1、S2、.、Si被选中后，S中未被覆盖的点数。令u0=|S|, k是满足下列条件的最小数：uk=0, 即S中每个元素被S1、S2、.、Sk中至少一个覆盖。显然，ui-1ui, ui-1-ui是S中由Si第一次覆盖的元素数。于是，。注意：|Si-(S1S2.Si-1|S-(S1S2.Si-1|=ui-1, 因为Greed算法保证：S不能覆盖多于Si覆盖的新结点数,否则S将在Si之前被选中。于是，。对于任意整数ab,我们有H(b)-H(a)=(b-a) 。 使用上面结果，H(ui-1)- H(uI)(ui-1-ui)。 =H(u0)-H(uk) =H(u0)-H(0) (因为uk=0) =H(u0) (因为H(0)=0) =H(|S|) (因为u0=|s|). 推论1 Greedy-Set-Cover具有Ratio Bound ln(|x|+1) 证：由不等式ln(n+1)可知 H(max|S|:SF)H(|X|)=ln|x|+1。7.4 子集求和问题1. 问题定义 输入：(S,t), S=x1,x2,.xn xi=整数，t=正整数 输出：, 其中AS，t且=max|BS2. 幂函数时间算法 定义1 设S是一个集合，x是一个正整数，定义S+x=s+x | sS. 算法 输入：S=x1,x2,.xn xi=整数，t=正整数 输出：, 其中AS，t且=max|BS Exact-Subset-Sum(s,t) s=x1,x2,.xn1. n|s|;2. L0;3. For i1 To n Do4. LiMerge-List(Li-1,Li-1+xi);5. 删除Li中所有大于t的元素;6. Return Ln中最大元素. *Merge-List(L,L)合并L和L, 产生一个有序表.*Merge-List(L,L)的时间复杂性为O(|L|+|L|). Exact-Subset-Sun(s,t)计算过程： L0= L1= /* 前一个元素所有子集的和 */ L2= /* 前二个元素所有子集的和 */ L3= /* 前三个元素所有子集的和 */ 算法正确性：令p0=0, pi=x | x=,Ax1,x2,.xi,即pi是x1,x2,.xi的所有子集合的集合。pi= pi-1(pi-1+ pi). 我们可以对i作数学归纳法，证明Li是pi中所有不大于t的元素的有序表。于是，算法是正确的。算法的复杂性：|Li|2iT(S,t)1+21+22+.+2n=O(2n).3. 完全多项式时间近似模式Trim算法 定义2(修剪表L) 设(01)是修剪参数, L是一个表. 根据修剪L是指:(1). 从L中删除尽可能多的元素,(2). 如果L是L修剪后的结果, 则对于每个从L中删除的元素y, L中存在一个元素zy, 使得(y-z)/y或(1-)yzy. *如果y被修剪掉，则存在一个代表y的z没有被修剪掉，而且z相对于y的相对误差小于。 例. 如果=0.1, L=, 则L修剪为L=. 算法 输入：L=y1,y2,.ym, yiyi+1; 01 输出：L: Trimed有序表 Trim(L,)1. m|x|2. L3. lasty14. For i2 To m Do5. If last(1-)yi /* yi-1(1-)yi, 即对于yL,不满足(1-)yiy */6. Then yi加入到L末尾 /* L中目前没有能够表示yi的元素 */7. last yi8. Return L 复杂性：T(L,)=0(|L|)=0(m)完全多项式近似模式 输入：S=x1,x2,.xn, t0, 0e1 输出：近似解 Approx-Subset-Sum(S,t,e)1. n|S|2. L03. For i1 To n Do4. LiMerge-List(Li-1,Li-1+xi)5. LiTrim(Li,e/n) /* 修剪参数=e/n */6. 从Li中删除大于t的元素7. 令z是Ln中最大值8. Return z 定理1 Approx-Subset-Sum是子集求和问题的一个完全多项式时间近似模式。证：如前所述，pi= pi-1(pi-1+ pi)=x | x=,Ax1,x2,.xi是x1,x2,.xi的所有子集合的和的集合, p0=0。Li经第5步修剪以及第6步的大于t元素的删除，仍然有LipI。于是，第8步返回的z是S的某个子集的和。我们需证明 C*(1-e)z,即(C*-z)/C*e, C*是优化解，z是Approx-Subset-Sum产生的近似解。注意，由于子集合求和问题是最大化问题，(C*-z)/C*是Approx-Subset-Sum的相对误差。 算法是关于|S|和1/e的多项式时间算法。(1). 往证C*(1-e)z 我们对i作归纳法证明：ypi, yt, 存在一个zLi使(1-e/n)iyzy. 当i=0时pi=0,Li=0,命题成立。设当ik时命题成立。pk+1= pkpk+xk+1。由归纳假设，ypk+1pk,yt,存在zLkLk+1使(1-e/n)kyzy, 于是(1-e/n)k+1yzy。而对于ypk+1-pk，y=y+xk+1t,ypk,由归纳假设，存在zLkLk+1使(1-e/n)kyzy。于是，(1-e/n)ky+xk+1z+xk+1y+xk+1。由于zLk，z+xk+1Lk+1, 而且(1-e/n)ky+xk+1)-(1-e/n)k+1(y+xk+1) =(1-e/n)k(y-(1-e/n)y)+(xk+1-(1-e/n)k+1xk+1)0,即(1-e/n)k+1(y+xk+1)(1-e/n)ky+xk+1z+xk+1y+xk+1。最后，如果C*pn是子集合求和问题的优化解，则存在一个zLn， 使得(1-e/n)n C*zC*。Approx-Subset-Sum返回最大的这样的z,即z。由于，(1-e/n)n是关于n递增的函数。由于n1, (1-e)e/n,即，z/z1/(1-e/n)。如果Li中具有k+2个元素，则必有：y0=0, y1=z0, y2z01/(1-e/n), y3z01/(1-e/n)2, yk+1z01/(1-e/n)k, 而且z01/(1-e/n)kt故Li中元素至多为k+2=2+log1/(1-e/n)t=2+（lnt/-ln(1-e/n)） 2+nlnt/e。 算法的运行时间是|Li|的多项式，即n和1/e的多项式。7.5 Traveling-Salesman Problem (TSP)7.5.1 问题定义输入：完全无向图G=(V,E), 代价函数C：E非负整数集合。输出：具有最小代价的Hamilton环 * Hamilton环是一个包含V中每个结点一次的简单环。 *代价函数的扩展：设AE，C(A)=。*三角不等式：C(u,w)C(u,v)+C(v,w).*满足三角不等式的TSP问题是NP完全问题。*不满足三角不等式的TSP问题更是NP完全问题。*不满足三角不等式的TSP问题的近似算法没有常数Ratio bound， 除非NP=P。7.5.2 满足三角不等式的TSP问题1. 最小生成树算法问题定义 输入：无向连通图G=(V,E), 权函数W：E非负整数集合。 输出：具有最小权的无环TE。 *权函数的扩展：设TE，W(T)=。 Prim算法 输入：无向连通图G，权函数W，生成树的根r 输出：最小生成树(v, pv) | vV-r 数据结构：Q：优先队列,在算法执行过程中始终存储G不在生成 树中的结点集合； keyv: 生成树中与v相邻接的所有边的最小权，如 果这样的边不存在，keyv= pv：在生成树中v的父结点。 MST-Prim(G,w,r)1 Q=VG; /* G的所有结点加入优先队列 */2 FOR each uQ DO3 Keyu=;4 keyr=0; /* 令树根是目前具有最小key的结点 */5 pr=NIL; /* 树根无父结点 */6 While Q0 Do7 u=EXTRACT-MIN(Q); /* 从Q中取出具有最小key的结点u，u连接(V-Q,Q) */ 8 For each vAdju Do