近似算法

引言

近似算法是一种解决NP完全问题的优化问题的方法。这种技术不能保证找到最佳解决方案。近似算法的目标是在合理的时间内（最多是多项式时间）尽可能接近最优值。这种算法被称为近似算法或启发式算法。

• 对于旅行商问题，优化问题是找到最短的循环，近似问题是找到一个短的循环。
• 对于顶点覆盖问题，优化问题是找到包含最少顶点的顶点覆盖，近似问题是找到一个包含少量顶点的顶点覆盖。

性能比率

假设我们正在处理一个优化问题，每个解决方案都有一个成本。近似算法返回一个合法的解决方案，但该合法解决方案的成本可能不是最优的。

例如，假设我们正在考虑一个最小顶点覆盖（VC）。一个近似算法为我们返回一个VC，但大小（成本）可能没有最小化。

另一个例子是我们正在考虑一个最大独立集（IS）。一个近似算法为我们返回一个IS，但大小（成本）可能不是最大的。设 C 为近似算法返回的解决方案的成本，C* 为最优解决方案的成本。

我们说近似算法对于输入大小 n 具有近似比 P (n)，其中

直观地说，近似比衡量近似解与最优解的差别。一个大的（小的）近似比表明解比最优解差很多（或大致相同）。

请注意，如果比率不依赖于 n，则 P (n) 始终 ≥ 1，我们可以写成 P。因此，1-近似算法给出了最优解。有些问题具有小常数近似比的多项式时间近似算法，而其他问题具有其近似比随 n 增长的已知的最佳多项式时间近似算法。