数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言
C++
C #
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会科学
时装学
法学多项式时间逼近规划
多项式时间近似方案
我们可以为 NP 完全问题，例如 0-1 背包问题或子集和问题，找到一些多项式时间的解决方案。这些问题在现实世界中非常普遍，因此必定有一些方法可以解决这些问题。
多项式时间近似方案 (PTAS) 是一种针对优化问题的算法近似类型。对于 0-1 背包问题，存在伪多项式解，但当值很大时，该解不可行。然后我们需要一个 PTAS 解决方案。
一些 NP 完全问题，例如图着色、K 中心问题等，没有已知的多项式时间解决方案。PTAS 用于逼近算法。这些算法取参数 ε> 0，并且为了逼近，我们将最小化 (1 + ε) 和最大化 (1 - ε)。
示例
例如，如果我们选择一个最小化问题并取 ε = 0.5，那么使用 PTAS 的解决方案几乎是 1.5。因此，运行时间一定是关于 n 的多项式，但它可以是关于 ε 的指数。
更新于：2020-06-17
837 次浏览
广告