NP优化：近似算法

本文概述

• 介绍
• 绩效比率

介绍

近似算法是解决NP优化问题的一种方法。此技术不能保证最佳解决方案。近似算法的目标是在最长时间后的合理时间内, 尽可能地接近最佳值。这样的算法称为近似算法或启发式算法。

• 对于旅行推销员问题, 优化问题是找到最短周期, 而近似问题是找到短周期。
• 对于顶点覆盖问题, 优化问题是找到顶点最少的顶点覆盖, 而近似问题是找到顶点很少的顶点覆盖。

绩效比率

假设我们在一个优化问题上工作, 其中每个解决方案都会带来成本。近似算法返回合法解决方案, 但是该合法解决方案的成本可能不是最优的。

例如, 假设我们正在考虑最小尺寸的顶点覆盖（VC）。近似算法会为我们返回VC, 但是大小（成本）可能不会最小化。

另一个示例是我们正在考虑最大大小的独立集（IS）。近似算法会为我们返回一个IS, 但是大小（成本）可能不是最大。令C为近似算法返回的解的成本, 而C *为最优解的成本。

我们说近似算法对于输入大小n具有近似比率P（n）, 其中

直觉上, 近似比衡量近似解与最优解的区别。大的（小的）逼近比衡量该解决方案比最优解决方案（或多或少与最佳解决方案）差得多。

观察到P（n）始终≥1, 如果该比率不依赖于n, 我们可以写成P。因此, 采用1-近似算法可以得出最佳解。一些问题采用了具有较小恒定近似比率的多项式时间近似算法, 而另一些问题则采用了众所周知的多项式时间近似算法, 其近似比率随n增长。