近似算法是一种算法,它为数学优化问题求得可行解,并对该解相对于最优解的质量给出可证明的保证。这个术语通常指用于求解难以精确计算的问题的多项式时间算法。近似算法不要求得到最优答案,而是明确说明:为了高效求得一个解,需要牺牲多少解的质量。
这一研究领域在组合优化中尤为重要,其应用涉及选择路线、分配作业、确定设施位置,或在约束条件下选取子集。许多此类问题都具有NP难性,因此,在标准的复杂性假设下,不太可能存在通用的高效精确算法。近似算法提供了一种系统性的替代方案:其性能由数学分析支撑,而不仅仅依赖于实验中的良好表现。
这一领域将算法设计与计算复杂性、几何、概率和连续优化联系起来。其核心问题既关乎可能性,也关乎局限性:能够实现怎样的保证,实现这些保证需要多少计算资源,以及更好的保证是否意味着某种出乎意料的突破,例如为 NP 中的每一个问题找到多项式时间算法。
形式化保证及其解释
一个优化问题规定了一组实例、每个实例的可行解、一个目标函数,以及该目标是要最小化还是最大化。用 表示实例 的最优目标值,用 表示算法返回的目标值。按照近似比至少为一的常见约定,最小化问题的 -近似算法满足
而最大化问题的 -近似算法满足
可行性也是保证的一部分:一个成本很低、却违反了必要约束的解,通常不能算作近似解。
对于最大化问题,另一种广泛使用的约定是报告所得目标值占最优值的比例。按照这一约定,-近似算法(其中 )保证 。因此,“二倍近似”和“二分之一近似”可能描述的是同一种最大化保证。有关近似的表述必须明确说明或清楚体现所采用的约定。近似因子可以是常数,例如 ,也可以是实例规模的函数,例如 。
乘性保证最适用于非负目标值。如果一个最小化问题实例的最优值为零,那么有限的乘性保证要求输出值也为零。对于负的目标值,则需要采用不同的定义或施加限制。此外,给所有目标值加上同一个常数,虽然不会改变哪个解最优,却可能极大地改变问题的乘性可近似性。因此,近似质量取决于目标函数在数值上的具体形式,而不只是它对各个解的排序。
加性保证则对绝对误差给出界限,例如在最小化问题中保证 。有些算法给出形如 的混合界。还有一些算法提供渐近保证,即当最优值足够大时,所述近似比才适用。当目标值是较小的整数时,这些区别尤为重要。
通常的效率要求是:相对于输入的编码长度,算法具有多项式时间复杂度;编码长度也包括表示权重和容量所用的比特数。此类保证通常针对所有有效实例的最坏情况,而不是某个便于使用的数据集上的平均表现。随机化算法则可能对目标值的期望作出保证,或给出以指定概率成立的界限。这类表述必须区分算法自身使用的随机性与输入中的随机性。对每个实例都成立的确定性保证、对每个实例都成立的期望保证,以及实测平均值,是不同类型的证据。
历史发展与复杂性视角
近似方法的出现早于现代对优化问题的复杂性分类。在调度领域,罗纳德·格雷厄姆于1966年对列表调度的分析给出了一个影响尤为深远的最坏情况保证。将作业逐一分配给 台相同机器中当前负载最小的一台时,最终的最大负载不超过最优值的 倍。格雷厄姆后来分析了按处理时间递减顺序安排作业的方法,得到了更强的界限 。这些结果表明,简单的算法也能具有精确且不依赖于具体实例的性能保证。
20世纪70年代初,NP完全性理论的发展改变了这类研究的动机。斯蒂芬·库克和理查德·卡普的研究揭示了许多类问题,其精确求解与P与NP问题密切相关。近似由此成为更细致地区分困难优化问题的一种方式。精确求解具有NP难度,并不能决定一个问题能否被高效地求得近似最优解:有些NP难问题允许在多项式时间内达到任意高的近似精度,另一些则无法在任何固定常数因子内得到近似。
20世纪70年代出现了若干奠基性成果。戴维·约翰逊1974年的研究推动了组合问题近似算法的系统性分析,其中包括针对覆盖问题的对数近似保证。萨尔塔杰·萨尼为调度问题和背包类问题开发了早期的近似方案。奥斯卡·伊巴拉和金哲于1975年的研究为背包问题和子集和问题给出了完全多项式时间近似方案。1976年,尼科斯·克里斯托菲德斯提出了度量旅行商问题的 近似算法。这些成果表明,即使同属计算困难问题这一大类,不同问题的可近似程度也可能存在显著差异。
在20世纪80年代和90年代,数学规划逐渐成为这一领域的核心工具。通过松弛,可以将离散问题与连续优化给出的下界或上界进行比较。原始—对偶方法、随机舍入和半定优化提供了适用于多种问题的技术。1995年,米歇尔·戈曼斯和戴维·威廉姆森提出了影响深远的最大割半定近似算法,保证所得解的目标值至少约为最优值的 倍。
与此同时,不可能性结果也在不断发展。通过20世纪90年代初的一系列研究建立起来的概率可检验证明理论,使研究者能够对求取近似最优解的困难程度作出强有力的论断。后续成果又将精确的近似阈值与约束满足问题的相关猜想联系起来。因此,这一领域形成了相辅相成的两个方面:一方面通过构造算法证明某个近似比可以达到,另一方面通过复杂性归约表明,要进一步改进这一近似比,就必须突破某项明确的计算复杂性假设。当这两个方面得出的界限吻合时,这一界限尤其有意义,因为它确定了在该假设下,多项式时间算法所能达到的最佳保证。
贪心选择、费用分摊论证与局部搜索
贪心算法通过一系列在局部看来有利的选择来构造解。贪心方法并不天然就是近似算法:必须针对具体问题和选择规则,证明其解的质量。一种典型的证明方法,是将算法的费用分摊给一些对象,而这些对象也对任何最优解构成约束。这种技巧通常称为费用分摊论证,它将一系列局部决策转化为与最优解的全局比较。
带权集合覆盖问题就是一个经典例子。给定一个包含 个元素的全集,以及若干具有非负费用的集合,任务是以最小总费用覆盖所有元素。贪心规则每次选择费用与新覆盖元素个数之比最小的集合。如果还有 个元素未被覆盖,而最优覆盖的费用为 ,那么该最优覆盖中至少有一个集合,其每个新覆盖元素的平均费用不超过 。将所选集合的费用按新覆盖元素的个数均摊到这些元素上,可得
随着尚未覆盖的元素不断减少,可用于分摊剩余费用的元素个数也不断下降,由此得到对数级的近似保证。
另一种初等论证可以为无权顶点覆盖给出近似因子为 2 的算法。先构造任意一个极大匹配,即一组互不共享端点、且无法再加入任何边的边集。然后输出每条匹配边的两个端点。这些顶点构成一个顶点覆盖:如果有一条边未被覆盖,那么它的两个端点都未被匹配,因此本可以将这条边加入匹配。任何可行的顶点覆盖都必须包含每条匹配边的至少一个端点,所以匹配的大小是最优值的下界,而算法选择的顶点数恰好是匹配大小的两倍。这里不需要最大匹配;只要匹配是极大的就足够了。
局部搜索从一个可行解出发,反复在指定的邻域中执行能改进当前解的操作。局部最优解未必是全局最优解,但精心选择的邻域可以带来近似保证。例如,在度量 -中位数问题中,以关闭一个已开放设施并开放一个未开放设施作为交换操作,在精确的局部最优解处可获得近似因子为 5 的保证。如果允许每次交换至多 个设施,则可得到 的界。证明时,将局部解中的设施与最优解中的设施进行比较,再综合一组表明指定交换无法改进当前解的不等式。
局部搜索的分析不仅要考虑解的质量,还必须考虑运行时间。当费用采用二进制编码时,严格改进解的一系列操作可能极其漫长。因此,算法通常要求每次接受的操作都使目标值产生足够大的相对改善。这可以保证迭代次数为多项式量级,但通常会付出近似质量略微下降的代价。因此,邻域的定义和停止准则都是定理的组成部分,而不是可以从定理中省略的实现细节。
线性松弛、舍入与原始—对偶方法
许多离散优化问题都可以表述为整数规划,其中变量只能取整数值。去掉这些限制,就得到一个线性规划松弛。对于最小化问题,每个整数可行解也是松弛问题的可行解,因此分数最优值是真正最优值的下界。对于最大化问题,它则给出上界。接下来的算法任务,就是将分数解转化为合法的离散解,同时避免目标值损失过多。
带权顶点覆盖可以用来说明确定性舍入。为每个顶点 设置一个变量 ,表示是否选择该顶点。其松弛问题为
选择所有满足 的顶点。每条边都至少有一个端点被选中,并且
这一阈值既保证了解的可行性,也控制了成本。
整数间隙衡量整数最优值与其松弛问题最优值之间的差距。对于最小化问题,它是在所有适用实例上,整数最优值与分数最优值之比的上确界。如果间隙很大,那么仅通过将算法输出值与该松弛问题的最优值进行比较,所能证明的近似保证就会受到限制。但这本身并不排除通过更强的规划模型或其他论证获得更好的近似保证。必须区分:某种局限究竟来自特定的松弛,还是来自计算问题本身。
原始—对偶方法利用对偶线性规划,其可行解能够为原问题的最优值提供可验证的界。在带权顶点覆盖中,对偶问题为每条边赋予非负值 ,并要求每个顶点都满足
。逐步提高边的对偶值,并选择约束达到紧致状态的顶点,就可以构造出一个可行的顶点覆盖。由于每条边至多对两个被选中的端点作出贡献,覆盖的成本不超过对偶值总和的两倍。再由弱对偶性,即可将这个总和与最优覆盖成本联系起来。
更精细的舍入方法会保留变量间的相关性、构造组合结构,或在初步选择后修复违反约束的情况。设施选址、网络设计和调度问题都受益于这些方法。松弛的价值不仅在于它们可以求解,还在于其约束揭示了舍入算法必须保留的结构。分数解可以帮助识别哪些选择成本较低、哪些要求难以满足,以及哪些地方需要协调决策。
随机化与半正定优化
随机性既可以简化算法的构造,也可以简化其分析。最大割问题要求将图的顶点划分为两部分,使跨越两部分的边的总权重最大。如果每个顶点都独立地以 的概率选择任意一部分,那么每条边跨越两部分的概率都是 。因此,割的期望权重等于所有边总权重的一半,且至少为最优值的一半。这样,无须知道最优割,就能保证期望值至少达到最优值的一半。
同样的论证可以通过条件期望法去随机化。逐个为顶点分配所属部分,每次都选择不会降低最终权重条件期望的一侧。由于初始期望等于所有边总权重的一半,最终得到的割能够确定性地达到至少这一数值。这说明了一个重要原则:即使存在具有相同保证的确定性算法,随机性仍可能揭示一种基于平均值的论证思路。
随机舍入将概率选择应用于分数松弛解。在集合覆盖问题中,对于分数值为 的集合,可以以 的概率选取它,其中 是一个适当的常数。对于一个元素,如果覆盖它的各个变量之和至少为一,那么利用独立性,可以将它未被覆盖的概率上界估计为约 。利用联合界可以控制存在未覆盖元素的概率,而利用期望的线性性则可以约束所选集合的总成本。完整的算法可以采用重复采样或显式修补步骤;仅仅计算期望,并不能证明每个采样得到的解都是可行的。
半正定规划要求矩阵变量为半正定矩阵,从而能够构造更强的松弛。对于最大割问题,Goemans–Williamson 松弛为每个顶点分配一个单位向量 ,并最大化
将向量限制在两个相反方向上的赋值方式,就能表示普通的割,因此这个连续优化问题的最优值是最优割权重的上界。
舍入过程随机选择一个经过原点的超平面,再根据各顶点对应的向量位于超平面的哪一侧,将顶点分为两部分。如果两个向量的夹角为 ,它们被分到不同侧的概率就是 。将这一概率与松弛问题中相应边的贡献 相比较,得到
因此,当边权重非负时,除去求解松弛问题时的数值精度误差,输出割的期望权重至少达到最优值的这一比例。与独立随机分配相比,这一改进来自利用向量的几何关系来协调各次舍入选择。
度量与几何近似
结构性假设可以极大地改变问题的可近似性。一个典型例子是旅行商问题,它要求找出一条访问每个顶点且成本最低的巡回路线。在度量版本中,成本具有对称性、非负性,并满足三角不等式:
这个不等式允许采用捷径操作:将行走路径中的一段替换为一条直达边,不会增加路径长度。许多路线规划近似算法都依赖这一操作。
一种简单的二倍近似算法从一棵最小生成树出发。从最优巡回路线中删除一条边,剩下的就是一棵生成树,因此最小生成树的成本不会超过最优巡回路线的成本。将树的每条边都复制一份,就得到一个各顶点度数均为偶数的连通多重图;该图存在欧拉回路,其成本是这棵树成本的两倍。再通过捷径操作跳过重复访问的顶点,就能得到一条哈密顿巡回路线,且成本不会增加。
克里斯托菲德斯算法将近似比改进至 。该算法找出最小生成树中所有度数为奇数的顶点,并在这些顶点之间加入一个最小成本完美匹配。这些顶点的数量必为偶数。对最优巡回路线应用捷径操作,使其只访问这些顶点,就得到一个环;将环上的边交替分成两组,可得到两个完美匹配,其中成本较低者的成本至多为原问题最优值的一半。最小成本完美匹配的成本也不会更高。因此,将生成树与该匹配合并,就能得到一个成本至多为最优值 的欧拉多重图,再通过捷径操作即可得到所需的巡回路线。
度量假设具有实质性作用,而非仅仅是形式上的修饰。对于不受限制的完全图,可以将哈密顿环问题实例中缺失的边表示为成本极高的边。只要将这一惩罚成本设得足够高,任何具有固定常数近似比的近似算法就都能区分哪些图存在哈密顿环、哪些图不存在。因此,除非 P 等于 NP,否则不受限制的旅行商问题不存在多项式时间常数因子近似算法;相比之下,度量版本则有性能优良的常数因子近似算法。
欧几里得几何提供了更多结构。对于固定维数欧几里得空间中的点,旅行商问题存在多项式时间近似方案;这一结果由桑吉夫·阿罗拉和约瑟夫·米切尔在 20 世纪 90 年代各自独立的研究中确立。一种典型方法是递归划分空间,并限制近似最优巡回路线穿越分区边界的方式,再用动态规划记录数量有界的边界穿越模式。分析表明,可以修改最优巡回路线,使其满足这些限制,而长度仅有很小的相对增幅。维数固定、精度固定是必不可少的前提:即使运行时间关于点的数量是多项式,其对这些参数的依赖仍可能相当显著。
近似方案与数值缩放
多项式时间近似方案(简称 PTAS)是由精度参数 索引的一族算法。对于最小化问题,它返回的解的目标值不超过 ;对于最大化问题,通常要求目标值至少为 。对于每个固定的 ,运行时间都必须是输入规模的多项式。因此,像 这样的运行时间也符合要求,尽管随着所要求的误差减小,计算开销会变得很大。
完全多项式时间近似方案(简称 FPTAS)满足更强的要求:运行时间必须同时是输入长度和 的多项式。这一区别反映了提高精度所需付出的代价。PTAS 在精度要求适中时可能很高效,但在 很小时可能并不实用;FPTAS 则使精度与计算开销之间的权衡更加可控。不过,这两种名称本身都不保证其中的常数或多项式次数足够小,能够满足某个具体应用的需要。
0–1 背包问题提供了一种标准的缩放构造。每件物品都有非负收益 和一个重量,并且只能选择装入或不装入。所选物品的总重量不得超过容量限制。剔除那些单独一件就超过容量的物品后,设 为剩余物品中的最大收益, 为剩余物品的数量。对于 ,令
动态规划算法可以针对缩放后的整数收益,找到精确最优的可行子集;其状态记录达到每个缩放后总收益所需的最小重量。
向下取整使每件物品损失的收益小于 ,因此一个解的总收益损失小于 。由于收益最高的单件可行物品本身就构成一个可行解,有 ,所以所选子集的实际收益至少为
每件物品缩放后的收益至多为 ,因此缩放后的总收益至多为 。由此,直接的动态规划实现的运行时间是 和 的多项式。如果所有可行物品的收益均为零,可以单独处理这一简单情形。
这一构造说明了近似方法如何将伪多项式时间算法转化为真正的多项式时间算法。伪多项式运行时间依赖于某个数值的大小,例如总收益,而非该数值的二进制编码长度。缩放能够减小这一数值,同时将由此引入的误差控制在一定范围内。相比之下,对于目标值为整数且其范围受到适当限制的强 NP 难问题,精度足够高的完全多项式时间近似方案将能在多项式时间内求得精确最优解。因此,除非 P 等于 NP,否则这类问题通常不可能有 FPTAS,尽管它们仍可能有 PTAS。
不可近似性与保近似归约
仅仅证明精确求解是 NP 难的,并不能确立近似求解的难度。用于证明精确求解困难性的归约,可能构造出最优值相对于庞大总量仅相差一个单位的实例。很小的相对误差就可能掩盖这一差异。要确立不可近似性,归约必须构造出受控的间隙:一类输入的最优值不超过某个阈值,而另一类输入的最优值则高于另一个与前者充分分离的阈值。
保近似归约形式化地描述了如何将一个问题的近似解转换为另一个问题的近似解。不同类型的归约保留不同的性质,例如常数因子可近似性,或近似方案的存在性。归约的具体细节至关重要:适合用于证明 NP 完全性的归约,未必能给出任何有用的近似关系。目标函数的缩放、辅助变量以及强制引入的成本,都可能改变相关的近似比。
关于概率可检验证明的 PCP定理,是间隙归约的一个主要来源。该定理的一种表述是:对于 NP 中的语言,只需使用对数数量的随机比特,并检查证明中常数个位置,就能验证输入是否属于该语言。将验证器的检验转化为约束后,便可得到这样的实例:可满足的情形与每种赋值都违反固定比例约束的情形可以区分开来。借助这一联系,在 P 不等于 NP 的假设下,可以排除那些对某些优化问题逼近最优值过于精确的算法。
在多项式时间可验证优化问题的标准定义下,APX 类包含那些存在多项式时间常数因子近似算法的优化问题。通过适当的保近似归约,APX 难性表明某个问题涵盖了这一类问题的近似求解难度。若要称为 APX 完全问题,还必须属于 APX。对于标准的 APX 完全问题,若存在多项式时间近似方案(PTAS),就意味着 P 等于 NP。因此,近似复杂性类区分了普通 NP 难性未能明确区分的计算难度层次。
有些阈值是紧确的。对于全集含有 个元素的集合覆盖问题,贪心算法给出的对数近似界本质上已经最优:对于每个固定的 ,达到 以内的近似比是 NP 难的。伊里特·迪努尔和戴维·斯托伊勒在 2014 年的研究中,仅在 P 不等于 NP 的假设下就确立了这一阈值,强化了此前依赖更强复杂性假设的结果。
另一些提出的阈值则依赖额外的猜想。苏巴什·科特于 2002 年提出的唯一博弈猜想,涉及某些约束满足问题的求解难度。在该猜想成立的条件下,戈曼斯–威廉姆森常数就是最大割问题的最优多项式时间近似阈值。与普通的 NP 难性结果相比,这类论断的结论更强,但所依赖的假设也更强。因此,在将某个算法描述为最优算法时,必须区分已经证明的困难性、依赖猜想的困难性,以及某种特定技术本身的局限。
其他保证与计算模型
并非所有有用的近似结果都能用单一的乘法比率来描述。在装箱问题中,需要将大小均不超过一的物品放入容量为一的箱子,并使所用箱子数量最少。算法可能满足如下界:
其中, 与具体实例无关,但取决于所要求的精度。这是一种渐近近似保证:当所需箱子数量很大时,加法项的相对影响便微不足道。这不同于对每个实例都保证 这一界。
小规模实例使这种区别不可避免。判断一组总大小为二的物品能否装入两个箱子,可以编码划分问题。由于箱子数量必须是整数,绝对近似比严格小于 的算法,只要最优解为两个箱子,就必须返回两个箱子。因此,它能够精确区分这些实例。加法常数使算法可以对大规模实例提供很强的保证,而不必对最优值较小的实例作出同样的承诺。
双准则近似允许在两项要求上作出受控的让步。聚类算法可能在使用超过指定数量 个中心的同时,使目标函数值保持在最优值的常数倍以内。调度算法可能只有在机器速度快于原始实例的条件下,才能达到给定目标。这些结果在数学上可能很强,但解读时必须同时说明两方面的放宽。一个违反硬约束的解,不能仅因目标函数值表现良好,就被视为通常意义上的可行近似解。
在线算法逐步接收输入,而且往往必须在尚不知道未来请求时作出决策。其性能通常用竞争比衡量,即与预先知道完整输入的最优离线解进行比较。这在代数形式上类似于近似比,但困难的来源不同:在线算法缺少未来信息,而离线近似算法掌握整个实例,只是计算资源有限。即使计算能力不受限制,在线算法的下界仍可能成立。
流式模型和分布式模型施加了进一步的限制。流式算法可能必须使用远小于完整图表示所需的内存来处理大型图;分布式计算中的算法则可能受到通信轮数或消息大小的限制。因此,近似质量必须与内存、通信、更新时间或同步开销一并考量。同样,参数化近似研究的权衡不仅涉及输入规模,也涉及某个结构参数。运行时间为 的过程,与运行时间为 的过程,具有不同的效率保证。仅报告目标函数值的近似比,可能掩盖使结果具有重要意义的资源因素。
应用、目标函数结构与实现
当优化模型描述的是大规模离散规划问题,而求得精确解的代价过高时,近似算法尤为有用。例如,在调度论中,将相互独立的作业分配给相同的机器,以最小化最大完工时间,就直接引出了最大完工时间的近似求解问题。列表调度的证明简短而富有启发性:若最后完成的作业的处理时间为 ,则它的开始时间至多为其余作业的总处理时间除以 。因此
这一证明既依赖于平均负载,也利用了任何可行调度都必须容纳处理时间最长的作业这一事实。
在设施选址中,目标函数同时考虑开设设施的成本和为客户提供服务的成本。常数因子近似结果通常依赖于满足度量性质的连接成本;在合并、关闭或替换设施时,这些性质为重新分配客户的论证提供了依据。在网络设计中,相关模型需要选择连接指定终端的链路。斯坦纳树问题与最小生成树问题的区别在于,前者可以使用额外的、非必需的顶点来降低总连接成本。这些建模选择既会影响最优值,也会影响哪些算法适用。
目标函数的结构可能与图结构或几何结构同样重要。次模函数刻画了边际收益递减的性质:向较小的已选集合中加入一个元素,所得收益至少不低于向较大的已选集合中加入该元素的收益。对于归一化、非负且单调的次模函数,在至多选择 个元素的基数约束下,贪心选择得到的目标值至少为最优值的 。在每一步,可获得的最大边际收益至少为当前值与最优值之间剩余差距的 分之一;反复应用这一不等式即可得到上述界限。最大覆盖问题就是一个典型例子。
这些结果与特征选择、实验设计和数据摘要等任务密切相关,但只有在所述数学假设成立时,相应保证才适用。机器学习中的目标函数并不天然具有次模性,而对目标函数进行近似求值或带噪声的求值,可能需要调整分析方法。同样,基于对称度量距离得到的路径规划保证,也未必适用于非对称的行程时间或额外的时间窗约束。
实际实现通常将具有可证明保证的方法与启发式方法结合使用。近似解可作为局部改进的初始解,而松弛问题则可提供针对具体实例的下界。如果最小化算法找到一个成本为 的解,且有一个有效下界 ,那么 就能为该解在这一实例上的质量提供保证,而且这种保证可能远强于一般的最坏情况定理。要确保这一证明凭据始终有效,就必须谨慎处理浮点容差、可行性检查和终止规则。优化求解器经过舍入的数值输出并不自动构成精确界限;严格的证明凭据要求可行性经过验证,或明确计入数值误差。