近似算法
近似算法
近似算法是为解决那些无法在多项式时间内得到近似解的问题而设计的算法。这类问题被称为NP完全问题。这些问题对于解决现实世界中的问题非常有效，因此，使用不同的方法来解决它们变得非常重要。
NP完全问题在三种情况下仍然可以解决：输入可能非常小，从而减少执行时间；某些问题仍然可以归类为可以在多项式时间内解决的问题；或者使用近似算法找到问题的近似最优解。
这引出了近似问题性能比的概念。
性能比
计算近似算法的性能比（也称为近似比）的主要思想是确定近似解与最优解的接近程度。
近似比用ρ(n)表示，其中n是算法的输入大小，C是近似最优解通过算法得到，C* 即为问题的最优解。该算法的近似比为 ρ(n) 当且仅当 −
$$max\left\{\frac{C}{C^{\ast} },\frac{C^{\ast }}{C} ight\}\leq ho \left ( n ight )$$
该算法称为 ρ(n)-近似算法。近似算法可应用于两类优化问题：最小化问题和最大化问题。如果问题的最优解是求最大成本，则该问题称为最大化问题；如果问题的最优解是求最小成本，则该问题称为最小化问题。
对于最大化问题，近似比通过 C*/C 计算，因为 0 ≤ C ≤ C*。对于最小化问题，近似比由 C/C* 计算，因为 0 ≤ C* ≤ C。
假设近似算法的成本均为正，则性能比定义明确，且不会小于 1。如果值为 1，则表示近似算法生成了精确的最优解。
示例
一些流行的近似算法示例是 −
子集和问题
