构造相连：学习旅行商问题中可处理的近环边缘分布

# 以构造保证连通：学习旅行商问题的可处理近游程边际分布  
来源：https://arxiv.org/html/2607.12127  

张馨远  
莱斯大学土木与环境工程系，休斯顿，TX  
钱新宇  
莱斯大学土木与环境工程系，休斯顿，TX  
通讯作者（2026年7月13日）  

###### 摘要  

学习型方法在旅行商问题（TSP）中的表现通常以解码或搜索后得到的游程来评估，但学习对象本身往往存在于替代空间，如热力图、赋值、构造策略或搜索引导分数。这掩盖了一个根本性问题：在解码之前，实际上学到了什么哈密顿结构？在本研究中，我们直接回答这一问题，通过一个有结构意义的潜在对象来学习TSP，而不是将大部分哈密顿结构留给最终解码阶段。基于一种通过构造确保连通的根11-树吉布斯族，我们提出了一种端到端无监督学习流程，称为*C2TSP*。该流程通过隐式微分从无偏TSP成本中学习残差边扰动。在结构校正方面，一个平滑的Held–Karp层恢复期望的度平衡，而证书引导的锐化进一步将连通分布推向更接近游程的结构。实验表明，C2TSP在保持可解释的结构信息的同时，实现了强大的解码性能。消融实验进一步验证了边扰动和证书引导锐化共同改善了游程成本和游程类似结构。  

## 1 引言  

