论文标题
在蒙特卡洛树上搜索加权顶点着色
On Monte Carlo Tree Search for Weighted Vertex Coloring
论文作者
论文摘要
这项工作介绍了使用流行的蒙特卡洛树搜索（MCTS）方法的首次研究，并结合了解决加权顶点着色问题的专用启发式方法。从基本的MCT算法开始，我们逐渐引入了许多算法变体，其中通过包括贪婪和本地搜索启发式的各种模拟策略扩展了MCT。我们对众所周知的基准实例进行实验，以评估每个研究组合的值。我们还提供了经验证据，以阐明每种策略的优势和限制。
This work presents the first study of using the popular Monte Carlo Tree Search (MCTS) method combined with dedicated heuristics for solving the Weighted Vertex Coloring Problem. Starting with the basic MCTS algorithm, we gradually introduce a number of algorithmic variants where MCTS is extended by various simulation strategies including greedy and local search heuristics. We conduct experiments on well-known benchmark instances to assess the value of each studied combination. We also provide empirical evidence to shed light on the advantages and limits of each strategy.
