💻 computer science

Connected by Construction: Learning Tractable Near-Tour Marginals for Traveling Salesman Problems

该论文提出了 C2TSP，一种端到端的无监督学习流水线，通过一个构造性连接的根 1-tree Gibbs 系列直接学习旅行商问题的可解释哈密顿结构，在通过残差边扰动和证书引导锐化来保留结构信息的同时，实现了强大的路径性能。

原作者： Ke Sun, Xinyuan Zhang, Xinwu Qian

发布于 2026-07-15

📖 1 分钟阅读☕ 轻松阅读

原作者： Ke Sun, Xinyuan Zhang, Xinwu Qian

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下你正在尝试解决一个终极配送路线谜题：旅行商问题（Traveling Salesman Problem, TSP）。你有一份城市列表，你需要找到一条经过每一个城市且仅经过一次，最后回到原点的最短路径。这是一个经典的脑力挑战，随着城市数量的增加，它会变得极其困难。

长期以来，计算机科学家一直试图教机器使用“基于学习”的方法来解决这个问题。把这些方法想象成一个学生，他拿到一张地图并被要求猜出最佳路线。但问题在于，大多数这类“学生”实际上是在猜测一张“热力图”（一张显示哪些道路可能较好的模糊图片）或者一套“构建规则”（如何一步步构建路线）。在他们尝试将猜测解码为真实路径之前，他们并没有真正掌握最终那条完整、连通的闭环。这就像是在还没看到蛋糕长什么样之前，就先去猜配料，然后寄希望于烤箱能神奇地把这些配料变成一个完美的蛋糕。

本文的作者 Ke Sun、Xinyuan Zhang 和 Xinwu Qian 说：“等等。如果我们不知道蛋糕在进烤箱之前长什么样，我们怎么知道自己学对了东西呢？”

核心思想：先构建一个连通的骨架

与其猜测一张模糊的热力图，作者提出了一种名为 C2TSP 的新学习方法。他们的秘诀在于一个被称为“通过构造实现连通”（connected-by-construction）的概念。

想象你正在构建一个城市的道路网络模型。大多数方法试图在纸上画线，并希望它们稍后能连接起来。C2TSP 则从构建一个特定的、坚固的骨架——根树 1-tree 开始。

骨架： 想象一个中心枢纽（“根”城市）连接着两条路。然后，想象一棵由道路组成的树，将所有其他城市连接到这个枢纽。
魔力： 通过这种方式构建，模型可以保证是连通的。你不会意外地画出一条通往虚无或将城市分割成两个孤岛的道路。这就像建造一座房子，其地基确保了墙壁一定会触及屋顶。

这个骨架唯一缺失的，就是要成为一个完美巡回（哈密顿回路）所需的条件：每个城市必须恰好连接两条路（一进一出）。在 1-tree 中，枢纽有两个连接，但其他城市可能拥有三条路或者只有一条路。

修复方案：“平衡行为”层

为了修复多余或缺失的道路，团队使用了一个被称为平滑 Held–Karp 平衡层（smoothed Held–Karp equilibration layer）的巧妙技巧。

把这想象成一个非常聪明的交通调度员。模型观察 1-tree 骨架并问道：“嘿，城市 A 有三条路，但它只需要两条。城市 B 有一条，但需要两条。”调度员并不只是删除道路；他会调整道路的“价格”。他会让多余的道路变得昂贵，让缺失的道路变得便宜，从而推动系统进行调整，直到平均而言，每个城市恰好有两条路。

这是一个巨大的突破，因为与其他试图一次性猜测整个路线的方法不同，该方法在保持结构连通的同时，计算了每条道路成为解的一部分的精确概率。他们从数学上证明了他们可以完美地进行这种计算，而这在以前被认为是对于完整的巡回问题是无法实现的。

“证书”：安全网

即使经过了平衡行为，系统中可能仍会残留一点点“混乱”。骨架是连通且平均平衡的，但它可能还不是一个完美的回路。

作者引入了一个证书（certificate），它就像是一个安全网或警告标签。它精确地衡量系统中还剩多少“混乱”（或非巡回质量）。这是一个数学保证，它说：“我们知道结构已经完成了 99%，这里是剩余 1% 的确切数值。”

利用这个证书，他们应用了一个称为锐化（sharpening）的最后步骤。想象你有一张略显模糊的路线照片。锐化步骤会让好的道路看起来非常明亮，让差的道路看起来很暗，从而推动模型向一个完美的、清晰的回路靠拢。

