破解TSP难题：识别关键"例外边"的闭合理论

旅行商问题（TSP）是组合优化领域最经典也最棘手的NP难问题之一。TSP要求找到访问所有给定城市恰好一次并返回起点的最短路径，对于n个城市，可能的路径数为(n-1)!/2，即使n=20也已超过10^16种可能。目前没有已知的多项式时间精确算法能在所有情况下求解此问题，最佳精确方法（如Concorde求解器使用的分支定界与切割平面）在最坏情况下仍需指数时间。在欧氏TSP中——城市位于欧氏平面上，边的权重为欧氏距离——大多数最优路径的边都是"局部合理"的：它们连接近邻节点，符合Delaunay三角剖分的直觉。

Delaunay三角剖分是计算几何中的核心构造：给定平面上的点集，它构造一种三角剖分使得没有任何点落在其他三角形的外接圆内。这一性质使得Delaunay边倾向于连接"自然近邻"的点对。研究表明，对于随机均匀分布的点集，最优TSP解中约95%以上的边属于Delaunay三角剖分。然而，真正让TSP变难的，往往是剩余那少数几条"不寻常"的边。近日，一位研究者在Reddit上发表了一项探索性工作，试图从数学上精确刻画这些"例外边"，为强化学习（RL）与神经组合优化（NCO）求解器提供可验证的结构先验。

从求解器直觉到闭合问题

这项研究是作者此前工作的延续。在之前的"无预训练、逐实例PPO求解器"中，作者引入了"例外边"（exception edge）的概念，作为PPO的一种归纳偏置。近端策略优化（PPO）是OpenAI于2017年提出的策略梯度强化学习算法，通过裁剪目标函数限制策略更新幅度，兼顾训练稳定性与样本效率。在神经组合优化领域，RL被用于训练神经网络直接构造或改进组合优化问题的解，典型范式包括自回归构造（逐步选择下一个访问城市）和改进式方法（学习局部搜索算子的选择策略）。"逐实例PPO"指的是针对每个具体问题实例从头训练策略网络，避免分布外泛化问题但计算成本较高。

其核心直觉是：一个良好的欧氏TSP路径中，绝大多数边都短小、连接近邻、类似Delaunay边，是"局部不出奇"的；而少数几条非局部的边，可能决定了搜索能否跳出局部最优的"盆地"。在组合优化中，搜索空间的"盆地"结构描述了哪些初始解最终会收敛到同一个局部最优——同一盆地内的解通过局部移动可以相互到达，而盆地之间的"屏障"代表了需要暂时恶化解质量才能跨越的区域。例外边可能恰好横跨两个盆地之间，提供从一个局部最优跳到更好局部最优的"捷径"。

但这最初只是一个求解器层面的假设。此后，作者放下了PPO，转而追问一个更基础的问题：能否从数学上精确定义什么是"例外边"？答案是将其转化为一个闭合问题（closure problem）。

在图论和组合优化中，闭合问题通常指在有向图中寻找权重最大的闭合子集。本文中"闭合"的含义有所不同：它指的是用一条边将一条哈密顿路径"闭合"为哈密顿回路——给定两个端点之间的哈密顿路径（访问所有节点恰好一次的路径），加上连接这两个端点的边即可形成完整的哈密顿回路。这一操作将"是否使用某条非标准边"转化为了一个精确的成本比较问题。

例外阈值的精确定义

作者固定一个稀疏的基准图 $G_0$（例如弱Delaunay图），一条边是否"例外"只相对于这个基准而言。弱Delaunay图是Delaunay三角剖分的一种放松版本，允许点恰好位于外接圆上的退化情况，通常比严格Delaunay图包含更多的边。具体定义如下：

• $Z_0$：仅使用基准边构成的最便宜哈密顿回路；
• $H_e$：对于某条非基准边 $e$，仅用基准边连接其两个端点的最便宜生成哈密顿路径；
• $c(e)$：用边 $e$ 闭合该路径的成本。

由此得到精确的"单例外阈值"：当一条非基准边所闭合的哈密顿路径节省的成本超过该边自身的成本时，这条边就在结构上变得有用。换言之，一个恰好包含一条例外边的路径，可以击败仅用基准边的最优解。数学上，这等价于 $\ ext{cost}(H_e) + c(e) < Z_0$，即闭合后的回路总长度严格小于纯基准边的最优回路。

有意思的是，这并不意味着 $e$ 一定属于全局最优解，也不代表它是被强制包含的。它只是揭示了这条边具有"结构性价值"——打破了仅使用"常规"边时能达到的最优性屏障。

负面结果揭示的关键洞察

通往闭合模型的道路并非一帆风顺。作者坦诚地分享了几次失败的尝试，这恰恰是这项工作严谨性的体现。

在早期的TSPLIB试点中，通用几何CUT提议方法在11条参考的非Delaunay边中，仅能解释其中2条。随后的密度-CUT实验虽然发现了许多路径连续的区域，但对这11条例外边的解释率竟然是0。

这些失败传递出一个清晰的信号：单纯的几何划分并不足够。真正关键的对象，是基准哈密顿路径与闭合它的那条边之间的"兼容性"。这一认识最终催生了闭合模型的构建思路——问题的本质不在于几何位置，而在于路径与闭合边的成本博弈。这意味着不能仅凭一条边的长度、角度或它跨越的几何区域来判断它是否"例外"，而必须考虑整个路径结构如何与这条边相互配合。

核心实验结果验证

作者在两个层面验证了理论的有效性。

小规模精确语料库验证

在一个冻结的、$n \le 12$ 的精确小规模自然语料库上：

