第九章approximationalgorithm

第九章approximationalgorithm内容摘要：

F)H(X)lnX+1. 复杂性分析 HIT CSamp。 E The Travelingsalesman Problem 问题的定义 近似算法设计 算法的性能分析 HIT CSamp。 E 问题的定义 • 输入 完全无向图 G=(V,E)。 代价函数 C: E→ 非负整数集合 C满足 三角不等式 : C(u,w)C(u,v)+C(v,w). • 输出 具有最小代价的 Hamilton环 • Hamilton环是一个包含 V中每个结点一次的简单环 . • 代价函数的扩展 : 设 AE, C(A)=(u,v)E C(u, v). • 不满足三角不等式的 TSP问题无具有 常数 Ration Bound的近似算法 , 除非 NP=P. HIT CSamp。 E • 基本思想 – 首先构造最小生成树 (可以使用第五章的算法 ) – 先序遍历最小生成树 , 构造 TSP的解 近似算法的设计 a d e b f g h c 先序遍历 : abchdefga a d e b f g h c 先序遍历解 优化解 d e b c g f h a HIT CSamp。 E • 近似算法 APPROXTSPTOUR(G,C) 1. 选择一个 rV[G]作为生成树的根。 2. 调用 MSTPrim(G, C, r)生成一个最小生成树 T。 3. 先序遍历 T, 形成有序结点表 L。 4. 按照 L中的顺序访问各结点 , 形成哈密顿环 . HIT CSamp。 E 算法的性能分析 • 时间复杂性 第 2步 : O(|E|+|V|log|V|)=O(|V|2+|V|log|V|)=O(|V|2) 第 3步 : O(|E|)=O(|V|2), 因为 G是完全图 , 第 4步 : O(|V|) T(G)=O(|V|2) HIT CSamp。 E • 解的精确度 定理 1. APPROXTSPTOUR具有 Ratio Bound 2. 证 . 设 H*是 TSP问题的优化解 , H是算法产生的近似解 .我们需要证明 C(H)2C(H*). 从 H*中删除任意一条边 , 可以得到 G的一个生成树 T’. 设 T是算法第 2步产生的导致 H的最小生成树 , 则 C(T)C(T39。 )C(H*). T的一个 full walk W列出了所有结点 (第一次访问的和 以后从一个子树返回时再访问的 ). 前面例子的 full walk给 出顺序 : a,b,c,b,h,b,a,d,e,f,e,g,e,d,a HIT CSamp。 E 由于 W通过每条边两次 , C(W)=2C(T), 进而 C(W)2C(H*). W不是哈密顿环 , 因为它通过某些结点多于一次 . 根据三角不等式 , 我们可以从 W中删除对一个结点的 任何 访问 , 而不增加代价 . (例如 ： 从 u→ v→ w 删除 v得 u→ w) 反复地应用上述操作 , 我们可以从 W中删除所有对任何结 点的非第一次访问 , 得到一个算法中的 preoder walk. 在我们的例子中 , 操作结果是 : a, b, c, h, d, e, f, g. 由于 T的 preoder walk导致 H, 我们有 C(H)C(W), 即 C(H)2C(H*), 明所欲证 . HIT CSamp。 E Randomization and Linear Programming 求解 Max3CNF问题随机近似算法 求解最小节点覆盖问题的线性规划算法 HIT CSamp。 E • 基本概念 定义 1. 设 C是随机近似算法 RAS产生的问题 P的 近似 解的代价 , C*是问题 P的准确解的代价 , n是 P 的大小 . 若 max(C/C*, C*/C)p(n), 则称 RSA 具有近似比 p(n). 我们也称 RAS是一个随机 p(n)近似算法 . 求解 Max3CNF问题随机近似算法 HIT CSamp。 E • Max3CNF问题的定义 输入 : 合取范式 CNF, 每个析取式具有三个变量 , 没有任何变量和它的非在同一个析取式中 输出 : 一个变量赋值 ,最大化值为 1的析取式个数 • 随机算法 RandomMax3CNF(CNF) 1. For 对于 CNF中的每个变量 x Do 2. 随机地为 x赋值 : x =0的概率为 1/2, x =1的概率为 1/2。 3. Return. HIT CSamp。 E • 性能分析 定理 . RandomMax3CNF是一个随机 8/7近似算法 . 证 . 假定输入 CNF中具有 n个变量 , m个析取式 , 第 i个析取式的形式为 xi1xi2xi3. 对 i=1, 2,… , m, 定义随机变量 : Yi=1 如果第 i个析取式为 1, 否则 Yi=0. Pr(第 i个析取式为 0)=Pr(xi1=0)Pr(xi2=0)Pr(xi3=0)=(1/2)3=1/8. Pr(第 i个析取式为 1)=1 1/8 = 7/8. E[Yi]=7/8. 令 Y=Y1+Y2+… +Ym. Y是 CNF中值为 1的析取式的个数 . E[Y]=1imE[Yi]=1im7/8=m7/8. 显然 , 优化解的代价为 m. 于是近似比 =m/(m7/8)=8/7 . HIT CSamp。 E • 问题的定义 – 输入 : 无向图 G=(V, E), 每个节点具有权 w(v). – 输出 : CV, 满足 (1). (u, v)E, uC或者 vC。