Data Structures Algorithms 简明教程
Approximation Algorithms
Approximation Algorithms
近似算法是专为解决不能在多项式时间内求解以获得近似解的问题而设计的。这些问题被称为 NP 完全问题。这些问题对解决现实世界问题非常有效，因此，使用不同的方法来解决它们变得很重要。
NP 完全问题仍然可以在三种情况下得到解决：输入非常小以至于执行时间减少、某些问题仍然可以归类为可以在多项式时间内解决的问题，或者使用近似算法为问题找到近似最优解。
这就引出了近似问题的性能比率的概念。
Performance Ratios
计算近似算法的 performance ratio （也称为 approximation ratio ）背后的主要思想是找出近似解与最优解的接近程度。
近似比率用 ρ(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，则表示近似算法生成了精确的最优解。