近似比（approximation ratio）

有些最佳化問題是 NP 困難的：我們不知道有任何多項式時間演算法能永遠找到絕對最佳的答案，而且很可能根本不存在。與其無止盡地等待完美，我們退而求其次，要一個快速、而且承諾「夠接近」的演算法。近似比正是「夠接近」到底有多近的精確說法：它衡量在最壞情況下，演算法的答案最多會偏離真正最佳解多遠。

把它講精確。令 OPT 為某個實例最佳解的值，ALG 為演算法實際回傳的值。對最小化問題（我們希望成本小），近似比是所有實例上 ALG / OPT 的最大可能值；比值為 2 表示演算法回傳的成本永遠不超過最佳值的兩倍。對最大化問題（我們希望值大），近似比是 OPT / ALG 的最大可能值，所以比值 2 表示演算法回傳的值永遠不少於最佳值的一半。兩種情況下，比值都是一個不小於 1 的數，越接近 1 的演算法越好；剛好等於 1 表示它永遠最佳。最關鍵的是，這個比值是對「每一個」輸入的最壞情況承諾——它不是你平常看到的平均落差。

為何要費力證一個比值？因為沒有它，一個啟發式方法可能在你試過的例子上看起來很好，卻在某些對手刻意構造的輸入上慘敗。一個證明過的近似比是「無論來什麼輸入都成立」的保證，而這正是 NP 困難問題在多項式時間內否則給不出的那種穩健性。誠實的提醒：這個比值描述的是「最壞情況」。一個「2 近似」在真實資料上通常比兩倍好得多；那個 2 是安全上限，不是典型結果。而且好的比值仍不代表你找到了最佳解——它代表你與最佳解之間有一段受控、可證的距離。