近似算法

在计算机科学和运筹学中，近似算法（英语：Approximation algorithm）是指能为最优化问题寻找近似解的算法，该类算法找到的近似解与最优解之间的差值需能证明不超过某个值。由于人们普遍猜测P≠NP，许多优化问题因此无法在多项式时间内得到精确解决。进而，理论计算机科学领域内自然而然地出现了试图在多项式时间复杂度内得到近似最优解的近似算法。在绝大多数情况下，近似算法得到的近似值位于最优解到最优解乘以某个特定的值之间，这个特定的值被称作近似比。不过，也有一些算法得到的近似值是在最优解到最优解加某个特定的值之间。

近似算法的设计及分析过程中都包含一系列的数学证明，以保证其最差情况效率仍可接受。这点也是它与模拟退火等启发式算法之间的不同之处，启发式算法通常能够找到一个比较好的近似解，但其设计及分析之初往往并不涉及最差情况效率的证明。

背景

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

近似比

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

$\alpha \cdot OPT\leq x\leq OPT$

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

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

$OPT\leq x\leq \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-CUT、MAX2SAT也被证明了可能达到的最优近似比。

参见

• P/NP问题