如果某些对象彼此不兼容，如何分组和合并对象？
How to group and merge objects, if some are incompatible with each other?
我有一堆对象，我想将它们合并成尽可能少的复合对象。
我可以计算任意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)) 时间和 returns 一个大小为 (a+b) 的对象。假设大小在 1000 左右。
将此视为图形问题。每个对象都是一个顶点，当且仅当 v1 和 v2 兼容时，才会有一条边 (v1, v2)。您现在正在寻找 clique cover，它是 NP 完全的。
注意 clique cover 是一个决策问题（是否可以用 k cliques 覆盖图形？），但你可以通过对 [=13 进行二进制搜索将其转化为优化问题=]（我可以覆盖 8 个派系吗？如果是，请尝试 4 个，如果否，请尝试 16 个，等等）。那么问题仍然是NP完全的。
正如@timrau 已经评论过的那样 - 正如维基百科中提到的 link - 补充问题是 graph coloring: you have the same vertices, but now there is an edge (v1, v2) if and only if v1 and v2 are incompatible. You then want to find the minimum number of colors needed to color your vertices, such that no adjacent vertices have the same color. Wikipedia also provides a number of algorithms。
我有一堆对象，我想将它们合并成尽可能少的复合对象。
我可以计算任意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)) 时间和 returns 一个大小为 (a+b) 的对象。假设大小在 1000 左右。
将此视为图形问题。每个对象都是一个顶点，当且仅当 v1 和 v2 兼容时，才会有一条边 (v1, v2)。您现在正在寻找 clique cover，它是 NP 完全的。
注意 clique cover 是一个决策问题（是否可以用 k cliques 覆盖图形？），但你可以通过对 [=13 进行二进制搜索将其转化为优化问题=]（我可以覆盖 8 个派系吗？如果是，请尝试 4 个，如果否，请尝试 16 个，等等）。那么问题仍然是NP完全的。
正如@timrau 已经评论过的那样 - 正如维基百科中提到的 link - 补充问题是 graph coloring: you have the same vertices, but now there is an edge (v1, v2) if and only if v1 and v2 are incompatible. You then want to find the minimum number of colors needed to color your vertices, such that no adjacent vertices have the same color. Wikipedia also provides a number of algorithms。