摘要：组合优化问题在计算复杂性理论里处于关键地位，特别是当P≠NP的时候，近似算法就成了处理NP难题优化问题的主要手段。这个研究形成了一套系统的近似复杂性层次理论架构，仔细剖析了各种组合优化问题的近似属性及其相互联系。凭借创建以近似比函数为基础的复杂性类别定义体系，研究弄清了旅行商问题、图着色、最大团这类经典问题在近似意义下的层次结构。理论分析显示，保近似归约技术给创建问题间的等价关系赋予了有用手段；参数化近似理论的出现又拓宽了传统复杂性分析的范围。这项研究给近似算法的设计给予理论指引，对于推动计算复杂性理论向前迈进有着重要的学术价值。

关键词：组合优化；近似算法；计算复杂性；层次理论；算法设计

1. 绪论

1.1研究背景与问题提出

计算复杂性理论从诞生之初就试图去了解计算问题的本质难度。众多计算问题之中，组合优化问题因为有着广泛的适用范围和深刻理论内涵而备受瞩目；它要在一个有限制的离散结构当中，找到符合特定约束条件的最佳答案。典型的例子有旅行商问题、背包问题以及图着色问题等等。

现代组合优化理论遇到的根本难题源于P和NP之间的关系悬而未决。许多重要的组合优化问题被证实为NP困难，这表明在P不等于NP的前提下，不存在针对这些问题的多项式时间精确算法。这种理论上的局限性促使近似算法研究的迅猛发展。近似算法能在多项式时间内找到较为接近最优的解，其性能用近似比来衡量，即算法输出与最优解的比值。

机器学习技术的发展给组合优化问题求解开辟了新道路^[1]，深度学习与强化学习方法在解决复杂优化问题时有着巨大潜力，不过这些方法缺少理论保证，传统近似算法虽然在某些实例上可能不如机器学习方法，但能给予严格理论分析和性能保证。

量子计算的出现给组合优化带来新机遇^[2]，量子近似优化算法在一些特定问题上效果不错，不过其理论根基还需继续充实，这样的发展让构建统一理论框架变得越发迫切，这样做的目的就是更好地认识各种求解方法适合哪些问题以及能达到怎样的效果。

强化学习在组合优化中应用愈发广泛^[3]，通过对智能体模型进行训练以快速求解复杂问题，这种方法的优点是可以自适应学习问题特点，但理论分析却较为困难。如何在保持算法灵活性的同时又给予理论保证，是目前研究的重点。

启发式算法在实际应用中获得了很大的成功^[4]，尤其是对于大型实例，启发式算法往往可以在合理的时间内得到一个较好的解，但是启发式算法不能保证得到最优解。启发式算法的设计依赖于问题的特殊结构，没有通用的理论。

图结构在组合优化里很重要^[5]，很多优化问题都能转换成图上的问题，这样就给算法设计提供了很多理论工具，图论技术和近似算法结合出了很多很好的研究结果，不过各个问题之间到底怎么联系还需要再仔细探究。

网络优化问题在现代社会中变得愈发重要^[6]。互联网、物联网、社交网络等复杂系统都涉及到大规模的网络优化问题，这些网络优化问题具有规模大、结构复杂等特点，传统的精确算法很难应对。

局部搜索算法是求解组合优化问题的重要方法^[7]，它在解空间内做局部搜索来找到高质量的解。这类算法的理论分析比较困难，特别是关于算法是否收敛、得到的解的质量如何等。

传统的近似算法理论已经有了较为完善的理论框架^[8]，但是面对新的技术、新的应用，现有的理论已经不能完全适应，建立更完善、更统一的理论框架，从而指导新的算法设计与分析，是当前的迫切需求。

1.2研究目标与学术贡献

本研究的主要目标是形成一套系统化的组合优化近似复杂性层次理论，这一理论框架能够给各类优化问题的近似特性赋予统一的分析手段，从而为算法设计给予理论上的引导。

研究的学术贡献主要体现在理论创新上，把参数化近似这个概念引入进来之后，就把固定参数可处理性理论同近似算法融合起来，从而拓宽了传统复杂性分析的范围，这种融合既充实了理论内容，又给实际算法设计给予了新的想法。

保近似归约技术的系统研究是本工作的重要贡献之一，建立严格的归约体系，发现看似不同的优化问题在近似意义下存在着内在联系，归约技术使得近似比在转换过程中保持不变，为建立问题等价关系提供了强有力的工具。