他们的发现

团队在包含 50、100、200、500 甚至 1,000 个城市的谜题上测试了他们的方法。以下是数据展示的结果：

纯解码： 当他们让模型在没有任何额外帮助（比如人工修正）的情况下直接选择最佳路线时，C2TSP 的表现极其强大。在一个 100 城市的谜题中，经过 100 轮局部搜索后，它找到的路线最优性差距仅为 1.90%；而仅用简单的“挑选最佳”猜测时，差距为 4.83%。
对比： 其他流行的方法，如 DIFUSCO 或 Fast-T2T，在面对大型谜题（500+ 城市）时往往表现挣扎，除非使用大量的额外搜索时间。C2TSP 则保持了稳定性。
“消融”测试： 为了证明他们的想法奏效，他们拆除了系统的一部分。
- 如果没有边扰动（edge perturbation，即调整道路价格的部分），误差会从 1.55% 跳升至 12.74%。
- 如果没有锐化，模型虽然学会了连通结构，但无法如此接近完美的回路。
- 这证明了学习道路价格和最后的锐化步骤对于获得最佳结果都是必要的。

他们并未声称的事项

需要注意的是，这篇论文并没有声称解决了旅行商问题。他们明确表示，他们的方法依赖于一个“易处理的代理”（tractable surrogate）——即一种聪明的近似。根树 1-tree 是完美巡回的一个替代物。虽然它非常接近，但论文承认，剩余的“度波动”（degree fluctuations，即城市拥有 3 条路而非 2 条路的微小缺陷）虽然得到了控制和减少，但并未总是被完全消除。

他们还指出，对于非常大的谜题（如 1,000 个城市），一些使用大量局部搜索的方法（如 DIMES）仍然可以表现出色，但当你想获得一个本身就具有强大结构性的强力起点时，C2TSP 更为出众。

总结

简单来说，C2TSP 就像是教机器人通过先强制构建一个连通的骨架，然后教它如何平衡道路，最后给它一个证书来检查自己的工作，从而构建巡回路线。它不再是猜测一张模糊的图片并寄希望于它变成一条路线，而是让机器人学习路线本身的形状。结果表明，这种“通过构造实现连通”的方法使学习过程更加稳定，并且最终的路线更好，尤其是在谜题变得庞大且复杂时。

技术摘要：通过构造实现连接 (C2TSP)

问题定义

本文研究了旅行商问题（TSP），这是一个经典的组合优化问题，要求解必须满足两个结构约束：局部度约束（每个节点的度数必须为 2）和全局连通性（所选边集必须构成一个单一的哈密顿回路）。

目前的基于学习的 TSP 方法通常无法在学习到的对象中直接表示这种全局连通结构。相反，它们依赖于：

自回归构造： 通过程序化掩码顺序生成路径。
基于热图的方法： 预测边得分，并依赖下游的修复、采样或搜索来获得有效路径。
分配空间松弛： 建模平滑的类置换对象，但这些对象并不直接捕捉决定路径成本的边邻接结构。

这些方法存在两个主要局限性：它们无法提供关于连通组合对象的易处理全局分布；且其性能与下游解码或搜索过程紧密耦合，导致难以将学习到的表示质量与后处理效果区分开来。

方法论：C2TSP

作者提出了 C2TSP（Connected by Construction，通过构造实现连接），这是一个端到端的无监督学习流水线，通过一个具有结构意义的潜在对象——**根树 1-树（rooted 1-tree）**来学习 TSP。

1. 根树 1-树代理

模型并非尝试直接学习哈密顿回路（其配分函数是难解的），而是操作于 根树 1-树 这一族。

定义： 根树 1-树由所有非根节点（ $\bar{V}$ ）上的生成树以及恰好两条与固定根节点（ $r$ ）相连的边组成。
结构保证： 通过构造，该族中的每种配置都是全局连通的，并且满足根节点度数约束（ $d_r = 2$ ）。
易处理性： 与哈密顿 Gibbs 分布不同，根树 1-树 Gibbs 族允许精确分解。这使得精确计算配分函数 $Z_r(\eta)$ 、边边缘分布 $\mu(\eta)$ 和度矩成为可能，从而实现了无需采样的期望成本训练。

2. 平滑 Held–Karp 平衡化

