近似算法

维基百科,自由的百科全书
跳转至: 导航搜索

近似算法计算机科学算法研究的一个重要方向。所谓“近似”,就是指结果不一定是最优的,但是也在可以承受的范围内,而且可以比精确求解消耗更少的资源。这里的资源是计算复杂性理论中的标准,可以是时间,空间或者询问次数等。

背景[编辑]

在计算复杂性理论中的某些假设下,比如最著名的P\neq NP假设下,对于一些可已被证明为NP完全的优化问题,无法在多项式时间内精确求到最优解,然而在现实或理论研究中,这类问题都有广泛的应用,在精确解无法得到的情况下,转而依靠高效的近似算法求可以接受的近似解。近似算法的研究也是当今计算机科学研究的一个主要方向。

近似比[编辑]

对于一个最大化问题的实例,设其最优解是OPT,某个近似算法的解是x,若下式成立,

\alpha\cdot OPT\le x\le OPT

其中0<\alpha<1则定义此近似算法的近似比为\alpha

相应的,对于一个最小化问题的实例,设其最优解是OPT,某个近似算法的解是x,若下式成立,

OPT\le x\le \alpha\cdot OPT

其中\alpha>1则定义此近似算法的近似比为\alpha

分类[编辑]

按照可以达到近似比的不同,可以将近似算法大致按以下分类:

  1. FPTAS
  2. PTAS
  3. 常数近似
  4. 对数的多项式
  5. 多项式

其中对数的多项式和多项式都是对应于输入规模的。

设计方法[编辑]

近似算法的常用设计方法有贪心法线性规划半正定规划松弛和取整随机算法等。

近似的困难性[编辑]

对于一些问题,近似算法的近似比也会有一定的局限性,一个最大化问题(最小化问题类似)最好的近似算法可以达到的近似比不能比某个特定的值更高。20世纪90年代发展起来的PCP理论为证明近似的困难性提供了一套系统的工具。例如,对于常见的MAX3SAT问题,一个简单的随机算法可以满足7/8的子句,但是可以证明,找到一个能保证满足高于7/8+\epsilon(\forall\epsilon>0)比例子句的问题是NP困难的。所以在P\neq NP的假设下,这个问题我们可以得到的最优近似比是7/8。进入21世纪之后,计算机科学家为了近似困难性更往前一步,提出了唯一性游戏假设,在这一假设下,一些重要的问题如MAX-CUTMAX2SAT也被证明了可能达到的最优近似比。