$n$ 座城市各访问一次再回到起点，求总里程最短的走法。可行解有 $(n-1)!/2$ 条，$n=20$ 就是 $6\times10^{16}$。但真正的困难不是数量，而是这个空间没有梯度：任何改动都是整段边的替换，你无法「稍微调整一点点」。连续优化里「沿坡往下走」的全部直觉，在这里一句都用不上。
但 TSP 并非一团乱麻。在平面上，最优路线一定不自交：两条边若交叉，换个接法必然更短（三角不等式）。这就是 2-opt——一条几何事实立刻砍掉一大片搜索空间。组合优化的全部功夫，就是找这种能砍掉一大片的结构。
$\pi$ 是走访顺序的一个排列，$S_n$ 是全部 $n!$ 个排列，$d$ 是两城距离，下标循环回到起点。写成整数规划更有用：$x_{ij}\in\{0,1\}$ 表示是否走边 $(i,j)$，约束每城进出各一次，外加子回路消除约束——否则解会退化成几个互不相连的小圈。这类约束有指数多条；Dantzig 等人 1954 年的对策是不预先写下，先解松弛，哪条被违反就补哪条——割平面法由此诞生。
TSP 同时是两件相反事情的样本：它是 NP-hard 的教科书例子，可 Concorde 求解器已精确解出 85900 城的实例并给出最优性证明。这不矛盾——NP-hard 是关于最坏情况的陈述，现实实例却带着几何结构，割平面正把它一条条兑换成约束。「理论上难」与「这个实例可解」之间那道缝隙，是整个运筹学工业站立的地方。
电路板钻孔与激光切割的走刀路径、基因组测序中 contig 的排序、望远镜观测调度、快递最后一公里，都是 TSP 或其变体。启发式一侧，LKH 用可变深度的边交换，在百万级实例上逼近最优 1% 以内。
既然求不到最优，退一步：能否保证「我的解不超过最优的 1.5 倍」，且对所有输入都成立？这与启发式有本质区别——启发式是「通常还行」，近似算法是带证明的承诺。
难点是个悖论：你根本不知道最优值 $\mathrm{OPT}$，怎么证明自己离它多近？出路是找一个算得出来的下界。TSP 中任何回路删掉一条边都是生成树，所以最小生成树长度 $\le \mathrm{OPT}$；于是只需证明「我 $\le c\times$ 下界 $\le c\times \mathrm{OPT}$」。整个近似算法领域，本质是一门构造好下界的手艺。
$\mathrm{ALG}(I)$ 是算法在实例 $I$ 上的输出，$\mathrm{OPT}(I)$ 是真实最优值，$\rho$ 与实例无关。Christofides 算法用最小生成树 + 奇度顶点上的最小完美匹配，对满足三角不等式的 TSP 给出 $\rho=3/2$；这个 1976 年的纪录直到 2020 年才被 $3/2-10^{-36}$ 撼动——数值微不足道，意义在于 $3/2$ 不是墙。
近似把 P vs NP 的二值问题展开成一条连续光谱：不再只问「能不能高效解」，而问「能高效逼近到什么程度」。更漂亮的是这条光谱本身有可证的硬边界——PCP 定理说明，除非 P=NP，集合覆盖的 $\ln n$ 已是最优，最大团连 $n^{1-\varepsilon}$ 都做不到。「有多难」从一句抱怨变成了可精确计算的量。
贪心的 $\ln n$ 集合覆盖是数据子集选择与测试精简的骨架；LP 松弛加随机舍入是云调度与预算分配的通用套路。机器学习里最直接的一条：子模函数在拟阵约束下最大化有 $1-1/e$ 的贪心保证（Nemhauser 等，1978），用于传感器布点、数据蒸馏、少样本示例挑选——「选一个多样又有代表性的子集」几乎总能写成这个形式。
一边是任务，一边是工人，连线表示「能做」，求最多的一对一配对。贪心会卡住：先配掉的一对，可能正好堵死后面两对。
解法是增广路：从一个未配对的点出发，交替走「未匹配边、已匹配边、未匹配边……」，若最终停在另一个未配对的点上，就把这条路上所有边的状态整体翻转——原来匹配的松开，原来没匹配的接上。路上匹配边比未匹配边少一条，翻转后总数恰好 $+1$。妙处是：它自动拆掉你先前的错误配法，无需回溯。Berge 定理更进一步：匹配最大 $\iff$ 不存在增广路——全局最优性被压缩成一个可局部验证的条件。
左式中 $M$ 取遍所有匹配，$C$ 取遍所有顶点覆盖（碰到每条边的顶点集）：最大匹配数等于最小覆盖数，这是对偶——「最多能配几对」的答案，同时就是「为何不能更多」的证明。右式中 $N(S)$ 是 $S$ 的邻居集：完美匹配失败当且仅当某个子集的候选人太少。瓶颈永远是一个具体子集，而非玄学的全局拥挤。
一般图里增广路会失效：奇圈让交替路绕回自身。Edmonds 1965 年的对策是「花」（blossom）——把整个奇圈缩成一个点，在缩图上继续搜索，找到后再展开。也正是在这篇论文里，他第一次主张「好算法」应定义为运行时间多项式增长。复杂性理论最核心的类 P，定义来自一篇讲怎么配对的论文。
全美肾脏配对交换（UNOS）靠最大权匹配救人；住院医师分配、广告位实时投放（在线二分匹配的 RANKING 算法有 $1-1/e$ 竞争比）、目标跟踪的数据关联，跑的都是同一套算法。而最优传输正是匹配的连续松弛，Sinkhorn 迭代把它变得可微，如今用于扩散模型与域自适应。
贪心——每次拿当前看起来最好的，绝不反悔——有时对得惊人（Kruskal 求最小生成树），有时错得离谱（TSP 的最近邻）。什么时候贪心是对的？拟阵给出了完整回答。
先看一个巧合：线性代数里的「线性无关向量组」与图论里的「不含圈的边集（森林）」，行为一模一样。其一，子集仍然无关；其二，两个无关集大小不同时，大的那个里一定能挑出一个元素补进小的，仍保持无关。把这两条抽出来当公理，就得到拟阵。第二条是关键：它保证你无论从哪起步，都不会走进「还没到最大却再加不进任何元素」的死胡同。
拟阵是一对 $(E,\mathcal{I})$：$E$ 是有限地面集（所有边、所有向量），$\mathcal{I}$ 是称作「无关集」的子集族，满足空集属于 $\mathcal{I}$、对取子集封闭，以及上式这条交换公理。直接推论是：所有极大无关集等大，这个公共大小就是秩——在向量空间里它是矩阵的秩，在图里是生成森林的边数。
Rado–Edmonds 定理：贪心对所有权重函数都返回最优解，当且仅当该结构是拟阵。这是精确的「当且仅当」，不是「贪心通常管用」这类经验之谈——数学难得能把一整类算法的适用范围一次划清。界线还往前走：两个拟阵的交仍可多项式求解（二分匹配恰是两个划分拟阵的交），三个就 NP-hard。分水岭画在「二」与「三」之间。
Kruskal 算法就是图拟阵上的贪心；带截止期的单机排程、网络可靠性同样落在拟阵框架里；编码理论中线性码对应向量拟阵。机器学习方面，子模函数是拟阵秩函数的推广：数据子集选择、主动学习、推荐多样性、上下文示例挑选，几乎都是「在拟阵约束下最大化子模函数」，概念 2 那个 $1-1/e$ 正从这个结构长出来。