最近的工作内容涉及到寻找一类问题的近似算法。总感觉应该把现有的比较经典的近似算法学习一下。这篇文章是算法导论第35章近似算法的笔记。主要讲解了顶点覆盖问题、旅行商问题、集合覆盖问题、随机化与线性规划以及子集合问题。

算法导论之近似算法

对于NPC问题，我们不知道如何在多项式时间内取得最优解。但是我们可以寻找一些能够在多项式时间内得到近似最优解的方法。这种返回近似最优解的算法就叫做近似算法。

近似算法的性能比

如果对于规模为n的任意输入，近似算法所产生的近似解的代价C和最优解的代价C*只差一个因子$\rho(n)$:

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

则称该近似算法有近似比$\rho(n)$。如果一个算法的近似比达到$\rho(n)$, 则称该算法为$\rho(n)$ 近似算法。