图着色问题的算法研究综述

来源：计算机工程与应用杂志2024年第18期北京时间：

作者：宋家欢, 王晓峰, 胡思敏, 贾璟伟, 颜冬

单位：1.北方民族大学 计算机科学与工程学院，银川 750021；2.北方民族大学 图形图像智能处理国家民委重点实验室，银川 750021

摘要：图着色问题（graph coloring problem，GCP）是一个经典的组合优化问题，已广泛应用于数学、计算机科学和生物科学等多个领域。由于图着色问题的NP难特性，目前还没有多项式时间内的精确算法求解该问题，为了给出求解该问题的高效算法，需要对现有算法进行梳理。主要分为智能优化算法、启发式算法、强化学习算法等，从算法原理、改进思路、性能和精度等方面进行对比分析，归纳出算法的优缺点，并指出GCP的研究方向和算法设计路径，对于相关问题的研究有指导意义。

关键词：图着色问题,智能优化算法,启发式算法,强化学习算法