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