我有一个图着色问题，涉及到数千个顶点，每个顶点有10到50条边。我一直在研究许多图着色启发式算法（GA，禁忌搜索...），但我发现很难比较它们并决定哪种最适合我。有没有人在大规模图着色方面有经验，可以推荐一种技术，或者告诉我该领域的最新算法？
谢谢。
最先进的图着色元启发式算法
3
- user1544745
2
简单的启发式算法不够用吗？ - John Dvorak
你也可以尝试更理论化的近似方法。 - amit
2个回答
1
将其实现在像Drools Planner这样的优化引擎中，并运行其benchmarker以确定哪种元启发式算法最有效。
特别是如果您没有一个纯图着色问题（因此您有额外的约束条件），那么事先无法确定哪种元启发式算法最有效。
- Geoffrey De Smet
0
我知道的一个好的解决方案是使用Kempe链的模拟退火。基本上，您使用标准的模拟退火算法，当您想对解决方案进行随机更改时，选择两个相邻节点，并根据Kempe链规则更改它们的颜色。
- twistedlogic
3
请问您能否添加有关“Kempe链”的更多细节？ - arunmoezhi
我从Coursera上Pascal van Hentenryck教授的离散优化课程中了解到了这项技术。 - twistedlogic
课程的新课程已经推出，我会推荐它。Kempe链的想法是：您想将一个节点的颜色更改为任意颜色，但您还想保持解决方案的可行性。例如，您想将节点n1的颜色从蓝色更改为红色。但是，您有两个相邻的节点n2和n3已经是红色的。想法是从蓝色->红色更改n1上的颜色，n2和n3更改为红色->蓝色，n2，n3相邻的红色节点更改为蓝色，以此类推。这样可以保持解决方案的可行性。 - twistedlogic
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接