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

Question

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

我可以计算任意2个对象是否可以合并，如果可以合并，就合并它们。

当且仅当 A 与 B 的一个或多个元素不兼容时，对象 A 与由 N 个合并对象组成的另一个 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兼容。您现在正在寻找 clique cover , 这是 NP 完全的。

请注意，团覆盖是一个决策问题(是否可以用 k 团覆盖图形？)，但您可以通过对 k 进行二分搜索将其转化为优化问题(我可以覆盖 8 个派系吗？如果是，尝试 4 个，如果否，尝试 16 个，等等)。那么问题仍然是 NP 完全问题。

---

正如@timrau 已经评论过的——以及维基百科链接中提到的——补码问题是 graph coloring : 你有相同的顶点，但现在有一条边 (v1, v2)当且仅当 v1和 v2 不兼容。然后，您想要找到为顶点着色所需的最少颜色数，以便没有相邻顶点具有相同的颜色。维基百科还提供了一些 algorithms为此。