设计与分析 - 近似算法

近似算法是旨在解决在多项式时间内无法求解近似解的问题的算法。这些问题被称为 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，则表示近似算法生成精确的最优解。

近似算法的几个流行例子是 -