如何对对象进行分组和合并，如果某些对象彼此不兼容？

Question

我有一堆对象，我想将它们合并成尽可能少的复合对象。

我可以计算任何两个对象是否可以合并，如果可以合并，则合并它们。

一个对象A与由N个合并对象组成的另一个B不兼容当且仅当A与B的一个或多个元素不相容。

贪婪的解决方案(合并为工作的第一步)对4个对象失败，其中1x4 (1不能与4)、2x3、3x4分组。贪婪的解决方案将对象1和2放入第1组，然后将对象3放入第2组，将对象4放入第3组。正确的解决方案是将对象1和3放入第1组，将对象2和4放入第2组。

这个问题的名称是什么，它可以解决吗？如果是的话，算法是什么？

(最坏的情况=蛮力，这是缓慢但可行的，因为我合并的对象数量非常少。)

编辑:合并失败，如果不能合并，否则合并。未合并和合并都是可访问的。需要O( size (a) + size(b))时间，并返回大小对象(a+b)。假设尺寸在1000左右。

Answer 1

把这看作是一个图问题。每个对象都是一个顶点，并且有一个边(v1, v2)当且仅当v1和v2是兼容的。您现在正在寻找一个团盖，它是NP-完全的。

请注意，团覆盖是一个决策问题(是否可以用k团覆盖该图？)，但您可以通过对k进行二进制搜索(例如，8个团)将其转化为优化问题？如果是，尝试4，如果不是，尝试16，等等)。这个问题仍然是NP-完全的。

正如@timrau已经评论过的--就像维基百科链接中提到的--补语问题是图着色：您有相同的顶点，但现在只有当v1和v2不兼容时，才有一个边缘(v1, v2)。然后，您希望找到为顶点着色所需的最小颜色数，这样相邻的顶点就没有相同的颜色。维基百科还为此提供了许多算法。