近似算法

在计算机科学和运筹学中，近似算法（英語：Approximation algorithm）是指能为最优化问题寻找近似解的算法，该类算法找到的近似解与最优解之间的差值需能证明不超过某个值。由于人们普遍猜测P≠NP，许多优化问题因此无法在多项式时间内得到精确解决。进而，理論計算機科學领域内自然而然地出现了试图在多项式时间复杂度内得到近似最优解的近似算法。在绝大多数情况下，近似算法得到的近似值位于最优解到最优解乘以某个特定的值之间，这个特定的值被称作近似比。不过，也有一些算法得到的近似值是在最优解到最优解加某个特定的值之间。 近似算法的设计及分析过程中都包含一系列的数学证明，以保证其最差情况效率仍可接受。这点也是它与模拟退火等启发式算法之间的不同之处，启发式算法通常能够找到一个比较好的近似解，但其设计及分析之初往往并不涉及最差情况效率的证明。