本文概述
- 介绍
- 绩效比率
- 对于旅行推销员问题, 优化问题是找到最短周期, 而近似问题是找到短周期。
- 对于顶点覆盖问题, 优化问题是找到顶点最少的顶点覆盖, 而近似问题是找到顶点很少的顶点覆盖。
例如, 假设我们正在考虑最小尺寸的顶点覆盖(VC)。近似算法会为我们返回VC, 但是大小(成本)可能不会最小化。
另一个示例是我们正在考虑最大大小的独立集(IS)。近似算法会为我们返回一个IS, 但是大小(成本)可能不是最大。令C为近似算法返回的解的成本, 而C *为最优解的成本。
我们说近似算法对于输入大小n具有近似比率P(n), 其中
文章图片
直觉上, 近似比衡量近似解与最优解的区别。大的(小的)逼近比衡量该解决方案比最优解决方案(或多或少与最佳解决方案)差得多。
【NP优化(近似算法)】观察到P(n)始终≥1, 如果该比率不依赖于n, 我们可以写成P。因此, 采用1-近似算法可以得出最佳解。一些问题采用了具有较小恒定近似比率的多项式时间近似算法, 而另一些问题则采用了众所周知的多项式时间近似算法, 其近似比率随n增长。