Lecture12-近似算法.ppt

近似算法 高文宇 gwyy@163.com 近似算法 一些NP完全问题存在多项式时间的近似算法，通过消耗越来越多的计算时间，这些近似算法可以达到不断缩小的近似比。也就是说，在计算时间和近似质量之间可以进行权衡，如子集和问题。 相关定义 定义1. 图G=(V,E)称为简单连通无向图，需满足以下条件： （1）G为无自回路的、连通的无向图。 （2）G中任意两个节点之间至多有一条边。 定义2. 图中节点u和节点v之间存在一条边，则称节点与节点相邻。 定义3. 图中的任意节点u，称u在图中的相邻节点的个数为节点u的度数，记为d(u)。 定义4. 点覆盖集。 点覆盖问题 Vertex Cover: 在给定图中找出最小点覆盖。 点覆盖的贪心算法 每次在剩余图中选择度最大的节点。 贪心策略不一定得到最好结果 例如在下图中每次选择度大的节点将得到一个大小为5的点覆盖集，而最优解只需4个节点即可。 点覆盖的另一个近似算法 2-近似 APPROX-VERTEX-COVER(G) 1 C ← ? 2 E′ ← E[G] 3 while E′ ≠ ? 4 do let (u, v) be an arbitrary edge of E′ 5 C ← C ∪ {u, v} 6 remove from E′ every edge incident on either u or v 7 return C APPROX-VERTEX-COVER 算法执行过程 APPROX-VC是2-近似算法 定理： APPROX-VC是2-近似算法。 点覆盖的思考题 ? 35.1-3: Professor Nixon 提出使用贪心策略来求最小点覆盖，即每次选择度最大的节点。请给出一个例子说明这种策略达不到近似比2。(Hint: Try a bipartite graph with vertices of uniform degree on the left and vertices of varying degree on the right.) 35.1-4: 设计一个贪心算法，在线性时间内找出一棵树的最小点覆盖。 35.1-5: 从定理 Theorem 34.12的证明可知，点覆盖和团问题在某种意义上是互补的，即最小点覆盖是补图中某一最大团的补。 这种关系是否意味着存在一个多项式的近似算法，它对团问题有着固定的近似比？ 关于点覆盖的开放问题 对于点覆盖，存在近似比小于2的近似算法吗？ 连通支配集问题 Connected Dominating Set. 连通支配集. 设图G=(V,E)是简单连通无向图，若节点集S是V的子集，S ≠ ?，对任意节点u∈V-S，u都与S中至少一个节点相邻，则称S是图G的支配集。若由S导出的子图为连通图，则S为连通支配集。 在应用领域，我们通常希望求解最小CDS，即求得的CDS包含的节点数最少。然而，无论是求解最小支配集或最小CDS都是NP难问题，因此我们只能采用一些近似算法来求解这个问题。 连通支配集的贪心算法 每次考虑度大的节点 同时还需考虑连通性 对偶的概念 多叶子生成树 连通支配集的难度 尚未找到常数近似度的近似算法。 支配集比点覆盖“更难”。 旅行商问题 Traveling-salesman 旅行商问题：给定一个完全无向图G，每条边用一非负权值表示代价，如何找出G的一个具有最小代价的哈密尔顿回路。 TS问题是NP完全的，即使限定其代价函数满足三角不等式。 三角不等式 三角不等式，triangle inequality ：对所有节点 u, v, w ∈ V,有： c(u, w) ≤ c(u, v) + c(v, w). 则称代价函数 c 满足三角不等式。 在很多应用中，三角不等式自动满足，例如图的顶点为平面上的点，顶点间的旅行代价为顶点间的欧几里德距离。 满足三角不等式的TS问题 求解思路 （1）求出一棵MST，MST的权值就是最低费用旅行线路的费用值的下界。 （2）对MST进行先序遍历，所得节点序列即为TS巡游序列。 算法 APPROX-TSP-TOUR(G, c) 1 select a vertex r ∈ V [G] to be a root vertex 2 compute a minimum spanning tree T for G from root r using MST-PRIM(G, c, r) 3 let L be the list of vertices visited in a preorder tree walk of T 4 return the hamiltonian cycle H that visits the v