组合优化概述

复杂度类	含义	实际策略
P	存在高效精确算法	直接求解
NP-Complete	可验证但（可能）不可高效求解	近似算法或启发式
NP-hard	至少与NP-Complete一样难	启发式或特殊结构利用

三、精确方法

精确方法保证找到全局最优解，但在最坏情况下可能需要指数级时间。

3.1 穷举法（暴力搜索）

穷举法是最直观的方法，即遍历可行解空间中的所有解，逐一计算目标函数值并记录最优解。

算法框架：

输入：可行解空间 F，目标函数 f
输出：最优解 x*

best_value ← +∞
for each x ∈ F do
    if f(x) < best_value then
        best_value ← f(x)
        x* ← x
return x*

特点：

保证找到最优解；
时间复杂度为 \( O(|\mathcal{F}|) \)，通常为指数级或阶乘级；
仅适用于小规模问题实例。

适用场景：问题规模极小（如 \( n \leq 15 \) 的TSP），或作为其他算法正确性验证的基准。

3.2 分支定界法

分支定界法（Branch and Bound）是求解组合优化问题最常用的精确方法之一。其核心思想是将搜索空间系统地划分为更小的子问题（分支），并通过计算下界（定界）来剪除不可能包含最优解的子空间。

基本原理：

设原问题为 \( P_0 \)，分支定界法维护一个活跃节点列表。对每个节点（子问题）\( P_i \)：

分支：将 \( P_i \) 分解为若干互不相交的子问题 \( P_{i1}, P_{i2}, \ldots \)；
定界：计算每个子问题的目标函数下界 \( LB(P_{ij}) \)；
剪枝：如果 \( LB(P_{ij}) \geq UB \)（当前已知最优解的值），则剪去该子问题。

关键要素：

分支策略：如何将问题分解为子问题；
定界方法：如何计算有效的下界（如线性松弛、拉格朗日松弛）；
搜索策略：深度优先、宽度优先或最佳优先。

下界计算示例（以整数规划为例）：

对于整数规划问题，通过求解其线性松弛（去掉整数约束）得到下界：

\[ LB = \min{c^T x : Ax \leq b, , x \geq 0} \leq \min{c^T x : Ax \leq b, , x \in \mathbb{Z}^n_+} \]

3.3 动态规划

动态规划（Dynamic Programming）利用问题的最优子结构和重叠子问题性质，通过将原问题分解为子问题并存储子问题的解来避免重复计算。

最优子结构：问题的最优解包含其子问题的最优解。

状态转移方程：设 \( V(S, i) \) 为某个子问题的最优值，动态规划通过状态转移方程建立子问题之间的递推关系。

经典示例——TSP的动态规划解法（Held-Karp算法）：

设 \( d(S, i) \) 表示从起点出发，经过集合 \( S \) 中所有城市，最终到达城市 \( i \) 的最短路径长度。状态转移方程为：

\[ d(S, i) = \min_{j \in S \setminus {i}} \left[ d(S \setminus {i}, j) + c_{ji} \right] \]

其中 \( c_{ji} \) 为城市 \( j \) 到城市 \( i \) 的距离。

时间复杂度：\( O(2^n \cdot n^2) \)
空间复杂度：\( O(2^n \cdot n) \)

虽然仍为指数级，但相比穷举法的 \( O(n!) \) 有显著改进。

动态规划适用条件：

问题具有最优子结构；
子问题之间存在重叠（否则分治法更合适）；
状态空间规模可接受。

3.4 其他精确方法

割平面法：通过逐步添加有效不等式（割平面）来收紧线性松弛，直至得到整数最优解；
分支定价法（Branch and Price）：结合列生成与分支定界，适用于变量数量极大的问题；
约束规划（Constraint Programming）：通过约束传播和搜索相结合来求解组合问题。

四、近似算法与近似比

4.1 近似算法的动机

对于NP-hard问题，当问题规模较大时精确算法不可行。近似算法在多项式时间内给出一个近似最优解，并提供解的质量保证。

4.2 近似比的定义

对于最小化问题，算法 \( A \) 的近似比（approximation ratio）\( \rho \) 定义为：

\[ \frac{A(I)}{OPT(I)} \leq \rho, \quad \forall I \]

其中 \( A(I) \) 为算法对实例 \( I \) 给出的解的目标值，\( OPT(I) \) 为最优解的目标值。

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

\[ \frac{OPT(I)}{A(I)} \leq \rho, \quad \forall I \]

