论文分享：The Transformer Network for the Traveling Salesman Problem

旅行商问题（TSP）是经典的组合优化问题，其目标是在访问每个城市（节点）一次并最终返回起点的条件下，找到一条最短路径。传统的求解方式分为精确算法与近似/启发式算法，精确算法保证最优解但难以处理大规模问题；近似算法牺牲部分最优性以提高求解效率。近年来，利用深度学习与强化学习技术，研究者尝试寻找更好的求解规则。本文介绍了一种基于Transformer网络的SOTA方法。

传统的TSP求解方式包括动态规划、整数规划等精确算法和启发式算法。启发式算法虽非最优但具有较高的求解效率。

本文方法采用编码-解码结构。编码器使用标准Transformer，解码器为自回归解码器，通过beam search预测路径。编码器将所有节点映射至编码空间，解码器预测路径，包含四个步骤：应用自注意力、生成query、更新状态、生成节点。

TSP表示为序列优化问题，解码目标为最大化序列概率。本文使用beam search求解。实验结果显示，本文方法在TSP50和TSP100上与最优解的差距显著缩小，提高了基于学习的启发式方法的性能。

综上，本文提出的方法为解决TSP问题提供了一种新颖的神经网络解决方案，通过Transformer网络在大规模问题上展现出优于传统算法的性能。