复杂性类别的准确刻画是本研究的基本成果，通过界定依靠近似比函数的复杂性类别，研究形成了更为精细的问题划分系统，这种划分既包含时间复杂度，又牵涉到近似质量等诸多方面的性能指标。

算法下界理论发展是本研究重要部分，通过分析特定问题类别近似不可能性，找到算法性能理论极限，这种下界分析给评价算法好坏提供客观标准，能找出近似比最优的算法。

2. 相关理论与研究现状分析

2.1近似算法复杂性理论基础

近似算法复杂性理论建立在经典计算复杂性理论的基础之上，但其关注点从“能否求解”转向“能否近似求解”。这一理论转变反映了计算科学从追求完美解向追求实用解的思维转换。

PCP定理的证明标志着近似算法理论的重大突破。该定理揭示了许多NP完全问题存在常数不可近似性，即不存在近似比小于某个常数的多项式时间算法。这一结果不仅确立了某些问题的近似下界，还为设计新的不可近似性证明提供了强有力的工具。

表1展示了主要复杂性类别的定义及其相互关系：

表1 近似复杂性类别分类

半定规划松弛技术在近似算法设计中发挥着重要作用。该技术通过将原问题松弛为半定规划问题，然后使用随机舍入技术恢复整数解。Goemans-Williamson算法for最大割问题是这一技术的典型应用，达到了0.878的近似比。

线性规划松弛作为另一重要技术，通过将整数约束松弛为连续约束来获得下界。舍入技术将分数解转换为整数解，其性能分析通常涉及积分间隙的计算。许多经典近似算法都基于这一框架，如最小顶点覆盖的2-近似算法。

随机化技术为近似算法设计提供了额外的灵活性。概率方法不仅能够简化算法设计，还能够在某些情况下获得更好的近似比。期望值分析和概率集中不等式是分析随机化算法的主要工具。

去随机化技术将随机算法转换为确定性算法，保持相同的性能保证。条件期望方法和有限独立性技术是实现去随机化的常用手段。这一技术的发展使得许多优秀的随机算法得以实际应用。

2.2组合优化问题的分类与层次结构

组合优化问题种类繁多，因此要创建起系统的分类体系，按照问题结构，约束类型，目标函数等特征，可以将这些组合优化问题归入不同的类别，每个类别中的问题有着类似的算法特征和复杂程度。

图优化问题属于组合优化的重要分支，它包含最短路径，最小生成树，最大流这些基本问题，还有旅行商问题，图着色，团问题这些难题，图的结构特征给算法设计给予了众多理论手段。

网络流问题是图优化问题的一种特殊情形，但是由于它的实际重要性及其广泛应用，所以它属于单独的一类问题。最大流最小割定理是这类问题的基础，而线性规划对偶理论给算法设计提供指导。多商品流、成本流等扩展问题也使理论更加复杂。

整数规划问题提供了一个描述组合优化问题的框架，线性规划松弛、分支定界、割平面等技术是解决此类问题的基本技术，近些年半定规划松弛技术的发展使得一些特殊的整数规划问题有了更好的近似算法。

调度问题在运筹学与计算机科学领域均占有重要地位，机器调度，任务分配以及资源分配等都是具有实际背景的问题，此类问题有着复杂的约束条件，多种目标以及诸多要素需要权衡。

图1呈现了主要问题类别的近似复杂性层级：

图1 组合优化问题近似复杂性层次图

装箱问题与背包问题体现出资源分配优化的关键特点，这类问题的算法设计常常依靠贪心策略以及动态规划手段，近似算法的性能评价大多联系到对最优解结构的洞察。

匹配问题与覆盖问题在图论中有对偶关系，最大匹配与最小顶点覆盖间的关系显示了线性规划对偶理论在组合优化中的应用，这种对偶关系给算法设计给予了关键启迪。

设施选址问题结合了图论与运筹学的特征，它既包含离散的选择，又包含连续的成本函数，局部搜索算法对于这类问题表现良好，不过理论分析比较繁杂。

近似算法设计通常要利用问题的特殊结构，度量空间的三角不等式性质给很多几何优化问题提供算法设计基础，平面图的特殊性质让一些在一般图上难解的问题变得容易解决。

3. 组合优化近似复杂性的层次理论构建

3.1近似复杂性类别的数学刻画

建立严格的数学框架是理论构建的基础。近似复杂性类别的定义需要综合考虑算法的时间复杂度、空间复杂度和近似质量等多个维度。传统的复杂性理论主要关注判定问题，而近似复杂性理论需要处理优化问题的特殊性质。

