arXiv:2502.00767v1 公告类型：交叉 摘要：深度学习在解决欧几里得旅行商问题（TSP）等组合优化问题方面显示出显著的潜力。然而，现有TSP算法的大多数训练和测试实例都是从特定的分布（如均匀分布）中随机生成的。这导致了对深度学习算法在离分布外（OOD）泛化场景中的性能分析和理解不足，这些场景与组合优化领域的最坏情况性能密切相关。对于数据驱动的算法而言，随机生成数据集的统计属性至关重要。本研究构建了一种名为最近邻密度的统计量，用于验证随机生成数据集的渐近性质，并揭示基于学习的求解器的贪婪行为，即总是选择最近邻节点来构建解路径。基于这种统计量，我们开发了依赖于分布转移或实例扰动的可解释的数据增强方法，并验证了基于学习的求解器在增强数据上的性能明显下降。此外，使用增强数据微调基于学习的求解器进一步增强了它们的泛化能力。总之，我们揭示了基于学习的TSP求解器存在过度贪婪的局限性，这可能对AI赋能的组合优化求解器具有深远的影响。