根树 1-树的主要结构缺陷是非根节点的度数可能不等于 2。为了修正这一点，作者引入了一个 平滑 Held–Karp (HK) 平衡化层。

该层通过求解节点加性对偶变量（ $\lambda$ ）来倾斜边成本，使得在修改后的 Gibbs 分布下，每个非根节点的期望度数等于 2。
该层通过隐式微分通过平衡映射进行端到端训练，遵循隐式优化层的范式。
这一过程确保了学习到的分布在期望上是度平衡的，消除了“度缺陷”并保持了连通性。

3. 基于证书的锐化

即使经过 HK 平衡化，分布中仍可能包含非路径结构的概率质量（即不是哈密顿回路的根树 1-树）。

证书： 作者推导出了一个证书，利用非根节点度的总方差来上界化这种“非路径质量”（ $\gamma(q)$ ）： $\gamma(q) \leq \frac{1}{2} \sum \text{Var}(d_i)$ 。
精炼： 基于证书的锐化步骤使用 Bernoulli 上界证书的导数，将边缘分布推向更接近路径的结构。这起到了一种确定性精炼的作用，惩罚低概率边并奖励高概率边，从而降低了认证的非路径质量上界。

4. 学习流水线

该流水线从无偏 TSP 成本中学习 残差边扰动（ $\Gamma_\theta$ ）。

前向传播： 原始成本被扰动，经过投影以移除节点加性成分，通过 HK 平衡化层，最后通过基于证书的锐化进行精炼。
损失函数： 模型使用基于学习到的边边缘的期望 TSP 成本进行无监督训练，无需显式的结构约束惩罚项（因为这些约束已由架构强制执行）。

核心贡献

易处理的根树 1-树表示： 本文引入了一种表示方法，通过构造确保了全局连通性，同时允许进行精确的边缘计算以进行训练。
C2TSP 流水线： 一个端到端的无监督框架，结合了用于残差边扰动的图神经网络（GNN）和用于度平衡的平滑 Held–Karp 层。
非路径质量证书： 推导出了一个界定剩余结构差距的证书，并利用该证书驱动锐化机制，从而将分布推向哈密顿回路。
实验验证： 证明了根树 1-树表示能产生强大的纯解码性能，并且在集成到 LKH-3 等经典求解器时保持鲁棒，这与几种热图基准方法在较大规模下表现下降的情况形成对比。

实验结果

作者在 2-D 对称欧几里得 TSP 实例（TSP-50 到 TSP-1000）上对 C2TSP 进行了评估，对比基准包括 DIFUSCO、DIMES、Fast-T2T、UTSP 和 NeuroLKH。

纯解码： 在 25 种测试配置（不同问题规模和解码器水平）中，C2TSP 在 20 种配置中达到了最低的最优性差距。值得注意的是，它在具有重度局部搜索预算（例如 100 次 2-opt 迭代）的场景下表现最佳，这表明学习到的分布已经编码了强大的路径结构。
LKH 集成： 当作为 LKH-3 求解器的候选源时，C2TSP 在所有问题规模下都保持稳健，始终保持在距离原始 LKH-3 约 1 个万分之一（‱）以内。相比之下，热图方法（DIFUSCO、Fast-T2T、UTSP）在集成 LKH 时，在较大规模（ $n \geq 500$ ）下性能显著下降。
消融研究：
- 去除边扰动会导致性能大幅下降（平均差距从 1.55% 增加到 12.74%），表明学习残差边几何形状的必要性。
- 基于证书的锐化通过精炼边缘分布进一步提升了性能，证实了仅靠低松弛成本不足以实现高质量解码。

重要性与主张

本文声称，可微的潜在对象是学习型 TSP 的核心建模选择。通过在解码之前编码连通性，C2TSP 暴露了一个“近路径边缘”，其结构演化可以被训练、认证和分析。

作者认为，其工作标志着一种转变：从学习无约束的边得分转向学习一个具有明确结构意义且易于处理的近路径边缘。他们主张，这种方法将学习到的表示与后处理分离，使得模型能够为局部搜索过程提供全局一致的起点。

论文也承认了其设计选择中固有的局限性：根树 1-树放宽了精确的哈密顿回路支撑。虽然连通性得到了强制执行，且度平衡在期望上得到了恢复，但剩余的度波动是通过平衡化和锐化而非精确消除来控制的。作者建议，这为开发更紧密的证书导向更新和更丰富的易处理连通族开辟了方向。