近似算法.doc

近似算法所有已知的解决NP-难问题算法都有指数型运行时间。但是,如果我们要找一个“好”解而非最优解,有时候多项式算法是存在的。给定一个最小化问题和一个近似算法,我们按照如下方法评价算法:首先给出最优解的一个下界,然后把算法的运行结果与这个下界进行比较。对于最大化问题,先给出一个上界然后把算法的运行结果与这个上界比较。近似算法比较经典的问题包括:最小顶点覆盖、旅行售货员问题、集合覆盖等。迄今为止,所有的NP完全问题都还没有多项式时间算法。对于这类问题,通常可采取以下几种解题策略。(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*]<=ε(n),则称ε(n)为该近似算法的相对误差界。近似算法的性能比ρ(n)与相对误差界ε(n)之间显然有如下关系:ε(n)≤ρ(n)-1。顶点覆盖问题的近似算法V,使得若(u,v)是G的一条边,则v∈V’或u∈V’。顶点覆盖V’的大小是它所包含的顶点个数|V’|。Í 问题描述:无向图G=(V,E)的顶点覆盖是它的顶点集V的一个子集V’VertexSetapproxVertexCover(Graphg) {cset= e1=;{ while(e1!= 从e1中任取一条边(u,v); cset=cset∪{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。旅行售货员问题近似算法问题描述:旅行商问题(简称TSP)又名货郎担问题,是著名的组合优化问题。问题是这样提出的:某售货员要到若干个城市去推销商品,已知各城市间的路程(或旅费),要求选定一条从驻地出发,经过每个城市恰好一次,最后回到驻地的路线,使总的路程(或旅费)最小。给定一个完全无向图G=(V,E),其每一边(u,v)∈E有一非负整数费用c(u,v)。要找出G的最小费用哈密顿回路。 TSP旅行商问题三种近似算法近似算法1 - 邻近点法 任一顶点出发,在每次到达的顶点处,选择最近的未经历点前行,直至历遍所有顶点后回到出发点,复杂度为O(n^2).近似算法2 - 最小生成树法  先求出完全图的最小生成树T,给每条边添加一条重边,使其成为Euler图,沿Euler闭迹历遍所有顶点,当遇到已访问的顶点,不重复记录,最终得到一个Hamilton图,(Prim算法和Fleury算法)复杂度为O(n^2).近似算法3 - 最小权匹配法  用"最小生