算法探析与策划2016第14讲.ppt

IP(If xi?{0,1}), LP(If xi?0) Min{w1x1+w2x2+w3x3+w4x4+w5x5+w6x6} x1+x2?1 x1+x6?1 x2+x3?1 x2+x4?1 x2+x6?1 x3+x4?1 x4+x5?1 x4+x6?1 x5+x6?1 w1 w2 w3 w4 w5 w6 0?xi 整数规划是NP-hard,放松xi?0整数规划变为线性规划 IP?LP ZLP(G,W) ? OPT(G,W) 让x1, x2, …, xn在[0,?]之间取值 Min{w1x1+w2x2+w3x3+w4x4+w5x5+w6x6} x1,x2,x3,x4,x5,x6?0 x1+x2?1 x1+x6?1 x2+x3?1 x2+x4?1 x2+x6?1 x3+x4?1 x4+x5?1 x4+x6?1 x5+x6?1 Relax, xi?{0,1} ? xi?0 xi+xj?1 i j 算法分析与设计 第14讲-2016 山东大学计算机学院 1+? C logn n? T(n)=P(n,1/?) 隐含?是常数 Full polynomial time approximation scheme P1, P2, …, Pn W1,W2, …,Wn 为什么叫多项式近似方案，而不叫多项式近似算法。人可以控制? 集合S(i)记录所有数对。 放入p, w Pil+p?Pik+p, Wil+w?Wik+w Wnk?M ? ?P, w1?，?P, w2?，两者必去掉一个。 \{被他数对支配的数对}, 1?in 到前i个数对时 S(i+1) = S(i+1)-{被其他支配} P=(P1,P2,P3,P4,P5)=(W1,W2,W3,W4,W5)=W=(1,2,10,100,1000) M=1112, 因为每个元素价值与重量相等， 所以就不用考虑数对了，只考虑一个数。 P=(P1,P2,P3,P4,P5)=(W1,W2,W3,W4,W5)=W=(1,2,10,100,1000) M=1112 P=(P1,P2,P3,P4,P5)=(W1,W2,W3,W4,W5)=W=(1,2,10,100,1000) 第一个元素 M=1112 P=(P1,P2,P3,P4,P5)=(W1,W2,W3,W4,W5)=W=(1,2,10,100,1000) 第二个元素 M=1112 P=(P1,P2,P3,P4,P5)=(W1,W2,W3,W4,W5)=W=(1,2,10,100,1000) 第二个元素 M=1112 P=(P1,P2,P3,P4,P5)=(W1,W2,W3,W4,W5)=W=(1,2,10,100,1000) 第三个元素 M=1112 P=(P1,P2,P3,P4,P5)=(W1,W2,W3,W4,W5)=W=(1,2,10,100,1000) 第三个元素 M=1112 P=(P1,P2,P3,P4,P5)=(W1,W2,W3,W4,W5)=W=(1,2,10,100,1000) 第四个元素 M=1112 P=(P1,P2,P3,P4,P5)=(W1,W2,W3,W4,W5)=W=(1,2,10,100,1000) 第四个元素 M=1112 P=(P1,P2,P3,P4,P5)=(W1,W2,W3,W4,W5)=W=(1,2,10,100,1000) 第五个元素 M=1112 10,W，只有一个 P,20，只有一个 原来的背包实例{P1,P2,…,Pn}，{W1,W2,…,Wn} 变成新的背包实例{q1,q2,…,qn}，{W1,W2,…,Wn} 最小单位价值 每个qi都是LB??/n整数倍 背包容量保持不变。 q1,q2,…,qr p1,p2,…,pr q1,q2,…,qn p1,p2,…,pn {P1,…,Pn,W1,…,Wn}的最优解元素下标集合：R {q1,…,qn,W1,…,Wn}的最优解元素下标集合：R’ 得到的解的价值为 ? P*(I’) p1, p2, …, pn q1, q2, …, qn r1, r2, …, rn 最小优化问题 BoundOPT(I)可以多项式时间得到，算法A得到的解值A(I) BoundOPT(I)/A(I)?r，则OPT(I)/A(I) ?r 最大优化问题 例如背包问题： 按照价值/重量由大到小顺序装入背包， 到第一个不能装入的元素为止， 所有元素价值之和是最优解的一个界。 下面举个例子，顶点覆盖Vertex Cover 近似算法，近似性能比为2， 1C=? 2任意选择一条边(u,v)，选择其中两个顶点加入到C=C?{u,v} 3删除G中以u或v为端点的边 4重复2，3直到没有变可选择。 5输出C 上次内容： (1)图着色不能多项式时间近似到小于，TSP问题不能多项式时间近似