加权 n 着色问题算法

Question

我有 100 个顶点和一个函数 f(x,y)，用于计算顶点 x 和顶点 y 之间的边的权重。f 并不是特别昂贵，因此如果需要，我可以生成带有权重的索引邻接表。

有哪些有效、易于处理的方法可以通过最小化或最大化连接相同颜色顶点的所有边的权重总和来优化这些顶点的 n 着色？

我想模拟退火在这种情况下可能会很有用。

代码包的链接也非常有用，所以我不必重写轮子！

谢谢！

Answer 1

NetworkX是一个非常方便的用于实验图形的 python 包。如果您更喜欢 C++，还有 boost，但是在 NetworkX 之后，在 boost 中使用图形会显得异常笨拙。

模拟退火并不是一个坏主意。您可以先进行常规着色以找到下限，这将有助于指导您的搜索。不过，您应该更准确地定义您的问题。您的意思是为传入边缘的总和选择一些枢轴值并尝试围绕枢轴划分颜色吗？