多项式时间近似算法 在计算机科学领域多项式时间近似算法PTAS是一种用于优化问题最常见的是NPhard优化问题的近似算法 PTAS使用一个大于的参数 ε产生一个对于最小化问题能在   ε 倍最优解内的解决方案或最大化问题的   ε 倍例如对于欧几里得旅行商问题现有的最好PTAS 将产生一个长度最多为   ε L 的解其中L是最短行程的长度 ε的大小越小PTAS的近似性能比越靠近也即说明这个PTAS的计算结果越接近最优解 对于一个固定大小的εPTAS 的运行时间必须是对于问题大小多项式的例如对于一个原时间复杂度为On的算法它的PTAS时间复杂度可以为Onk其中k为参数但对于不同的 ε可以是不同的时间复杂度为Onε 甚至Onexpε 的算法同样属于 PTAS