近似比 \( \rho \geq 1 \)，\( \rho \) 越接近1说明近似算法越好。

4.3 近似算法示例

顶点覆盖问题的2-近似算法

问题：给定无向图 \( G = (V, E) \)，找到最小的顶点子集 \( C \subseteq V \)，使得每条边至少有一个端点在 \( C \) 中。

算法：

C ← ∅
E' ← E
while E' ≠ ∅ do
    选取 E' 中任意一条边 (u, v)
    C ← C ∪ {u, v}
    删除 E' 中所有与 u 或 v 关联的边
return C

近似比证明：算法选取了 \( k \) 条边，这些边互不相邻，因此最优解至少需要 \( k \) 个顶点来覆盖这些边。而算法返回 \( 2k \) 个顶点，故近似比为2。

集合覆盖问题的贪心近似算法

问题：给定全集 \( U \) 和 \( U \) 的子集族 \( \mathcal{S} = {S_1, S_2, \ldots, S_m} \)，找到最少数量的子集使其并集覆盖 \( U \)。

贪心算法：每次选择覆盖最多未覆盖元素的子集。

近似比：\( H(n) = \sum_{k=1}^{n} \frac{1}{k} = O(\ln n) \)，其中 \( n = |U| \)。

4.4 近似方案

多项式时间近似方案（PTAS）：对于任意 \( \varepsilon > 0 \)，存在 \( (1+\varepsilon) \)-近似算法，其运行时间为输入规模的多项式（但可能是 \( \varepsilon \) 的指数函数）；
完全多项式时间近似方案（FPTAS）：运行时间同时为输入规模和 \( 1/\varepsilon \) 的多项式。

例如，0-1背包问题存在FPTAS，时间复杂度为 \( O(n^2 / \varepsilon) \)。

4.5 不可近似性

某些问题在特定假设下被证明不存在好的近似算法：

除非 \( P = NP \)，TSP（一般情况）不存在常数近似比的多项式时间算法；
除非 \( P = NP \)，集合覆盖问题不存在近似比优于 \( (1 - o(1)) \ln n \) 的多项式时间算法；
最大团问题不存在 \( n^{1-\varepsilon} \) 近似比的多项式时间算法（在某些复杂度假设下）。

五、启发式与元启发式概述

5.1 启发式算法

启发式算法（Heuristics）是针对特定问题设计的快速求解方法，通常基于问题的结构特征和经验规则。它们不保证找到最优解，也不提供近似比保证，但在实践中往往能快速给出高质量的解。

常见构造型启发式：

贪心法：每一步选择当前最优的局部决策；
最近邻法（用于TSP）：从起始城市出发，每次访问最近的未访问城市；
插入法（用于TSP）：逐步将城市插入到当前回路中代价最小的位置。

常见改进型启发式：

2-opt/3-opt（用于TSP）：通过交换路径中的边来改进当前解；
Or-opt：移动路径中的一段到另一位置；
局部搜索：在当前解的邻域中寻找更优解。

5.2 元启发式算法

元启发式（Metaheuristics）是一类通用的高层搜索策略框架，适用于广泛的组合优化问题。它们通过平衡探索（exploration）和开发（exploitation）来在搜索空间中有效寻找高质量解。

5.2.1 模拟退火（Simulated Annealing）

模拟退火模拟物理退火过程，通过控制“温度“参数来决定是否接受劣解：

以概率 \( \exp(-\Delta f / T) \) 接受比当前解差的邻域解；
温度 \( T \) 随迭代逐渐降低（冷却）；
高温阶段易于跳出局部最优，低温阶段趋于精细搜索。

接受准则：对于新解 \( x’ \)，如果 \( f(x’) < f(x) \) 则接受；否则以概率

\[ P(\text{accept}) = \exp\left( -\frac{f(x’) - f(x)}{T} \right) \]

接受该解。

5.2.2 遗传算法（Genetic Algorithm）

遗传算法模拟生物进化过程：

编码：将解表示为“染色体“；
选择：根据适应度选择优秀个体；
交叉：组合两个个体产生新个体；
变异：对个体进行随机扰动。

其核心思想是通过种群的演化，逐代产生更好的解。

5.2.3 禁忌搜索（Tabu Search）

禁忌搜索通过维护一个禁忌列表来避免搜索过程中的循环：

每次移动后，将相关操作加入禁忌列表；
禁忌列表中的操作在一定迭代次数内不允许执行；
通过释放准则（aspiration criteria）允许在特定条件下解禁。

