近似演算法

在電腦科學和運籌學中，近似演算法（英語：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問題