Abstract

最近在解决大规模旅行商问题（TSP）方面的进展采用了热图引导的蒙特卡洛树搜索（MCTS）范式，其中机器学习（ML）模型生成热图，指示每个边作为最优解一部分的概率分布，以指导MCTS寻找解。然而，我们的理论和实验分析对基于ML的热图生成的有效性提出了质疑。为此，我们证明了一个简单的基线方法可以在热图生成中胜过复杂的ML方法。此外，我们对热图引导的MCTS范式的实践价值提出了质疑。为此，我们的发现显示了它与LKH-3启发式方法相比的劣势，尽管该范式依赖于特定问题的手工策略。对于未来，我们建议研究方向集中在开发更理论化的热图生成方法和探索自主、泛化的ML方法来解决组合问题。代码可供审查：https://github.com/xyfffff/rethink_mcts_for_tsp。

1. Introduction

旅行商问题（TSP）是一个经典的优化挑战，在物流、网络设计以及更广泛的运筹学（OR）领域有着重要的应用。传统上，通过像Concorde这样的精确算法