C2TSP：基于连通构造的TSP边缘分布学习
速览
针对TSP学习方法只在代理空间学特征的问题，该研究提出C2TSP，基于连通1-树Gibbs族进行无监督学习。通过隐微分从无偏TSP代价学习残差边扰动，并引入平滑Held-Karp层和证书引导锐化使分布接近环游结构。实验表明C2TSP在保持可解释结构的同时取得强解码性能。
AI 深度解读
背景
旅行商问题（Traveling Salesman Problem, TSP）是组合优化领域的基础性 NP-hard 问题，目标是在完全图中找到一条恰好访问每个节点一次并返回起点的最短哈密顿回路（tour）。近年来，基于学习的方法被广泛用于 TSP 求解，例如使用神经网络生成热力图（heatmaps）、分配矩阵（assignments）、构造策略（construction policies）或搜索引导分数（search-guidance scores）。这些方法通常通过解码或搜索后得到的最终 tour 来评估性能，而学习对象本身却往往存在于一个替代空间（surrogate space）中。这掩盖了一个根本问题：在解码之前，模型实际上学到了什么样的哈密顿结构（Hamiltonian structure）？ 现有方法大多将哈密顿结构的构建完全留给最后的解码阶段，导致中间的潜在表示缺乏结构上的可解释性。本文直接回答了这个问题——通过学习一个具有结构意义的潜变量来直接表征 TSP 的哈密顿特性，而非依赖后续解码拼凑出回路。
核心内容
本文提出一种名为 C2TSP（Connected-by-Construction TSP）的端到端无监督学习管道，其核心思想是让模型直接学习一个“天生连通”的分布，而不是在解码后才体现连通性。具体来说，C2TSP 基于一个连通的、按构造方式定义的 rooted 1-tree Gibbs 族（connected-by-construction rooted 1-tree Gibbs family）来建模 TSP 的边际分布。该分布由一系列残差边扰动（residual edge perturbations）参数化，并通过隐式微分法（implicit differentiation）从无偏的 TSP 代价（即真实 tour 长度）中学习这些扰动。
为了确保学习到的分布逐渐接近真正的 tour 结构，模型引入了两个关键矫正机制：
-
平滑的 Held–Karp 层（Smoothed Held–Karp Layer）：恢复期望的度平衡（expected degree balance）。经典的 Held–Karp 下界通过松弛度约束来逼近 TSP 最优值，C2TSP 将其平滑化并作为可微层嵌入网络，使得模型输出的边际分布满足每个节点度数为 2 的期望约束。
-
证书引导锐化（Certificate-Guided Sharpening）：进一步将连通分布推向更接近 tour 的结构。该过程利用“证书”（certificate）——即从当前分布中抽取的子图是否接近哈密顿回路的判定信息——来引导概率锐化，使高概率边更集中地形成回路骨架。
实验表明，C2TSP 在解码（例如使用 beam search 或 2-opt 后处理）后能取得与传统 SOTA 方法相当甚至更优的 tour 代价，同时保留了可解释的结构信息——即模型直接输出的边际分布本身已经呈现了清晰的近-tour 模式（near-tour marginals），而不仅仅是热力图。消融实验进一步验证：边扰动与证书引导锐化的联合使用，同时改善了 tour 代价和结构近似度（tour-like structure）。
关键要点
- 解决了“学习阶段到底学到了什么哈密顿结构”这一根本问题，而不是把结构构建全部推给解码。
- 提出基于 connected-by-construction rooted 1-tree Gibbs 族 的潜变量建模，确保从构造上保证分布的连通性。
- 使用 隐式微分 从无偏 TSP 代价中学习残差边扰动，实现端到端无监督训练。
- 平滑 Held–Karp 层 以可微方式恢复度平衡，使分布逼近真实 tour 的度数约束。
- 证书引导锐化 利用子图结构信息推动分布从一般连通图向哈密顿回路靠拢。
- 实验显示：C2TSP 在最终 tour 质量上不低于主流方法，且提供可直接解释的结构化边际概率。
- 消融实验证明：边扰动与证书引导锐化两个组件对性能和结构都有正向贡献。
意义与影响
本文的工作开辟了学习型 TSP 方法中“结构先于解码”的新范式。传统方法将大部分结构化工作（如保证连通性、度约束）后置到解码搜索中，而 C2TSP 从训练阶段就开始学习具有明确图论意义的近-tour 分布，这使得模型输出本身就能反映出对问题结构的理解。这一思路不仅增强了解释性，也为后续设计更透明的组合优化学习系统提供了基础——例如，模型可以直接输出“哪些边很可能属于最优回路”，而无需依赖黑箱解码。此外，无监督训练方式避免了需要大量最优解作为标签的局限，提升了实用性。Held–Karp 层的可微化及其与证书引导的结合，也为其他需要度约束的图优化问题（如 VRP、分配问题）提供了可迁移的技术组件。总体而言，C2TSP 在性能与可解释性之间取得了平衡，有望推动学习型组合优化从“端到端黑箱”向“结构与搜索协同”的方向演进。