• 51/51 个"强制例外"实例在 $q=1$ 闭合层被精确解释；
• 当前的充分不等式安全认证了其中 48/51 个实例；
• 在98个精确有益对中，88个被安全认证；
• 安全候选上集将15,054个非Delaunay对压缩至644个，同时保留了该语料库中全部600个精确 $q=1$ 支撑对。

这意味着该方法能在大幅缩减候选空间的同时，不丢失关键的结构信息——将候选边从15,054条压缩到644条（压缩比超过23:1），同时零遗漏地保留了所有真正有用的边。这对TSP求解器而言极具价值，因为候选集大小直接决定了搜索算法的计算复杂度。

大规模实例LIN318验证

对于经典的LIN318实例（完全图含50,403条边）——这是TSPLIB基准库中由Lin和Kernighan于1973年提出的318城市实例，其已知最优解长度为42,029：

• 实验搜索图仅包含1,500条边：988条弱Delaunay边加512条独立生成的候选边；
• 在512条候选边中，有13条具有正的"安全增益下界"；
• 从严格的候选限定2/3-opt路径（长度42,210）出发，经过验证的强制闭合见证，再进行候选限定的2/3-opt优化，最终达到42,108；
• 已知最优解为42,029，最终残差仅为79，约 0.188%。

这里的2-opt和3-opt是TSP中经典的局部搜索算子：2-opt删除路径中的两条边并以另一种方式重连（实质上翻转路径的一个子段），3-opt则删除三条边有多种重连方式。"候选限定"意味着仅考虑预定义候选集中的边进行交换，将每步搜索的计算量从O(n²)或O(n³)大幅降低，但可能错过某些改进。从50,403条边压缩到1,500条边的搜索图上仍能达到0.188%的残差，说明了结构先验在缩减搜索空间方面的巨大潜力。

研究局限性的诚实说明

作者对这项工作的边界保持了高度清醒。他明确指出：

• 1,500条边的搜索图并非完全由阈值理论生成；
• 剩余的499个候选是"不确定"，而非被认证为负例；
• LKH被用于生成和验证闭合见证，因此42,108并非一个"无LKH"的独立求解结果；
• 这只是一次探索性的大规模实验，而非受控的求解器基准测试。

LKH（Lin-Kernighan-Helsgott）是由Keld Helsgott开发的TSP求解器，被广泛认为是实践中最强大的TSP启发式算法之一，通过复杂的k-opt移动和精心设计的候选边生成策略，能在合理时间内找到接近最优甚至最优的解。作者在实验中依赖LKH意味着结果验证了理论框架的合理性，但不能证明该框架能独立替代强力求解器。

他反复强调：不宣称对TSP的多项式时间求解，不宣称对例外边的完整分类，也不宣称每条 $\kappa>1$ 的边都是全局最优的。

对强化学习与神经组合优化的潜在意义

这项工作最初的动机始终是基于学习的组合优化。神经组合优化（NCO）是近年来兴起的研究方向，试图用深度学习模型（如Transformer、图神经网络）直接学习组合优化问题的求解策略，代表性工作包括Pointer Network、Attention Model（AM）、POMO等。这些方法的核心挑战之一是如何有效利用问题的结构特性——纯粹的端到端学习往往难以发现深层的组合结构。

作者认为，例外边理论可作为一种可验证的结构先验，在以下方面发挥作用：

• 缩减动作空间或候选边空间，让RL智能体在更小的搜索空间中学习——这直接缓解了组合爆炸问题，因为动作空间从O(n²)级别降至与候选集大小成正比的规模；
• 识别"门户"（portals），即那些可能连接原本相互隔离的局部搜索盆地的边——这为RL的探索策略提供了明确的方向指引，避免在同一盆地内无效采样；
• 区分普通局部边与结构性关键闭合边——这可以转化为注意力机制中的先验权重或图神经网络中的边特征；
• 为课程学习或排序模型提供已认证的正例与不确定案例——课程学习（curriculum learning）按照从易到难的顺序安排训练样本，闭合理论自然提供了难度分级。

作者建议的下一步实验，是在冻结预算下对比"有"与"无"闭合式候选引导的RL/NCO求解器性能——而非与高度工程化的经典求解器LKH做正面比拼。这是一种务实的实验设计：不试图证明学习方法能击败数十年工程优化的经典方法，而是验证结构先验是否能让学习方法在固定计算预算下获得实质性提升。

结语与开放问题

作者已在GitHub上公开了完整的理论、证明草图、核心精确预言机、安全证书、LIN318实验产物以及30项测试，并提供确定性复现。他特别希望社区就三个问题给出反馈：

1. 这种哈密顿闭合的形式化，是否已在其他名称下被研究过？
2. 对于端点约束的哈密顿路径 $H_e$，是否存在更强的可计算下界？
3. 闭合式候选引导究竟更适合作为RL/NCO的归纳偏置，还是应纯粹作为经典候选生成方法？

第二个问题尤其值得关注：如果能找到更紧的下界（例如基于松弛的LP下界或1-tree下界），就能在不求解NP难子问题的前提下更精确地筛选候选边。第三个问题则触及了一个更深层的争论——结构知识应该"硬编码"进算法还是让学习器自己发现。

这项研究的价值或许不在于它"解决"了什么，而在于它以严谨、诚实的方式，为理解TSP的"困难来源"提供了一个可验证的新视角——将玄妙的"哪条边重要"转化为一个可精确计算的成本博弈问题。它暗示了一种可能的研究路径：通过理解问题结构来引导学习，而非寄望于纯粹的端到端学习自动发现所有结构。