计算机应用研究

作者：宋家欢,王晓峰,胡思敏,姚佳兴,锁小娜,

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

关键词：图着色问题,强化学习策略,梯度下降,组合优化问题,

基金：国家自然科学基金资助项目(62062001)；宁夏青年拔尖人才资助项目(2021)；宁夏自然科学基金项目(2024AAC03165)；；

图着色问题（graph coloring problem，GCP）是经典的组合优化问题，其目标是为图的每个顶点分配不同的颜色，使得相邻顶点的颜色不同，同时尽可能减少所用颜色的数量。GCP属于NP难问题，传统求解方法（如贪心算法、启发式搜索和进化算法）往往因计算复杂度高而受限，且易陷入局部最优解。为了解决这些问题，提出了一种基于强化学习策略（reinforcement learning strategy，RLS）的梯度下降学习方法来求解GCP。具体而言，将GCP转换为强化学习中的策略优化问题，通过设计策略梯度算法，将图的着色状态映射为强化学习的状态，将颜色分配视为动作，以目标函数的负值作为奖励信号，逐步优化着色策略。实验结果表明，所提方法在不同类型和规模的图实例上均优于传统启发式算法，尤其在高维度和复杂约束条件下表现出较强的全局探索能力和收敛性。该研究表明，基于强化学习的图着色方法为在解决复杂组合优化问题上具有广泛的应用潜力，为图着色及其衍生问题提供了有效的求解新路径。

来源：2025年第4期

《计算机应用研究》期刊编辑部

查看计算机应用研究杂志2025年第4期