5.2.4 蚁群算法（Ant Colony Optimization）

蚁群算法模拟蚂蚁觅食行为：

人工蚂蚁根据信息素浓度和启发式信息构造解；
信息素更新：好的解对应的路径上信息素增加；
信息素蒸发：避免过早收敛。

路径选择概率：

\[ p_{ij} = \frac{[\tau_{ij}]^\alpha \cdot [\eta_{ij}]^\beta}{\sum_{k \in \mathcal{N}i} [\tau{ik}]^\alpha \cdot [\eta_{ik}]^\beta} \]

其中 \( \tau_{ij} \) 为信息素浓度，\( \eta_{ij} \) 为启发式信息（如距离的倒数），\( \alpha, \beta \) 为权重参数。

5.2.5 其他元启发式

粒子群优化（PSO）：模拟鸟群觅食行为；
差分进化（DE）：基于种群的连续优化方法，可适用于离散问题；
变邻域搜索（VNS）：系统地改变邻域结构进行搜索；
迭代局部搜索（ILS）：在局部搜索的基础上加入扰动机制；
自适应大邻域搜索（ALNS）：通过破坏和修复操作进行搜索。

5.3 启发式与元启发式的比较

特征	启发式	元启发式
问题依赖性	强（针对特定问题）	弱（通用框架）
解的质量保证	无（或有限）	无（但通常更好）
计算效率	通常很快	需要较多计算时间
实现复杂度	较低	中等到高
参数调节	少	需要调参

六、常见组合优化问题分类

6.1 路径与路由问题

旅行商问题（TSP）：找到经过所有城市恰好一次的最短回路；
车辆路径问题（VRP）：用有限车辆为客户配送，最小化总行驶距离；
最短路径问题：在带权图中找到两点间的最短路径（属于P类）；
中国邮递员问题：找到经过所有边至少一次的最短回路。

6.2 分配与调度问题

指派问题：将任务一对一地分配给工人，最小化总成本（属于P类）；
作业车间调度（Job Shop Scheduling）：在多台机器上安排工件加工顺序；
流水车间调度（Flow Shop Scheduling）：工件按固定顺序经过多台机器；
并行机调度：在多台相同机器上分配任务以最小化完工时间。

6.3 背包与装箱问题

0-1背包问题：从物品中选择子集放入容量有限的背包，最大化总价值；
多维背包问题：具有多个约束维度的背包问题；
装箱问题（Bin Packing）：将物品装入最少数量的箱子中；
切割下料问题：从原材料中切割所需规格，最小化废料。

6.4 图论问题

图着色问题：用最少颜色对图的顶点着色，使相邻顶点不同色；
最大独立集问题：找到图中最大的互不相邻顶点集合；
最大团问题：找到图中最大的完全子图；
顶点覆盖问题：找到最小顶点集覆盖所有边；
最小生成树：找到连接所有顶点的最小权重树（属于P类）。

6.5 网络设计问题

斯坦纳树问题：找到连接指定终端节点的最小权重树；
网络流问题：在网络中传输最大流量或最小费用流（部分属于P类）；
设施选址问题：确定设施位置以最小化总服务成本；
网络可靠性设计：设计满足连通性要求的最低成本网络。

6.6 覆盖与划分问题

集合覆盖问题：用最少子集覆盖全集；
集合划分问题：将全集划分为互不相交的子集；
集合包装问题：选择最多互不相交的子集。

6.7 问题难度一览

问题	复杂度类	最佳已知精确算法
最短路径	P	\( O(m + n \log n) \)
最小生成树	P	\( O(m \alpha(n)) \)
指派问题	P	\( O(n^3) \)
0-1背包	NP-hard（弱）	\( O(nW) \)（伪多项式）
TSP	NP-hard（强）	\( O(2^n \cdot n^2) \)
图着色	NP-hard（强）	\( O(2^n \cdot n) \)

七、求解策略的选择

7.1 问题规模与方法选择

在实际应用中，选择求解方法需要综合考虑以下因素：

问题规模：小规模（\( n < 20 \)）可用精确方法；中等规模（\( 20 \leq n \leq 100 \)）可尝试分支定界；大规模（\( n > 100 \)）通常需要启发式或元启发式；
解的质量要求：是否需要最优解或近似解即可满足需求；
时间约束：是离线优化还是需要实时响应；
问题结构：是否存在可利用的特殊结构（如稀疏性、对称性）。