NP优化(近似算法)

本文概述

  • 介绍
  • 绩效比率
介绍 近似算法是解决NP优化问题的一种方法。此技术不能保证最佳解决方案。近似算法的目标是在最长时间后的合理时间内, 尽可能地接近最佳值。这样的算法称为近似算法或启发式算法。
  • 对于旅行推销员问题, 优化问题是找到最短周期, 而近似问题是找到短周期。
  • 对于顶点覆盖问题, 优化问题是找到顶点最少的顶点覆盖, 而近似问题是找到顶点很少的顶点覆盖。
绩效比率 假设我们在一个优化问题上工作, 其中每个解决方案都会带来成本。近似算法返回合法解决方案, 但是该合法解决方案的成本可能不是最优的。
例如, 假设我们正在考虑最小尺寸的顶点覆盖(VC)。近似算法会为我们返回VC, 但是大小(成本)可能不会最小化。
另一个示例是我们正在考虑最大大小的独立集(IS)。近似算法会为我们返回一个IS, 但是大小(成本)可能不是最大。令C为近似算法返回的解的成本, 而C *为最优解的成本。
我们说近似算法对于输入大小n具有近似比率P(n), 其中
NP优化(近似算法)

文章图片
直觉上, 近似比衡量近似解与最优解的区别。大的(小的)逼近比衡量该解决方案比最优解决方案(或多或少与最佳解决方案)差得多。
【NP优化(近似算法)】观察到P(n)始终≥1, 如果该比率不依赖于n, 我们可以写成P。因此, 采用1-近似算法可以得出最佳解。一些问题采用了具有较小恒定近似比率的多项式时间近似算法, 而另一些问题则采用了众所周知的多项式时间近似算法, 其近似比率随n增长。

    推荐阅读