第27篇讨论了贪心近似和局部搜索它们为集合覆盖和最大割分别给出了 O(logn)O(logn) 和 1/21/2 的近似比。这些常数或对数级别的近似比在许多应用中已经足够但当应用场景对精度要求极高时“常数近似”远远不够。我们能否做到任意接近最优具体而言能否设计一个算法对任意给定的精度参数 ε0ε0输出一个近似比不超过 (1ε)(1ε) 的解且运行时间在输入规模 nn 上保持多项式对于一部分NP困难问题答案是肯定的。这类算法被统称为多项式时间近似方案。但“多项式时间”这个限定词背后藏着微妙的差异算法是 nf(1/ε)nf(1/ε) 还是 f(1/ε)⋅nO(1)f(1/ε)⋅nO(1)前者当 εε 很小时会迅速膨胀到不可接受后者则始终保持对 nn 的线性或低次多项式依赖。这种差异将PTAS家族细分为不同等级也划定了不同问题的近似难度边界。一、PTAS、EPTAS与FPTAS的形式化定义设 ΠΠ 是一个最优化问题OPT(I)OPT(I) 为实例 II 的最优值。PTAS多项式时间近似方案若存在一个算法 AA对于任意实例 II 和任意 ε0ε0AA 在 ∣I∣O(1)∣I∣O(1) 时间内输出一个解其目标值满足 (1ε)(1ε)-近似比对于最小化问题或 (1−ε)(1−ε)-近似比对于最大化问题且 εε 以任意形式出现在指数中如 n1/εn1/ε则称 ΠΠ 具有PTAS。PTAS是三类方案中定义最宽松的一类——只要对每个固定的 εε 算法在 nn 上是多项式的即可但允许指数中含 1/ε1/ε。EPTAS高效多项式时间近似方案若PTAS的运行时间可写为 f(1/ε)⋅nO(1)f(1/ε)⋅nO(1)其中 ff 是任意可计算函数则称其为EPTAS。EPTAS要求 εε 与 nn 在复杂度中分离——nn 的指数不依赖于 εε。FPTAS完全多项式时间近似方案若EPTAS的运行时间进一步限制为 (1/ε)O(1)⋅nO(1)(1/ε)O(1)⋅nO(1)即关于 1/ε1/ε 也是多项式的则称其为FPTAS。这是三类方案中最强的一类——无论在 nn 上还是在 1/ε1/ε 上都是多项式的。三个层次的关系是FPTAS⊂EPTAS⊂PTASFPTAS⊂EPTAS⊂PTAS。强包含关系意味着某些问题具有PTAS但不具有EPTAS在标准复杂度假设下某些问题具有EPTAS但不具有FPTAS。这一分层为近似算法的精细分类提供了理论框架。二、背包问题的FPTAS动态规划与缩放01背包问题是展示FPTAS构造的经典案例。问题回顾nn 件物品物品 ii 的重量为 wiwi价值为 vivi背包容量为 WW求总价值最大的物品子集且总重量 ≤W≤W。在第7篇中我们给出了 O(nW)O(nW) 的动态规划但这是一个伪多项式时间算法——WW 可能是指数级。现在我们换一个DP方向令 dp[i][j]dp[i][j] 表示前 ii 件物品中选出总价值恰好为 jj 所需的最小重量。状态转移为 dp[i][j]min(dp[i−1][j],dp[i−1][j−vi]wi)dp[i][j]min(dp[i−1][j],dp[i−1][j−vi]wi)。复杂度 O(n⋅Vmax)O(n⋅Vmax)其中 Vmax∑viVmax∑vi 仍可能是指数级。FPTAS的关键思想是缩放与舍入将物品价值按比例缩小并舍入为整数从而压缩DP的状态空间同时保证缩放引入的误差可控。具体构造如下设 vmaxmaxivivmaxmaxivi。对于给定的 ε0ε0定义缩放因子 Kε⋅vmaxnKnε⋅vmax。对每件物品构造缩放后的价值 v~i⌊vi/K⌋v~i⌊vi/K⌋。在新的缩放实例上运行上述DP此时最大总价值 ≤n⋅(vmax/K)n2/ε≤n⋅(vmax/K)n2/εDP复杂度为 O(n3/ε)O(n3/ε)这是关于 nn 和 1/ε1/ε 的多项式。近似比分析设缩放实例的最优解为 S∗S∗原实例的真正最优解为 O∗O∗。在 S∗S∗ 中物品总价值的损失来源于舍入——每件物品最多损失 KK 的价值∣S∗∣≤n∣S∗∣≤n总损失 ≤nKε⋅vmax≤ε⋅OPT≤nKε⋅vmax≤ε⋅OPT。因此缩放解的价值 ≥OPT−ε⋅OPT(1−ε)OPT≥OPT−ε⋅OPT(1−ε)OPT。这正好满足最大化问题的 (1−ε)(1−ε) 近似比。背包问题的FPTAS存在性并非孤例。一个著名的定理给出了FPTAS存在的必要条件若一个NP困难的优化问题具有FPTAS则其判定版本必然存在伪多项式时间算法。强NP完全问题即使所有数值以一元表示仍为NP完全除非PNP否则不可能具有FPTAS。三、平面图最大独立集的PTAS分隔与递归背包问题的FPTAS依赖于数值缩放。但许多图论问题不存在FPTAS如最大独立集在一般图中甚至在特定复杂度假设下连EPTAS也不存在。然而当输入限制为平面图时最大独立集问题却具有PTAS。其构造思路与背包完全不同——利用平面图的几何分隔性质。平面图的核心结构性质是平面分隔定理Lipton-Tarjan, 1979任意 nn 个顶点的平面图可以在 O(n)O(n) 时间内找到一个大小为 O(n)O(n) 的顶点分隔集其移除后将图分解为两个大小至多为 2n/32n/3 的不连通子图。基于此可构造平面图最大独立集的PTAS。算法采用递归分治若当前图规模小于某个阈值依赖于 εε则暴力枚举求最优。否则找到大小为 O(k)O(k) 的分隔集kk 为当前顶点数将其移除得到若干互不连通的子图。对分隔集枚举其所有可能的独立子集至多 2∣S∣2∣S∣ 种每种选择固定后在剩余子图上递归求解。所有子图的解与分隔集所选顶点合并取最大值。设 T(n)T(n) 为运行时间。递归式为 T(n)≤2O(n)⋅2⋅T(2n/3)T(n)≤2O(n)⋅2⋅T(2n/3)。对于任意固定的 ε0ε0可通过在递归树上截断到深度 O(log(1/ε))O(log(1/ε)) 来平衡误差。最终算法的运行时间为 O(nO(1/ε))O(nO(1/ε))——这是典型的PTAS而非EPTAS因为 nn 的指数依赖于 εε。误差分析的核心是分隔集的大小随图规模增大而增大但在每一层递归中移除的顶点数仅占当前图规模的 O(1/k)O(1/k) 比例在最坏情况下被移除的顶点在最优解中的占比也被控制在这一量级。通过精心设置递归深度总近似比可严格达到 (1−ε)(1−ε)。平面图上的许多其他NP困难问题——最小顶点覆盖、最小支配集、最大割——同样可通过类似的分隔递归技术获得PTAS。这一方法论的普适性源于平面图的分隔结构NP困难的根源被限制在局部密集区域而平面分隔定理保证了这些区域可被有效隔离。四、PTAS的存在条件与不可能性并非所有NP困难问题都具有PTAS。是否存在PTAS取决于问题的内在难度结构。从正面看PTAS通常存在于以下情形问题具有伪多项式时间算法且非强NP完全存在FPTAS如背包问题。问题在某种几何或拓扑约束下如平面图、欧氏空间、单位圆图可借助分隔定理分解为近似独立的小实例存在PTAS或EPTAS。问题的最优解具有“渐近无后效性”可通过动态规划加缩放构造如调度问题。从反面看APX-难问题即存在常数 c1c1 使得 cc-近似已是NP困难一定不存在PTAS除非PNP。例如旅行商问题在一般图上是APX-难的最大SAT、集合覆盖不可优于 O(logn)O(logn)也属于此类。PCP定理的推论进一步精确刻画了许多问题的不可近似下界。五、总结与展望PTAS、EPTAS、FPTAS构成了近似算法精确度的三级阶梯。背包问题凭借数值缩放获得FPTAS平面图最大独立集借助几何分隔获得PTAS。两者的构造逻辑截然不同却共同展示了算法设计师在面对NP困难问题时的核心智慧不要硬碰困难本身而是寻找困难的“来源”将其隔离、压缩或缩放。并非所有问题都拥有PTAS——当问题被证明为APX-难时常数近似已经是最优的可能。下一篇我们将进入不可近似性理论的核心地带讨论PCP定理的直观含义以及它如何为大量NP困难问题划出精确的近似比下界——为什么最大3-SAT不能近似到任意接近1为什么团问题连有意义的近似都不可能。
【算法分析与设计】第28篇：多项式时间近似方案（PTAS）的基本构造
发布时间：2026/5/31 19:52:21
第27篇讨论了贪心近似和局部搜索它们为集合覆盖和最大割分别给出了 O(logn)O(logn) 和 1/21/2 的近似比。这些常数或对数级别的近似比在许多应用中已经足够但当应用场景对精度要求极高时“常数近似”远远不够。我们能否做到任意接近最优具体而言能否设计一个算法对任意给定的精度参数 ε0ε0输出一个近似比不超过 (1ε)(1ε) 的解且运行时间在输入规模 nn 上保持多项式对于一部分NP困难问题答案是肯定的。这类算法被统称为多项式时间近似方案。但“多项式时间”这个限定词背后藏着微妙的差异算法是 nf(1/ε)nf(1/ε) 还是 f(1/ε)⋅nO(1)f(1/ε)⋅nO(1)前者当 εε 很小时会迅速膨胀到不可接受后者则始终保持对 nn 的线性或低次多项式依赖。这种差异将PTAS家族细分为不同等级也划定了不同问题的近似难度边界。一、PTAS、EPTAS与FPTAS的形式化定义设 ΠΠ 是一个最优化问题OPT(I)OPT(I) 为实例 II 的最优值。PTAS多项式时间近似方案若存在一个算法 AA对于任意实例 II 和任意 ε0ε0AA 在 ∣I∣O(1)∣I∣O(1) 时间内输出一个解其目标值满足 (1ε)(1ε)-近似比对于最小化问题或 (1−ε)(1−ε)-近似比对于最大化问题且 εε 以任意形式出现在指数中如 n1/εn1/ε则称 ΠΠ 具有PTAS。PTAS是三类方案中定义最宽松的一类——只要对每个固定的 εε 算法在 nn 上是多项式的即可但允许指数中含 1/ε1/ε。EPTAS高效多项式时间近似方案若PTAS的运行时间可写为 f(1/ε)⋅nO(1)f(1/ε)⋅nO(1)其中 ff 是任意可计算函数则称其为EPTAS。EPTAS要求 εε 与 nn 在复杂度中分离——nn 的指数不依赖于 εε。FPTAS完全多项式时间近似方案若EPTAS的运行时间进一步限制为 (1/ε)O(1)⋅nO(1)(1/ε)O(1)⋅nO(1)即关于 1/ε1/ε 也是多项式的则称其为FPTAS。这是三类方案中最强的一类——无论在 nn 上还是在 1/ε1/ε 上都是多项式的。三个层次的关系是FPTAS⊂EPTAS⊂PTASFPTAS⊂EPTAS⊂PTAS。强包含关系意味着某些问题具有PTAS但不具有EPTAS在标准复杂度假设下某些问题具有EPTAS但不具有FPTAS。这一分层为近似算法的精细分类提供了理论框架。二、背包问题的FPTAS动态规划与缩放01背包问题是展示FPTAS构造的经典案例。问题回顾nn 件物品物品 ii 的重量为 wiwi价值为 vivi背包容量为 WW求总价值最大的物品子集且总重量 ≤W≤W。在第7篇中我们给出了 O(nW)O(nW) 的动态规划但这是一个伪多项式时间算法——WW 可能是指数级。现在我们换一个DP方向令 dp[i][j]dp[i][j] 表示前 ii 件物品中选出总价值恰好为 jj 所需的最小重量。状态转移为 dp[i][j]min(dp[i−1][j],dp[i−1][j−vi]wi)dp[i][j]min(dp[i−1][j],dp[i−1][j−vi]wi)。复杂度 O(n⋅Vmax)O(n⋅Vmax)其中 Vmax∑viVmax∑vi 仍可能是指数级。FPTAS的关键思想是缩放与舍入将物品价值按比例缩小并舍入为整数从而压缩DP的状态空间同时保证缩放引入的误差可控。具体构造如下设 vmaxmaxivivmaxmaxivi。对于给定的 ε0ε0定义缩放因子 Kε⋅vmaxnKnε⋅vmax。对每件物品构造缩放后的价值 v~i⌊vi/K⌋v~i⌊vi/K⌋。在新的缩放实例上运行上述DP此时最大总价值 ≤n⋅(vmax/K)n2/ε≤n⋅(vmax/K)n2/εDP复杂度为 O(n3/ε)O(n3/ε)这是关于 nn 和 1/ε1/ε 的多项式。近似比分析设缩放实例的最优解为 S∗S∗原实例的真正最优解为 O∗O∗。在 S∗S∗ 中物品总价值的损失来源于舍入——每件物品最多损失 KK 的价值∣S∗∣≤n∣S∗∣≤n总损失 ≤nKε⋅vmax≤ε⋅OPT≤nKε⋅vmax≤ε⋅OPT。因此缩放解的价值 ≥OPT−ε⋅OPT(1−ε)OPT≥OPT−ε⋅OPT(1−ε)OPT。这正好满足最大化问题的 (1−ε)(1−ε) 近似比。背包问题的FPTAS存在性并非孤例。一个著名的定理给出了FPTAS存在的必要条件若一个NP困难的优化问题具有FPTAS则其判定版本必然存在伪多项式时间算法。强NP完全问题即使所有数值以一元表示仍为NP完全除非PNP否则不可能具有FPTAS。三、平面图最大独立集的PTAS分隔与递归背包问题的FPTAS依赖于数值缩放。但许多图论问题不存在FPTAS如最大独立集在一般图中甚至在特定复杂度假设下连EPTAS也不存在。然而当输入限制为平面图时最大独立集问题却具有PTAS。其构造思路与背包完全不同——利用平面图的几何分隔性质。平面图的核心结构性质是平面分隔定理Lipton-Tarjan, 1979任意 nn 个顶点的平面图可以在 O(n)O(n) 时间内找到一个大小为 O(n)O(n) 的顶点分隔集其移除后将图分解为两个大小至多为 2n/32n/3 的不连通子图。基于此可构造平面图最大独立集的PTAS。算法采用递归分治若当前图规模小于某个阈值依赖于 εε则暴力枚举求最优。否则找到大小为 O(k)O(k) 的分隔集kk 为当前顶点数将其移除得到若干互不连通的子图。对分隔集枚举其所有可能的独立子集至多 2∣S∣2∣S∣ 种每种选择固定后在剩余子图上递归求解。所有子图的解与分隔集所选顶点合并取最大值。设 T(n)T(n) 为运行时间。递归式为 T(n)≤2O(n)⋅2⋅T(2n/3)T(n)≤2O(n)⋅2⋅T(2n/3)。对于任意固定的 ε0ε0可通过在递归树上截断到深度 O(log(1/ε))O(log(1/ε)) 来平衡误差。最终算法的运行时间为 O(nO(1/ε))O(nO(1/ε))——这是典型的PTAS而非EPTAS因为 nn 的指数依赖于 εε。误差分析的核心是分隔集的大小随图规模增大而增大但在每一层递归中移除的顶点数仅占当前图规模的 O(1/k)O(1/k) 比例在最坏情况下被移除的顶点在最优解中的占比也被控制在这一量级。通过精心设置递归深度总近似比可严格达到 (1−ε)(1−ε)。平面图上的许多其他NP困难问题——最小顶点覆盖、最小支配集、最大割——同样可通过类似的分隔递归技术获得PTAS。这一方法论的普适性源于平面图的分隔结构NP困难的根源被限制在局部密集区域而平面分隔定理保证了这些区域可被有效隔离。四、PTAS的存在条件与不可能性并非所有NP困难问题都具有PTAS。是否存在PTAS取决于问题的内在难度结构。从正面看PTAS通常存在于以下情形问题具有伪多项式时间算法且非强NP完全存在FPTAS如背包问题。问题在某种几何或拓扑约束下如平面图、欧氏空间、单位圆图可借助分隔定理分解为近似独立的小实例存在PTAS或EPTAS。问题的最优解具有“渐近无后效性”可通过动态规划加缩放构造如调度问题。从反面看APX-难问题即存在常数 c1c1 使得 cc-近似已是NP困难一定不存在PTAS除非PNP。例如旅行商问题在一般图上是APX-难的最大SAT、集合覆盖不可优于 O(logn)O(logn)也属于此类。PCP定理的推论进一步精确刻画了许多问题的不可近似下界。五、总结与展望PTAS、EPTAS、FPTAS构成了近似算法精确度的三级阶梯。背包问题凭借数值缩放获得FPTAS平面图最大独立集借助几何分隔获得PTAS。两者的构造逻辑截然不同却共同展示了算法设计师在面对NP困难问题时的核心智慧不要硬碰困难本身而是寻找困难的“来源”将其隔离、压缩或缩放。并非所有问题都拥有PTAS——当问题被证明为APX-难时常数近似已经是最优的可能。下一篇我们将进入不可近似性理论的核心地带讨论PCP定理的直观含义以及它如何为大量NP困难问题划出精确的近似比下界——为什么最大3-SAT不能近似到任意接近1为什么团问题连有意义的近似都不可能。
