摘要
图着色问题(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.
作者
宋家欢
王晓峰
胡思敏
贾璟伟
颜冬
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)
出处
《计算机工程与应用》
CSCD
北大核心
2024年第18期66-77,共12页
Computer Engineering and Applications
基金
国家自然科学基金(62062001)
宁夏青年拔尖人才项目(2021)。
关键词
图着色问题
智能优化算法
启发式算法
强化学习算法
graph coloring problem
intelligent optimization algorithm
heuristic algorithm
reinforcement learning algorithm
