近似算法

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，则表示近似算法生成了精确的最优解。

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

打印页面