论文标题
旅行相同的道路：一种新颖的TSP解决策略
Travel the Same Path: A Novel TSP Solving Strategy
论文作者
论文摘要
在本文中，我们提供了解决旅行推销员问题的新型策略，这是在TCS社区中深入研究的著名组合优化问题。特别是，我们考虑模仿学习框架，这有助于确定性算法在需要时做出很好的选择，从而使速度提高，同时保持解决方案的确切性，而不会遭受不可预测性和潜在的大偏差。 此外，我们证明了在模仿学习框架下训练的图神经网络的强大概括能力。具体而言，该模型能够比基线更快地求解TSP的大实例，而在训练时仅看到小型TSP实例。
In this paper, we provide a novel strategy for solving Traveling Salesman Problem, which is a famous combinatorial optimization problem studied intensely in the TCS community. In particular, we consider the imitation learning framework, which helps a deterministic algorithm making good choices whenever it needs to, resulting in a speed up while maintaining the exactness of the solution without suffering from the unpredictability and a potential large deviation. Furthermore, we demonstrate a strong generalization ability of a graph neural network trained under the imitation learning framework. Specifically, the model is capable of solving a large instance of TSP faster than the baseline while has only seen small TSP instances when training.
