查看“︁近似算法”︁的源代码

{{noteTA
|G1=IT
}}
在[[计算机科学]]和[[运筹学]]中，'''近似算法'''（{{lang-en|Approximation algorithm}}）是指能为[[最优化问题]]寻找近似解的算法，该类算法找到的近似解与最优解之间的差值需能证明不超过某个值<ref>{{cite book |author1-last=Cormen |author1-first=Thomas H.|author2-last=Leiserson |author2-first=Charles E. |author3-last=Rivest |author3-first=Ronald L. |author3-link=罗纳德·李维斯特 |author4-first=Clifford |author4-last=Stein |translator1=潘金贵 |translator2=顾铁成 |translator3=李成法 |translator4=叶懋 |title=[[算法导论]] |date=2006 |publisher=[[机械工业出版社]] |isbn=978-7-111-18777-6 |edition=原书第二版  |accessdate=2022-09-04 |language=zh-hans |pages=[https://archive.org/details/suanfadaolun0002unse/page/633 633]-634}}</ref><ref name="Bernard. 2011">{{Cite book|title=The design of approximation algorithms|last=Bernard.|first=Shmoys, David|date=2011|publisher=Cambridge University Press|isbn=9780521195270|oclc=671709856|url=http://www.designofapproxalgs.com/|access-date=2022-09-04|archive-date=2022-12-20|archive-url=https://web.archive.org/web/20221220124034/http://designofapproxalgs.com/|dead-url=no}}</ref>。由于人们普遍猜测[[P/NP问题|P≠NP]]，许多优化问题因此无法在多项式时间内得到[[精确算法|精确]]解决。进而，[[理論計算機科學]]领域内自然而然地出现了试图在多项式[[时间复杂度]]内得到近似最优解的近似算法。在绝大多数情况下，近似算法得到的近似值位于最优解到最优解乘以某个特定的值之间，这个特定的值被称作近似比。不过，也有一些算法得到的近似值是在最优解到最优解加某个特定的值之间。

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

== 背景 ==

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

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

<math>\alpha\cdot OPT\le x\le OPT</math>

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

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

<math>OPT\le x\le \alpha\cdot OPT</math>

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

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

# {{le|FPTAS|Fully polynomial-time approximation scheme}}
# [[多項式時間近似算法]]（PTAS）
# 常数近似
# [[对数的多项式]]
# [[多项式]]

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

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

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

== 參見 ==
*[[P/NP問題]]

==参考文献==
{{reflist}}

{{算法}}
{{Authority control}}
[[Category:近似演算法| ]]
[[Category:計算複雜性理論]]