最先进的图形着色元启发法

Question

我有一个图形着色问题，涉及数千个顶点，每个顶点有 10 到 50 条边。我一直在研究许多图形着色启发法（GA、禁忌搜索......），但我发现它们很难比较并决定哪一个最适合我。有没有人有大规模图形着色方面的经验来推荐一种技术或告诉我该领域当前最先进的算法？

谢谢。

Answer 1

在像Drools Planner这样的优化引擎中实现它，并运行它的benchmarker来找出哪种元启发法最有效。

特别是如果您没有纯图形着色问题（因此您有额外的约束），则不可能提前判断哪种元启发式最有效。

Answer 2

据我所知，一个好的解决方案是使用带有 Kempe 链的模拟退火。基本上，您使用标准模拟退火，当您想要对解决方案进行随机更改时，您选择两个相邻节点并根据肯佩链规则更改它们的颜色。

Answer 3

我的 2021 年书中讨论了其中许多问题（以及潜在的解决方案）

Lewis, R. (2021) 图形着色指南：算法和应用（第二版）。施普林格。国际标准书号：978-3-030-81053-5。

这伴随着一套 C++ 算法。我还编写了一个用于图形着色的 Python 库，其中包括用于处理非常大的图形的启发式方法。