计算机工程与应用 ›› 2024, Vol. 60 ›› Issue (18): 66-77.DOI: 10.3778/j.issn.1002-8331.2403-0434

• 热点与综述 • 上一篇    下一篇

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

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

  1. 1.北方民族大学 计算机科学与工程学院,银川 750021
    2.北方民族大学 图形图像智能处理国家民委重点实验室,银川 750021
  • 出版日期:2024-09-15 发布日期:2024-09-13

Algorithmic Research Overview on Graph Coloring Problems

SONG Jiahuan, WANG Xiaofeng, HU Simin, JIA Jingwei, YAN Dong   

  1. 1.School of Computer Science and Engineering, North Minzu University, Yinchuan 750021, China
    2.Laboratory of Image & Graphics Intelligent Processing of State Ethnic Affairs Commission, North Minzu University, Yinchuan 750021, China
  • Online:2024-09-15 Published:2024-09-13

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

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

Abstract: 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.

Key words: graph coloring problem, intelligent optimization algorithm, heuristic algorithm, reinforcement learning algorithm