algorithm - 最先进的图形着色元启发式

Question

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

谢谢。

Answer 1

在像Drools Planner这样的优化引擎中实现它并运行它的基准测试以确定哪种元启发式方法效果最好。

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

Answer 2

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