机器学习方法越来越多地用于组合优化，因为它们能够在保持竞争性经验性能的同时提供快速的近似解。作为一个经典的组合优化问题，旅行商问题（TSP）受到了特别关注。一个可行的TSP解必须同时满足局部和全局结构约束：每个节点的度为2，且所选边必须形成一个连通的环。然而，许多基于学习的TSP方法并未在学习对象中直接表示这种全局连通边结构。自回归构造模型通过顺序生成游程，并利用掩码和解码规则逐步确保可行性[23（https://arxiv.org/html/2607.12127#bib.bib19），5（https://arxiv.org/html/2607.12127#bib.bib20），13（https://arxiv.org/html/2607.12127#bib.bib9），14（https://arxiv.org/html/2607.12127#bib.bib10）]。基于热力图的方法预测边分数，然后依赖修复、采样、局部搜索或树搜索来获得有效游程[8（https://arxiv.org/html/2607.12127#bib.bib24），21（https://arxiv.org/html/2607.12127#bib.bib25），17（https://arxiv.org/html/2607.12127#bib.bib12），22（https://arxiv.org/html/2607.12127#bib.bib29），15（https://arxiv.org/html/2607.12127#bib.bib30）]。赋值空间松弛方法，如基于Sinkhorn的方法，提供了平滑的置换类似对象，但并未直接建模决定游程成本的边邻接结构[16（https://arxiv.org/html/2607.12127#bib.bib11），20（https://arxiv.org/html/2607.12127#bib.bib28），18（https://arxiv.org/html/2607.12127#bib.bib27）]。混合方法如NeuroLKH使用学习信号来引导强大的手工启发式算法[25（https://arxiv.org/html/2607.12127#bib.bib14）]。尽管这些方法在可负担的推理时间内取得了强大的经验结果，但仍存在两个局限性：它们不提供连通组合对象上的可处理全局分布，且其最终性能可能与下游解码或搜索紧密耦合，使得学到的表示和后处理效果难以分离[24（https://arxiv.org/html/2607.12127#bib.bib26），7（https://arxiv.org/html/2607.12127#bib.bib34）]。  

相比之下，我们提出了一种基于根11-树族的“以构造确保连通”的表示。固定根节点后，一个根11-树由非根节点上的生成树以及恰好两条与根相连的边组成。因此，每个潜在配置通过构造是全局连通的，且恰好满足根节点的度约束。剩余的结构缺陷是非根节点的度不匹配：当每个非根节点的度也为2时，根11-树就变成了哈密顿环。与哈密顿环上的吉布斯分布（其配分函数难以处理）不同，根11-树吉布斯族允许精确因式分解，从而能够进行精确的边际计算和期望成本训练。这将我们的方法与经典的Held–Karp松弛联系起来，其中节点惩罚修改边成本，而最小11-树提供了强TSP下界[11（https://arxiv.org/html/2607.12127#bib.bib17），12（https://arxiv.org/html/2607.12127#bib.bib18）]。先前的工作已经从理论、启发式或学习角度探索了基于树或Held–Karp相关的TSP结构[19（https://arxiv.org/html/2607.12127#bib.bib35），10（https://arxiv.org/html/2607.12127#bib.bib36），9（https://arxiv.org/html/2607.12127#bib.bib37）]。我们的目标是将这种连通结构转化为一个端到端可微分的潜在表示，用于学习近游程边际分布。  

我们基于这种以构造确保连通的根11-树潜在族构建了一个端到端无监督学习流程，称为*C2TSP*。该模型首先预测残差边扰动，这些扰动以期望TSP成本为引导，将根11-树吉布斯分布向低成本结构倾斜。为了纠正剩余的非根节点度缺陷，我们引入了一个平滑的Held–Karp均衡化层，其动机在于与根11-树先验和经典Held–Karp下界结构的兼容性[11（https://arxiv.org/html/2607.12127#bib.bib17）]。该层求解节点加性对偶变量，使得每个非根节点在经对偶修改的根11-树分布下的期望度等于2，并通过隐式优化层的一般范式[2（https://arxiv.org/html/2607.12127#bib.bib1），1（https://arxiv.org/html/2607.12127#bib.bib2），4（https://arxiv.org/html/2607.12127#bib.bib3），6（https://arxiv.org/html/2607.12127#bib.bib4）]，通过微分均衡映射进行端到端训练。均衡化后，残差不再是连通性故障，而是被包含在连通、度平衡的潜在族内部的非游程质量。我们使用一个证书来控制这种残差缺陷，该证书通过非根节点度的总方差来上界非游程质量。随后，证书引导的残差精炼减少非游程质量，紧接着再进行一次重新均衡化。最后，解码通过从学到的边际分布中采样来完成，而不是基于搜索的后处理。  

本文的贡献如下：  

- •我们引入了一种用于TSP的可处理根11-树表示，它在确保全局连通性的同时，允许精确的边际计算用于期望成本训练。  
- •我们开发了C2TSP，一个端到端无监督学习流程，其中GNN从期望TSP成本预测残差边扰动，并通过平滑的Held–Karp均衡化层恢复期望的度平衡。  
- •我们推导了一个非游程质量证书，并用它来指导残差精炼，将学到的连通分布推向更接近游程的结构。  
- •我们通过实验表明，所提出的根11-树表示在纯解码性能上表现强劲，而几个基线方法则更受益于额外的局部搜索。进一步的消融实验显示了边扰动和证书引导锐化如何将连通分布推向更接近游程和更低成本的结构。  

## 2 方法  

### 2.1 问题定义  

#### 精确哈密顿吉布斯模型。  
设\(V=\{1,\ldots,n\}\)，并令\(\mathcal{E}\)为完全无向图的边集。每个哈密顿环\(H\in\mathcal{H}\)具有边关联向量\(x_H\in\{0,1\}^{|\mathcal{E}|}\)，且\(D\in\mathbb{R}^{|\mathcal{E}|}\)表示边成本向量。一个平滑的精确模型是哈密顿吉布斯律：  

\[
q_D^{\mathcal{H}}(H)=\frac{1}{Z_{\mathcal{H}}(D)}\exp\!\left(-\frac{1}{\tau}\langle D,x_H\rangle\right),\qquad H\in\mathcal{H},
\tag{1}
\]

其中\(Z_{\mathcal{H}}(D)\)是哈密顿配分函数。该模型难以处理，因为计算\(Z_{\mathcal{H}}(D)\)和对\(\log Z_{\mathcal{H}}(D)\)求微分需要对指数级数量的哈密顿环求和。  

#### 以构造确保连通：根11-树替代模型。  
由于精确哈密顿吉布斯推断难以处理，我们追求一个具有结构保证的可处理替代模型，它应该：（1）保留核心游程结构；（2）证明其所留下的结构差距；（3）在下面发展的均衡化保证下，学会缩小这个差距。注意，哈密顿环总是一个连通的、每个节点度为2的边集。我们通过使用根11-树来保持连通性，并通过一个平滑的Held–Karp（HK）均衡化层来处理剩余的度条件。固定一个根\(r\in V\)，令\(\bar{V}:=V\setminus\{r\}\)。设\(\mathcal{U}_r\)表示根11-树族，即在\(\bar{V}\)上的生成树加上恰好两条与\(r\)相连的边。每个\(U\in\mathcal{U}_r\)通过构造是连通的，满足\(d_r(U)=2\)，并具有边关联向量\(x_U\in\{0,1\}^{|\mathcal{E}|}\)。容易验证\(\mathcal{H}\subseteq\mathcal{U}_r\)。对于任意边参数\(\eta\in\mathbb{R}^{|\mathcal{E}|}\)，我们定义根11-树吉布斯律：

\[
q_{\eta}(U)=\frac{1}{Z_r(\eta)}\exp\!\left(-\frac{1}{\tau}\langle\eta,x_U\rangle\right),\qquad U\in\mathcal{U}_r,
\tag{2}
\]

及其边际分布：

\[
\mu(\eta):=\mathbb{E}_{q_{\eta}}[x_U].
\tag{3}
\]

引理2.1（https://arxiv.org/html/2607.12127#S2.Thmtheorem1）表明可处理边际（2（https://arxiv.org/html/2607.12127#S2.E2））具有精确配分函数，是可处理的。剩余的任务是形式化边参数\(\eta\)，使其保持度二结构并减少\(\mathcal{U}_r\)内部的结构缺陷。  

###### 引理 2.1（可处理的根11-树边际）。  
(2)中的配分函数\(Z_r(\eta)\)分解为\(\bar{V}\)上的加权生成树配分函数和一个两边的根选择规范化因子。因此，\(Z_r(\eta)\)、边边际\(\mu(\eta)\)以及所有度矩都可以精确计算。  

### 2.2 Held–Karp均衡化与结构差距证书  

给定11-树吉布斯族，剩下的哈密顿条件是强制非根节点的度为二。由于吉布斯律由边成本参数化，非根节点度约束的对偶价格需要表示为边加性场。对于由\(\bar{V}\)索引的\(\lambda\in\mathbb{R}^{n-1}\)，定义节点到边的提升映射\(A:\mathbb{R}^{n-1}\to\mathbb{R}^{|\mathcal{E}|}\)为：

\[
(A\lambda)_{ij}= \begin{cases} \lambda_i+\lambda_j, & i,j\in\bar{V},\\ \lambda_k, & \{i,j\}=\{r,k\},\ k\in\bar{V}. \end{cases}
\tag{4}
\]

那么，对于每个\(U\in\mathcal{U}_r\)，

\[
\langle A\lambda,x_U\rangle = \sum_{i\in\bar{V}} \lambda_i d_i(U).
\tag{5}
\]

因此\(A\lambda\)恰好是非根节点度价格的边加性表示。对于一般的边成本场\(c\in\mathbb{R}^{|\mathcal{E}|}\)，考虑关于11-树吉布斯族的熵正则化度校正问题：

\[
\min_{p\in\Delta(\mathcal{U}_r)} \quad \sum_{U\in\mathcal{U}_r} p(U)\langle c,x_U\rangle + \tau \sum_{U\in\mathcal{U}_r} p(U)\log p(U)
\tag{6}
\]

\[
\mathrm{s.t.}\quad \sum_{U\in\mathcal{U}_r} p(U) d_i(U)=2,\qquad i\in\bar{V},
\]

其中\(\Delta(\mathcal{U}_r)\)表示根11-树上的概率单纯形。该问题寻找一个具有最小自由能的连通根11-树分布，其非根节点度的期望匹配哈密顿目标。将提升恒等式(5)代入拉格朗日函数，会将度乘子合并为一个倾斜边成本\(c+A\lambda\)，从而保持根1-树族中的配分函数形式，记为\(q_{c+A\lambda}\)，如下所述。  

###### 定理 2.2（平滑Held–Karp均衡）。  
(6)的拉格朗日对偶为：

\[
\max_{\lambda\in\mathbb{R}^{n-1}} \Phi_{\tau}(c,\lambda),\qquad \Phi_{\tau}(c,\lambda):=-\tau\log Z_r(c+A\lambda)-2\mathbf{1}^{\top}\lambda.
\tag{7}
\]

此外，

\[
\frac{\partial \Phi_{\tau}(c,\lambda)}{\partial \lambda_i} = \mathbb{E}_{q_{c+A\lambda}}[d_i(U)]-2,\qquad i\in\bar{V},
\tag{8}
\]

\[
\frac{\partial^2 \Phi_{\tau}(c,\lambda)}{\partial \lambda_i \partial \lambda_j} = -\frac{1}{\tau} \operatorname{Cov}_{q_{c+A\lambda}}\bigl(d_i(U),d_j(U)\bigr),\qquad i,j\in\bar{V}.
\tag{9}
\]

因此\(\Phi_{\tau}(c,\lambda)\)关于\(\lambda\)是凹的，并且任何平稳最大化点\(\lambda^{\star}(c)\)满足：

\[
\mathbb{E}_{q_{c+A\lambda^{\star}(c)}}[d_i(U)]=2,\qquad i\in\bar{V}.
\tag{10}
\]

证明见附录A.2（https://arxiv.org/html/2607.12127#A1.SS2）。定理2.2表明，度乘子通过\(\langle A\lambda,x_U\rangle - 2\mathbf{1}^{\top}\lambda\)进入每个11-树的能量，而对\(p\in\Delta(\mathcal{U}_r)\)的优化恢复了吉布斯律\(q_{c+A\lambda}\)。因此，HK层是由\(\nabla_{\lambda}\Phi_{\tau}(c,\lambda^{\star}(c))=0\)定义的隐式映射\(c\mapsto \lambda^{\star}(c)\)。这个均衡化消除了连通替代模型中的度缺陷。剩下的结构差距是分配给度平衡的根11-树但不在哈密顿环支撑内的残差概率质量。下一个结果证明了这一残差差距。  

#### 结构差距证书。  
令\(\mathcal{N}:=\mathcal{U}_r\setminus\mathcal{H}\)，且\(\gamma(q):=q(\mathcal{N})\)表示非游程11-树的集合及其质量。HK均衡化仅强制了期望意义上的度平衡：\(\mathbb{E}_q[d_i(U)]=2\)。