摘要
基于学习的方法解决旅行商问题（TSP）时，通常通过解码或搜索后生成的路径进行评估，但所学习的对象往往存在于替代空间中，如热图、分配、构建策略或搜索引导分数。这掩盖了一个根本性的问题：在解码之前，实际上学习到了什么哈密顿结构？
本研究直接回答了这一问题，通过结构上有意义的潜在对象学习 TSP，而不是将大部分哈密顿结构留给最终解码阶段。基于连接构建的根植于 $1$-树的 Gibbs 家族，我们提出了一种名为 C2TSP 的端到端无监督学习管道。该管道通过隐式微分从无偏的 TSP 成本中学习残差边扰动。为了进行结构修正，一个平滑的 Held–Karp 层恢复期望的度平衡，而证书引导的锐化进一步推动连接分布向更像路径的结构发展。
实验结果表明，C2TSP 在保持可解释结构信息的同时，实现了强大的解码性能。消融实验进一步验证了边扰动和证书引导的锐化共同提升了路径成本与路径结构的相似性。
博主点评： 该研究通过引入结构化的潜在对象，显著提升了旅行商问题的求解效率与结果可解释性，展示了深度学习在组合优化问题中的新潜力。