arXiv:2504.03277v1 宣告类型: 新 摘要: 图着色问题是图算法中研究最多和最著名的問題之一。精确方法无法解决具有数百个以上顶点的实例，因此已经提出了大量的启发式方法。嵌套蒙特卡洛搜索（NMCS）和嵌套展开策略适应（NRPA）是单人游戏的蒙特卡洛搜索算法。令人惊讶的是，很少有工作专门评估蒙特卡洛搜索算法在组合图问题上的性能。在本文中，我们将展示如何高效地将蒙特卡洛搜索应用于图着色问题，并将这种 approach 与其现有的方法进行比较。