参数化近似理论将固定参数可处理性与近似算法相结合。对于参数为k的问题实例，算法的运行时间可以表示为f(k)·n^c的形式，其中f是关于k的任意函数，c是常数。这种分析框架允许算法在参数较小时获得更好的性能保证。

定义1（参数化近似算法）：给定优化问题Π和参数k，如果存在算法A使得对于任意实例I，算法A在时间f(k)·I^c内输出近似比为ρ(k)的解，则称A为参数化ρ(k)-近似算法。

这一定义的关键在于近似比可以依赖于参数k，而时间复杂度的指数部分仅涉及参数。这种设定反映了实际应用中参数通常较小的特点，使得某些理论上困难的问题在实践中变得可处理。

近似复杂性的层次结构可以通过归约关系来建立。保近似归约要求在归约过程中保持近似比的稳定性，这比传统的Karp归约或Turing归约更加严格。

定义2（保近似归约）：问题Π₁到问题Π₂的保近似归约是一个多项式时间算法R，满足：

· R将Π₁的实例I₁映射为Π₂的实例I₂

· 如果A是Π₂的ρ-近似算法，则R∘A∘R⁻¹是Π₁的ρ-近似算法，其中ρ与ρ相关

这种归约关系的传递性使得我们能够建立问题间的层次关系。如果问题Π₁归约到问题Π₂，则Π₂的近似下界也适用于Π₁。

近似比函数的增长性质决定了复杂性类别的划分。常数近似、对数近似、多项式近似等不同增长速度对应不同的复杂性层次。

公式1给出了近似比的形式化定义：

对于最小化问题，近似比定义为：

对于最大化问题，近似比定义为：

其中A(I)表示算法在实例I上的输出，OPT(I)表示实例I的最优解值。

3.2优化问题间的层次关系与等价性分析

建立问题间的等价关系需要双向的保近似归约。如果两个问题可以相互归约且保持相似的近似比，则这两个问题在近似意义下等价。这种等价关系为算法设计提供了重要指导。

图论问题在组合优化中占据核心地位，许多问题都可以转化为图上的优化问题。顶点覆盖问题和独立集问题之间的对偶关系是问题等价性的典型例子。对于顶点数为n的图G，如果S是大小为k的顶点覆盖，则V(G)\S是大小为n-k的独立集。

最大割问题和最大2-SAT问题之间存在近似等价关系。这种等价性通过构造特殊的图结构来实现，使得一个问题的近似算法可以直接应用到另一个问题上。

表2展示了主要问题类别间的归约关系：

表2 组合优化问题归约关系表

网络流问题同线性规划之间存在密切关联，很多网络优化问题具备不错的近似性质，最大流问题能够在多项式时间内被精确求解，这就给相关问题的近似算法设计赋予了根基。

多商品流问题的近似复杂性介于精确可解的单商品流和NP困难的整数多商品流之间。分数多商品流可以在多项式时间内通过线性规划求解，整数多商品流一般需要近似算法。

旅行商问题的不同变种表现出不同的近似性质，度量TSP存在3/2 - 近似算法，但是一般TSP并不存在常数近似算法（除非P = NP），这种差别显示出问题约束对近似性质的关键作用。

调度问题的复杂性分析需要考虑机器种类、任务属性、优化目标等诸多因素。单机调度问题一般比多机调度问题要容易解决，而在线调度问题要比离线调度问题要难解决。

整数规划的特殊情形往往拥有更好的近似性质，全单模矩阵对应的整数规划可以被通过线性规划松弛精确求解，一般的0-1整数规划则往往需要指数时间算法。

近似算法的下界分析依赖于复杂性理论的假设。P≠NP假设给出了最基础的下界，更强的假设比如唯一博弈猜想可以给出更强的不可近似性结果。

4. 理论应用与研究展望

4.1算法设计的理论指导意义

层次理论给算法设计赋予了系统性的指导准则，通过剖析问题处在复杂性层次中的位置，能够预估大概的近似比范围，从而引导算法设计策略的选择，这样的理论指导有益于防止把资源浪费在那些不可能得到好近似比的问题上。

机器学习方法在组合优化中应用得越来越多，但缺少理论保证是它最大的缺点，层次理论可以给机器学习算法赋予性能分析的框架，从而明白这些方法的优势和不足之处，通过创建起机器学习算法同传统近似算法之间的联系，可以设计出带有理论保证的学习加强算法。

强化学习在组合优化中取得成功之后，理论界开始关注如何给强化学习算法赋予近似比分析，怎样对训练过程的收敛性以及策略的质量展开分析，从而构建起强化学习算法的理论根基。

