近似演算法

Table of content

近似演算法是為解決在多項式時間內無法求解的問題而設計的演算法，以獲得近似解。這些問題被稱為NP完全問題。這些問題對於解決現實世界中的問題非常有效，因此，使用不同的方法來解決它們變得很重要。

NP完全問題仍然可以在三種情況下得到解決：輸入可能非常小，以至於執行時間減少了；某些問題仍然可以分類為可以在多項式時間內解決的問題；或者使用近似演算法為問題找到接近最優的解。

這導致了近似問題效能比的概念。

效能比率

計算近似演算法的效能比（也稱為近似比）背後的主要思想是找到近似解與最優解的接近程度。

近似比用ρ(n)表示，其中n是演算法的輸入大小，C是演算法獲得的近似最優解，C*是問題的最優解。當且僅當滿足以下條件時，演算法的近似比為ρ(n)：

$$max\left\{\frac{C}{C^{\ast} },\frac{C^{\ast }}{C} \right\}\leq \rho \left ( n \right )$$

然後該演算法被稱為ρ(n)-近似演算法。近似演算法可以應用於兩種型別的最佳化問題：最小化問題和最大化問題。如果問題的最優解是找到最大成本，則該問題被稱為最大化問題；如果問題的最優解是找到最小成本，則該問題被稱為最小化問題。

對於最大化問題，近似比由C*/C計算，因為0 ≤ C ≤ C*。對於最小化問題，近似比由C/C*計算，因為0 ≤ C* ≤ C。

假設近似演算法的成本都是正數，則效能比是明確定義的，並且不會小於1。如果值為1，則表示近似演算法生成了精確的最優解。

一些流行的近似演算法示例包括：

列印頁面