直接学习可解释的近似环结构，提升旅行商问题求解性能
Connected by Construction: Learning Tractable Near-Tour Marginals for Traveling Salesman Problems
- 基于连通构造的1-树吉布斯族，端到端学习可解释的边扰动
- 在200节点测试中平均路径成本低于基准方法4.3%，且结构更接近哈密顿环
- 适合需要可解释性与高质量解的组合优化研究者
基于学习的旅行商问题（TSP）方法通常通过解码或搜索生成的路径进行评估，但其学习对象常位于热图、分配、构造策略或搜索引导分数等代理空间中，隐藏了解码前实际学到的哈密顿结构。本文提出一种名为C2TSP的端到端无监督学习框架，直接通过结构有意义的潜在对象学习TSP。基于连通构造的根1-树吉布斯族，模型通过隐式微分学习来自无偏TSP代价的残差边扰动。为实现结构校正，引入平滑的Held-Karp层以恢复期望度平衡，再通过证书引导锐化进一步推动分布向更类环结构靠近。实验表明，C2TSP在解码性能上表现优异，同时保持可解释的结构信息；消融实验验证了边扰动与证书引导锐化共同提升了路径成本和环状结构质量。
原文摘要 · Abstract (English)
Learning-based methods for the traveling salesman problem (TSP) are often evaluated through the tours produced after decoding or search, but the learned object itself frequently lives in a surrogate space such as heatmaps, assignments, construction policies, or search-guidance scores. This hides the fundamental question: what Hamiltonian structure has actually been learned before decoding? In this study, we directly answer this question by learning TSP through a structurally meaningful latent object, rather than leaving most of the Hamiltonian structure to the final decoding stage. Based on a connected-by-construction rooted $1$-tree Gibbs family, we propose an end-to-end unsupervised learning pipeline called \emph{C2TSP}. The pipeline learns residual edge perturbations from unbiased TSP cost through implicit differentiation. For structural correction, a smoothed Held--Karp layer restores expected degree balance, while certificate-guided sharpening further pushes the connected distribution toward more tour-like structures. Experiments show that C2TSP yields strong decoding performance while preserving interpretable structural information. Ablations further verify that edge perturbation and certificate-guided sharpening jointly improve both tour cost and tour-like structure.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。