A Diversity Algorithm of Nested Rollout Policy Adaptation for Graph Coloring.

The Graph Coloring Problem is a well-known NP-hard problem. Over the years, numerous scholars have been pursuing efficient algorithms to obtain high-quality solutions. Nested Rollout Policy Adaptation (NRPA) is a Monte Carlo Tree Search algorithm for single-player games, and it has been proven effective and good in combinatorial optimization problems. In this paper, we use for the first time the NRPA algorithm combined with the destruction and reconstruction ideas of the Iterative Greedy algorithm to solve the Graph Coloring Problem. First, the basic principle of the NRPA algorithm is introduced. Then, NRPA is extended by using mixed sorting, destruction and reconstruction, and the Diversity-NRPA algorithm is proposed, which improves the diversity of the algorithm. Finally, Diversity-NRPA is applied to solve the Graph Coloring Problem by combining it with the knowledge of the graph theory field. We evaluate the performance of Diversity-NRPA on DIMACS, a well-known graph benchmark instance, and compare it with traditional graph coloring algorithms. The experimental results show that the Diversity-NRPA algorithm can achieve excellent performance in both solution quality and search efficiency in solving the Graph Coloring problem. [ABSTRACT FROM AUTHOR]