07-近似算法.ppt

* 近似算法 Approximation Algorithms * 近似算法 迄今为止，所有的NP完全问题都还没有多项式时间算法。对于这类问题，通常可采取以下几种解题策略。 (1)只对问题的特殊实例求解 (2)用动态规划法或分支限界法求解 (3)用概率算法求解 (4)只求近似解 (5)用启发式方法求解 本章主要讨论解NP完全问题的近似算法。 主要内容 近似算法的性能定义 顶点覆盖问题 旅行售货商(TSP)问题 子集和问题 近似方案：(完全)多项式近似方案 * * 1 近似算法的性能 若一个最优化问题的最优值为c*，求解该问题的一个近似算法求得的近似最优解相应的目标函数值为c，则将该近似算法的性能比定义为?= 。在通常情况下，该性能比是问题输入规模n的一个函数ρ(n)。 该近似算法的相对误差定义为?= 。若对问题的输入规模n，有一函数ε(n)使得 ≤ε(n)，则称ε(n)为该近似算法的相对误差界。 近似算法的性能比ρ(n)与相对误差界ε(n)之间有如下关系：ε(n)≤ρ(n)-1。 * 2 顶点覆盖问题的近似算法 问题描述：无向图G=(V,E)的顶点覆盖是它的顶点集V的一个子集V’?V，使得若(u,v)是G的一条边，则v∈V’或u∈V’。顶点覆盖V’的大小是它所包含的顶点个数|V’|。 顶点覆盖问题：找最小顶点覆盖。 VertexSet ApproxVertexCover ( Graph G ) { Cset=?； E1=E； while (E1 != ?) { 从E1中任取一条边e=(u,v)； Cset=Cset∪{u,v}； 从E1中删去与u和v相关联的所有边； } return Cset } Cset用来存储顶点覆盖中的各顶点。初始为空，不断从边集E1中选取一边(u,v)，将边的端点加入Cset中，并将E1中已被u和v覆盖的边删去，直至Cset已覆盖所有边。即E1为空。 * 2 顶点覆盖问题的近似算法 图(a)～(e)说明了算法的运行过程及结果。(e)表示算法产生的近似最优顶点覆盖Cset，它由顶点b,c,d,e,f,g所组成。 (f)是图G的一个最小顶点覆盖，它只含有3个顶点：b,d和e。 算法approxVertexCover的性能比为2。（c=6，c*=3） * 近似比: 2-Approximation Theorem. Algorithm ApproxVertexCover is a 2-approximation algorithm. Pf. Let A denote the set of edges that were picked by Algorithm ApproxVertexCover. Let C* be an optimal vertex cover. Then, C* must include at least one endpoint of each edge in A. Since no two edges in A share an endpoint, no two edges in A are covered by the same vertex from C*. Hence we have the lower bound C* ≥ |A|. On the other hand, the algorithm picks an edge for which neither of its endpoints is already in C. Then |C| = 2|A| Hence, |C| = 2|A|?≤ 2|C*|. * Vertex cover: summary No better constant-factor approximation is known!! More precisely, minimum vertex cover is known to be approximable within (for a given |V|≥2) (ADM85) but cannot be approximated within 7/6 (Hastad STOC97) for any sufficiently large vertex degree, Dinur Safra (STOC02)1.36067 * Vertex cover: summary Eran Halperin, Improved Approximation Algorithms for the Verte