量子算法在一些组合优化问题上展现出来的优势需要有理论来加以说明，量子近似优化算法的性能分析包含着量子力学原理以及计算复杂性理论的融合，这种跨学科研究给理论发展赋予了新的机会。

启发式算法的设计往往是凭经验、靠直觉，缺乏理论上的指导，层次理论能够帮助我们了解不同的启发式方法适合什么场合，启发式方法的设计。通过对问题结构和算法性能之间的关系的分析，我们可以设计出更好的启发式方法。

局部搜索算法的收敛性分析是重要理论问题，研究解空间的结构特征，可以预测局部搜索算法的性能，局部最优解的质量与全局最优解的关系决定算法的近似比。

在线算法面对着更大的理论难题，由于算法要在不完全信息之下作出抉择，而竞争分析给在线算法赋予了性能评判的架构，不过它同近似比分析相比仍然存在差距，怎样把在线分析和近似分析统一起来，这是个值得探究的方向。

4.2未来研究方向与理论拓展

平均情况分析给了解算法性能带来了新的视角，很多算法在最坏情况下表现得不好，但在平常的实例上却能得到很好的结果，想要创建起平均情况下的近似理论，就必要把概率论和算法分析结合起来。

随机实例模型的研究有益于了解实际问题的特征，通过剖析算法在随机图，随机背包实例这些模型上的表现，可预估算法在实际应用中的表现，这样的剖析要依靠概率论，组合数学以及算法设计。

多目标优化问题体现了实际应用的复杂性，在这样的问题里，不同的目标之间常常存在矛盾，要在多个方面做出权衡，Pareto最优解的概念给多目标问题供应了理论根基，不过，关于其计算复杂性的分析还并不完善。

分布式算法发展需要拓展传统复杂性理论，在分布式环境中，通信复杂度是重要性能指标，如何在保持近似质量的前提下尽量减少通信开销，这是分布式近似算法面临的难题。

近似算法的实际性能受实现细节影响，算法常数因子、内存访问模式、并行性等都会影响实际运行时间，建立更贴近实际的性能分析模型是理论研究的方向。

机器学习与传统算法的结合产生了很多有趣的问题。学习增强的近似算法利用机器学习来预测实例特征，然后再选择一个合适的算法策略，这种技术将机器学习的灵活性与传统算法的理论保证相结合。

量子计算的发展给组合优化带来了新的可能性，量子叠加、量子纠缠等量子力学现象也许会对一些优化问题产生指数级加速，但量子算法的设计与分析需量子力学和计算复杂性理论的深度结合。

大数据环境下的组合优化问题有规模大、维度高、噪声多的特点，传统的算法分析框架可能不再适用，要开发新的理论工具，流算法、草图算法等技术给处理大规模数据带来新思路。

理论成果到实际应用的转化仍存有挑战，学术界关心的理论最优点和工业界关心的实际效果之间有差别，怎样规划出既有理论保障又具备实际效益的算法成为重要研究方向，这就须要理论研究者和实践工作者密切配合，一同推动组合优化理论与应用向前发展。

参考文献

[1]郭田德,李安琪,韩丛英.组合优化问题的机器学习求解方法[J].中国科学:数学,2025,55(02):451-480.

[2]鲁江涛.量子近似优化算法的研究及其应用[D].电子科技大学,2024.DOI:10.27005/d.cnki.gdzku.2024.004075.

[3]张宏立,朱家政,董颖超.强化学习求解组合优化问题的研究综述[J].新疆大学学报(自然科学版)(中英文),2023,40(02):129-141.DOI:10.13568/j.cnki.651094.651316.2023.02.02.0001.

[4]孙海禄.基于启发式算法求解组合优化问题[D].河北地质大学,2022.DOI:10.27752/d.cnki.gsjzj.2022.000733.

[5]孙建.基于图结构的组合优化问题近似算法研究[D].北京工业大学,2022.DOI:10.26935/d.cnki.gbjgu.2022.000039.

[6]杨一宸.若干网络优化问题的算法研究[D].华东理工大学,2021.DOI:10.27148/d.cnki.ghagu.2021.000455.

[7]张永飞.局部搜索算法求解组合优化问题[D].东北师范大学,2018.

[8]马玉玲.浅谈求解组合优化问题的几种近似算法[J].电脑知识与技术,2008,4(36):2819-2820.

 作者：江西工业贸易职业技术学院 曹成海

编辑：杜勇

审核：张建胜