用蒙特卡洛搜索解决图着色问题，效果优于传统方法。
Monte Carlo Graph Coloring
- 将蒙特卡洛搜索框架改造用于图着色
- 在多个实例上达到更优着色结果
- 适合需要高质量解的组合优化场景
图着色是图算法中研究最广泛、最著名的难题之一。精确算法在超过数百个顶点的实例上已无法求解，因此大量启发式方法被提出。嵌套蒙特卡洛搜索（NMCS）和嵌套回滚策略适应（NRPA）是针对单人游戏的蒙特卡洛搜索算法。然而，很少有工作评估蒙特卡洛搜索算法在组合图问题上的表现。本文展示了如何高效将蒙特卡洛搜索应用于图着色问题，并与现有方法进行对比。
原文摘要 · Abstract (English)
Graph Coloring is probably one of the most studied and famous problem in graph algorithms. Exact methods fail to solve instances with more than few hundred vertices, therefore, a large number of heuristics have been proposed. Nested Monte Carlo Search (NMCS) and Nested Rollout Policy Adaptation (NRPA) are Monte Carlo search algorithms for single player games. Surprisingly, few work has been dedicated to evaluating Monte Carlo search algorithms to combinatorial graph problems. In this paper we expose how to efficiently apply Monte Carlo search to Graph Coloring and compare this approach to existing ones.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。