近似算法与随机化算法

《近似算法与随机化算法》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、近似算法与随机化算法近似算法基本概念所有已知的解决NP-难问题算法都有指数型运行时间。但是，如果我们要找一个"好"解而非最优解，有时候多项式算法是存在的。给定一个最小化问题和一个近似算法，我们按照如下方法评价算法：首先给出最优解的一个下界，然后把算法的运行结果与这个下界进行比较。对于最大化问题，先给出一个上界然后把算法的运行结果与这个上界比较。近似算法比较经典的问题包括：最小顶点覆盖、旅行售货员问题、集合覆盖等。迄今为止，所有的NP完全问题都还没有多项式时间算法。对于这类问题，通常可采取以下几种解

2、题策略。(1)只对问题的特殊实例求解(2)用动态规划法或分支限界法求解(3)用概率算法求解(4)只求近似解(5)用启发式方法求解若一个最优化问题的最优值为c*，求解该问题的一个近似算法求得的近似最优解相应的目标函数值为c，则将该近似算法的性能比定义为max(c/c*,c*/c)。在通常情况下，该性能比是问题输入规模n的一个函数ρ(n)，即max(c/c*,c*/c)=ρ(n)。该近似算法的相对误差定义为Abs[(c-c*)/c*]。若对问题的输入规模n，有一函数ε(n)使得Abs[(c-c*)/c

3、*]=ε(n)，则称ε(n)为该近似算法的相对误差界。近似算法的性能比ρ(n)与相对误差界ε(n)之间显然有如下关系：ε(n)≤ρ(n)-1。顶点覆盖问题的近似算法问题描述：无向图G=(V,E)的顶点覆盖是它的顶点集V的一个子集V'V，使得若(u,v)是G的一条边，则v∈V'或u∈V'。顶点覆盖V'的大小是它所包含的顶点个数

4、V'

5、。VertexSetapproxVertexCover(Graphg){cset=；e1=g.e；while(e1！=){从e1中任取一条边(u,v)；cset=cse

6、t∪{u,v}；从e1中删去与u和v相关联的所有边；}returnc}Cset用来存储顶点覆盖中的各顶点。初始为空，不断从边集e1中选取一边(u,v)，将边的端点加入cset中，并将e1中已被u和v覆盖的边删去，直至cset已覆盖所有边。即e1为空。图(a)~(e)说明了算法的运行过程及结果。(e)表示算法产生的近似最优顶点覆盖cset，它由顶点b,c,d,e,f,g所组成。(f)是图G的一个最小顶点覆盖，它只含有3个顶点：b,d和e。旅行售货员问题近似算法问题描述：给定一个完全无向图G=(V,E

7、)，其每一边(u,v)∈E有一非负整数费用c(u,v)。要找出G的最小费用哈密顿回路。旅行售货员问题的一些特殊性质：比如，费用函数c往往具有三角不等式性质，即对任意的3个顶点u,v,w∈V，有：c(u,w)≤c(u,v)+c(v,w)。当图G中的顶点就是平面上的点，任意2顶点间的费用就是这2点间的欧氏距离时，费用函数c就具有三角不等式性质。对于给定的无向图G，可以利用找图G的最小生成树的算法设计找近似最优的旅行售货员回路的算法。voidapproxTSP(Graphg){(1)选择g的任一顶点r；

8、(2)用Prim算法找出带权图g的一棵以r为根的最小生成树T；(3)前序遍历树T得到的顶点表L；(4)将r加到表L的末尾，按表L中顶点次序组成回路H，作为计算结果返回；}当费用函数满足三角不等式时，算法找出的旅行售货员回路的费用不会超过最优旅行售货员回路费用的2倍。(b)表示找到的最小生成树T；(c)表示对T作前序遍历的次序；(d)表示L产生的哈密顿回路H；(e)是G的一个最小费用旅行售货员回路。一般的旅行售货员问题在费用函数不一定满足三角不等式的一般情况下，不存在具有常数性能比的解TSP问题的多

9、项式时间近似算法，除非P=NP。换句话说，若P≠NP，则对任意常数ρ1，不存在性能比为ρ的解旅行售货员问题的多项式时间近似算法。集合覆盖问题的近似算法问题描述：给定一个完全无向图G=(V,E)，其每一边(u,v)∈E有一非负整数费用c(u,v)。要找出G的最小费用哈密顿回路。集合覆盖问题的一个实例〈X,F〉由一个有限集X及X的一个子集族F组成。子集族F覆盖了有限集X。也就是说X中每一元素至少属于F中的一个子集，即X=。对于F中的一个子集CF，若C中的X的子集覆盖了X，即X=，则称C覆盖了X。集合覆

10、盖问题就是要找出F中覆盖X的最小子集C*，使得

11、C*

12、=min{

13、C

14、

15、CF且C覆盖X}集合覆盖问题举例：用12个黑点表示集合X。F={S1,S2,S3,S4,S5,S6,}，如图所示。容易看出，对于这个例子，最小集合覆盖为：C={S3,S4,S5,}。集合覆盖问题近似算法--贪心算法SetgreedySetCover(X,F){U=X；C=；while(U！=){选择F中使

16、S∩U

17、最大的子集S；U=U-S；C=C∪{S}；}returnC；}算法的循环体最多执行min{

18、X

19、，