组合优化¶
Chapter 1: 组合优化绪论¶
Section 1.1: 组合优化的基本概念¶
-
应用对象：离散对象。
-
特点：
- 解的数量是有限的 \(\rightarrow\) 理论上可通过枚举（了解）得到最优解。
- 涉及高级数学与最优化理论。
- 困难性：通常不能穷举（解空间过大），也不能求导（变量不是连续型）。
- 现状：组合优化领域既缺少好的模型，也缺少好的求解工具。
- 学科基础：数学规划、图论和组合学、线性代数/矩阵、计算复杂性、数据结构。
- 应用领域：计算机科学 (CS)、管理科学、计算生物学。
Section 1.2: 经典组合优化模型¶
1. 背包问题 (Knapsack Problem, KP)
- 情况 ①：松弛形式 (Relaxed/Fractional)
- 定义：物品可分割。
- 最优解性质：贪心策略，一直放入“性价比”最高的物品；放不下则切割。
- 证明：任意交换法 (Exchange Argument)，交换后总价值变小。
- 情况 ②：标准形式 (0/1 Knapsack)
- 定义：物品不可切割。
- 性质：最优解没有普遍的简单性质（体现了组合优化的困难）。
2. 旅行商问题 (TSP)
- 可行解：一个城市的序号序列（等同于全排列）。
- 解的数量：\(\frac{A_{n}^{n}}{n} = (n-1)!\)。
3. 车辆路径问题 (VRP)
- 输入：\(n\) 个顾客（需求 \(q_v\)）、\(K\) 辆车（容量 \(Q\)）、仓库及距离。
- 约束：\(\sum q_{v} \le Q\)。
- 目标：最小化总路程。
4. 指派问题 (Assignment Problem)
- 输入：\(n\) 任务，\(n\) 员工，成本 \(C_{ij}\)。
- 目标：\(\min \sum C_{ij}\)。
- 算法：匈牙利算法 (\(O(n^{4})\))。
Section 1.3: 图论基础与相关问题¶
基本概念
- 图 (Graph): \(G = (V, E)\)，其中 \(V\) 为顶点集，\(E\) 为边集。
- 子图 (Subgraph): \(V^{\prime} \subseteq V, E^{\prime} \subseteq E\)。
- 生成子图 (Spanning Subgraph): \(V^{\prime} = V\) (包含所有顶点)。
树 (Trees)
- 定义：连通的无圈图。
- 最小生成树 (MST): 赋权图中权重和最小的生成树。
- 最小 Steiner 树问题: 允许增加点（Steiner点）的生成树。
- Gilbert - Pollak 猜想：最小 Steiner 树权和 \(\ge \frac{\sqrt{3}}{2}\) MST 权和。
- 应用：进化树、芯片设计。
欧拉图与邮递员问题
-
Euler 回路: 经过所有边恰好一次的闭迹（条件：连通且 0 个奇度点）。
-
Euler 路: 经过所有边恰好一次的非闭迹（条件：连通且 2 个奇度点）。
-
中国邮递员问题 (CPP):
-
目标：走遍所有边并回到起点，路程最短。
-
求解：若无 Euler 回路，需“重复”经过某些边（转化为匹配问题）。
-
Section 1.4: 图上选址问题 (Location Problems)¶
(注：此处紧接 9.22.pdf 内容，作为图论应用的深入例子)
1. 1-median 选址 (打麦场模型)
-
问题：寻找一点，使所有点到该点的加权距离和最小。
-
结论：最优解必在图的顶点上。
-
求解策略：
-
树状图 (无圈)：使用“进一法”。
-
抓取度为 1 的叶子，比较其权重 \(P_1\) 与其余部分权重。
-
若 \(P_{Total} > 2P_1\)，则将叶子合并入邻接内顶点（\(P_2 \leftarrow P_2 + P_1\)），删去叶子。
-
递归直到只剩两点。
-
-
有圈图：使用“破圈法”。
-
“道路有回环，每圈甩一段... 结果逐一算，算后再比较”。
-
将有圈图转化为树进行计算。
-
-
2. p-median 选址
- 在图中选 \(p\) 个点。属于 NPC 问题，是组合优化的基本问题。
Section 1.5: 算法的分类¶
(注：9.22.pdf 中对算法定义的讨论，属于绪论中的基本定义)
-
算法 (Algorithm)：解决问题的一组名义明确、可有限步执行的规则。
-
分类：
-
精确算法：求最优解，通常为指数时间。
-
近似算法：在多项式时间 \(O(P(n))\) 内运行，保证解的质量（如 \(r_A \to 3/2\)）。
-
启发式算法 (Heuristic)：基于经验，不保证界限，通过相对比较寻找较好解。
-
Chapter 2: 计算复杂性¶
Section 2.1: 问题与实例¶
-
问题 (Problem)：一般性的提问（如 TSP, KP）。
-
实例 (Instance)：参数取具体值的一个特例（如 \(n=50, w_i=...\)）。
-
优化问题 vs 判定问题：
-
优化问题：求极值（如 KP 求最大价值）。
-
判定问题：回答 Yes/No（如 KP 是否存在价值 \(\ge K\) 的解）。
-
关系：二者在计算复杂性上通常是多项式等价的（可通过二分查找互相转化）。
-
Section 2.2: 输入规模 (Input Size)¶
-
定义：存储一个实例所需的计算机存储单元数（二进制编码长度）。
-
数值 vs 编码：
-
整数 \(u\) 的数值为 \(u\)，但编码长度为 \(\log u\)。
-
\(f(u) = O(u)\) 对于输入规模 \(\log u\) 而言是指数级的。
-
-
具体问题的规模：
-
背包问题 (KP)：\(Size(I) \approx \sum \log w_i + \sum \log p_i + \log c\)。
-
旅行商问题 (TSP)：\(Size(I) \approx n^2 + \sum \log c_{ij}\)。
-
-
最大数 \(m(I)\)：实例中出现的最大整数。
Section 2.3: 时间复杂度与伪多项式时间¶
-
多项式时间算法：\(T(I) = O(P(Size(I)))\)。
-
指数时间算法：复杂度不能被输入规模的多项式界定。
-
伪多项式时间 (Pseudo-polynomial time)：
-
定义：复杂度是 \(Size(I)\) 和 \(m(I)\)（最大数值）的多项式函数，即 \(T(I) = O(P(Size(I), m(I)))\)。
-
例子：背包问题的 \(O(n \cdot W)\) 算法。虽然对数值 \(W\) 是多项式，但因 \(W\) 可达 \(2^{Size}\)，故对 \(Size\) 是指数的。
-
-
强多项式时间：
- 复杂度 \(T(I) = O(P(Size(I)))\) 且不依赖于数值 \(m(I)\)（即不会因为输入数字变大而显著变慢）。
Section 2.4: 算法效率与分类¶
-
时间复杂度回顾
-
伪多项式时间 (Pseudo-polynomial): \(O(mL)\), \(O(L \log n)\)。
-
多项式时间 (Polynomial): \(O(n^2)\), \(O(n \log L)\)。高效/实用算法。
-
指数时间 (Exponential): \(O(n 2^n)\), \(O(n!)\), \(O(2^n \cdot L)\)。低效/不实用。
-
-
任务分配问题案例
-
几项任务，第 \(j\) 个所需时间 \(p_j\)。
-
规模: \(n + \lceil \log_2 L \rceil\) (\(L\) 为最大数值)。
-
Section 2.5: 图灵机与计算模型¶
Church-Turing Thesis (丘奇-图灵论题)
- 猜想：所有在某合理的计算模型上可计算的函数，都能用图灵机计算。
图灵机 (Turing Machine, TM) 定义
-
结构：
-
一条（或多条）读写带：无限长方格，每个方格存一个字母表符号。
-
一个读写头：可移动。
-
一个状态控制器：包含有限个状态。
-
一组有限指令（程序）：即状态转移函数 \(\delta\)。
-
-
状态转移：\(\delta(q, \sigma) = (q', \sigma', \{L, R\})\)。
- 当前状态 \(q\)，读到符号 \(\sigma\) \(\rightarrow\) 转移到新状态 \(q'\)，写入新符号 \(\sigma'\)，读写头向左(L)或向右(R)移动。
-
瞬间像 (Configuration)：某一时刻图灵机的完整信息（带子内容、读写头位置、当前状态）。
DTM vs. NTM
-
确定性图灵机 (DTM)：状态转移函数是单值的。计算过程是一条路径。
- 判定问题：Halt & Output Yes/No。
-
非确定性图灵机 (NTM)：
-
状态转移函数是多值的（在一步有多种选择）。
-
计算过程是一棵计算树。
-
接受条件：只要计算树中存在一条路径能 Halt 并输出 "Yes"，则该实例被接受。
-
时间复杂度：该成功路径上的步数。
-
-
注：NTM 不是一个物理上合理的计算模型（不同于概率图灵机 PTM），但在理论分析中至关重要。
Section 2.6: P 类与 NP 类¶
定义
-
P 类 (Polynomial time)：DTM 在多项式时间内可解的问题类。
-
NP 类 (Nondeterministic Polynomial time)：NTM 在多项式时间内可解的问题类。
- 等价定义（验证定义）：若一个问题的解（证书/Certificate）可以在多项式时间内被 DTM 验证，则该问题属于 NP。
-
关系：\(P \subseteq NP\)（因为 DTM 是特殊的 NTM）。
-
核心开放问题：\(P = NP\) ?
常见问题举例
-
素数判定 (Primes)：属于 P 类 (AKS 算法)。
-
Subset Sum (子集和)：属于 NP 类（给定一个子集，验证其和是否为目标值是容易的），但不知道是否属于 P。
-
不可解问题：NTM 也不可解的问题（如停机问题）。
Section 2.7: NP 完全性 (NP-Completeness)¶
定义
-
NPC (NP-Complete)：NP 中最难的问题。
-
性质：若某个 NPC 问题存在多项式时间算法，则所有 NP 问题都有多项式时间算法（即 \(P=NP\)）。
归约 (Reduction)
-
多项式时间归约 (\(\le_m^P\))：
-
对于两个判定问题 \(\Pi_1\) 和 \(\Pi_2\)。
-
若存在多项式时间可计算的函数 \(f\)，使得对于 \(\Pi_1\) 的任意实例 \(I_1\)，有 \(I_2 = f(I_1)\) 是 \(\Pi_2\) 的实例，且：
- \(I_1\) 的答案为 "Yes" \(\iff\) \(I_2\) 的答案为 "Yes"。
-
则称 \(\Pi_1\) 多项式归约到 \(\Pi_2\) (\(\Pi_1 \le_m^P \Pi_2\))。
-
-
意义：
-
\(\Pi_2\) 不会比 \(\Pi_1\) 更容易（\(\Pi_2\) 至少和 \(\Pi_1\) 一样难）。
-
若有算法解 \(\Pi_2\)，则必可解 \(\Pi_1\)。
-
-
NPC 的正式定义：
一个问题 \(\Pi\) 是 NPC，如果：
-
\(\Pi \in NP\)。
-
对于任意 \(\Pi' \in NP\)，都有 \(\Pi' \le_m^P \Pi\)。
-
-
NP-Hard：满足条件 2 但不一定满足条件 1 的问题。
Section 2.8: 经典 NPC 问题与证明¶
第一个 NPC 问题：SAT (可满足性问题)
-
Cook-Levin 定理：Cook 运用图灵机语言证明了 SAT 是 NPC。
-
SAT 问题描述：给定布尔逻辑的合取范式 (CNF)，是否存在一种变量赋值使表达式为真？
- 暴力解法：\(O(2^n)\)。
-
Karp 的贡献：利用 SAT 构造归约，证明了 20 余个组合优化问题是 NPC。
证明 NPC 的通用步骤
-
证明 \(\Pi \in NP\)（通常构造一个多项式时间的验证算法）。
-
选取一个已知的 NPC 问题 \(\Pi_{known}\)。
-
证明 \(\Pi_{known} \le_m^P \Pi\)（构造归约）。
经典归约例子
-
3-SAT:
-
SAT 的特例，每个子句恰好包含 3 个文字。
-
结构规范，比 SAT 更简明，常用于后续归约。
-
SAT \(\le_m^P\) 3-SAT: 通过引入新变量将长子句拆解。
-
注：2-SAT 是 P 问题。
-
-
Hamilton Cycle (HC) \(\le_m^P\) TSP
-
HC 问题：判断图中是否存在经过所有顶点恰好一次的圈。
-
TSP (判定版)：是否存在长度 \(\le M\) 的回路？
-
归约构造：
-
给定 HC 实例 \(G=(V,E)\)。
-
构造 TSP 实例：城市集 \(V\)，距离 \(C_{ij} = 1\) 若 \((v_i, v_j) \in E\)，否则 \(C_{ij} = 2\)。阈值 \(M = |V|\)。
-
证明：\(G\) 有 HC \(\iff\) TSP 有长度为 \(|V|\) 的回路。
-
-
-
子图同构 (Subgraph Isomorphism)
-
包含 HC 问题作为特例（令子图 \(H\) 为 \(n\) 个顶点的圈），故也是 NPC。
-
图同构 (Graph Isomorphism)：难度介于 P 和 NPC 之间（目前未被证明是 NPC）。
-