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

Algorithmic Research Overview on Graph Coloring Problems

作　　者：宋家欢 王晓峰[1,2] 胡思敏 贾璟伟 颜冬 SONG Jiahuan;WANG Xiaofeng;HU Simin;JIA Jingwei;YAN Dong(School of Computer Science and Engineering,North Minzu University,Yinchuan 750021,China;Laboratory of Image&Graphics Intelligent Processing of State Ethnic Affairs Commission,North Minzu University,Yinchuan 750021,China)

机构地区：[1]北方民族大学计算机科学与工程学院,银川750021 [2]北方民族大学图形图像智能处理国家民委重点实验室,银川750021

出　　处：《计算机工程与应用》2024年第18期66-77,共12页Computer Engineering and Applications

基　　金：国家自然科学基金(62062001);宁夏青年拔尖人才项目(2021)。

摘　　要：图着色问题(graph coloring problem,GCP)是一个经典的组合优化问题,已广泛应用于数学、计算机科学和生物科学等多个领域。由于图着色问题的NP难特性,目前还没有多项式时间内的精确算法求解该问题,为了给出求解该问题的高效算法,需要对现有算法进行梳理。主要分为智能优化算法、启发式算法、强化学习算法等,从算法原理、改进思路、性能和精度等方面进行对比分析,归纳出算法的优缺点,并指出GCP的研究方向和算法设计路径,对于相关问题的研究有指导意义。The graph coloring problem(GCP)is a classic combinatorial optimization problem that has been widely applied in various fields such as mathematics,computer science,and biological science.Due to the NP hard nature of graph coloring problems,there is currently no precise algorithm in polynomial time to solve the problem.In order to provide an efficient algorithm for solving this problem,it is necessary to review the existing algorithms.It mainly divided into intelligent optimization algorithms,heuristic algorithms,reinforcement learning algorithms,etc.,comparative analysis is carried out from the aspects of algorithm principles,improvement ideas,performance and accuracy,summarizing the advantages and disadvantages of algorithms,and pointing out the research direction and algorithm design path of GCP,which has guiding significance for the research of related problems.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]