algorithm - 将人们分成两队，并且不要分配互相讨厌的同一队

Question

有 n 个人，想将他们分到两个团队。 但有人互相讨厌，所以不想分配同一个团队。 我想最大限度地增加较小规模的团队成员数量。

例如有5个人， 1-2、2-3、3-1、4-5是互相讨厌的。 那么 {1,5}, {2,4} 赋值是可能的。

还有 5 个人和 1-2、1-3、1-4、1-5是互相讨厌的。 那么 {2,3}, {4,5} 赋值是可能的。

如何解决这个问题？

Answer 1

假设你想“使用”尽可能多的人，那么这个问题基本上就是最大二分子图的优化变体，即 NP-Hard .

最大二分子图问题:

Given a graph G=(V,E), find two sets U1,U2 <= V - such that:

1. for each v,u in U1, (v,u) is not in E (and similarly for U2)
2. U1 [intersection] U2 = {}
3. For all other sets U1,U2 that follow rules (1),(2), |U1|+|U2| >= |U1'| + |U2'|

在你的例子中，“人”是顶点，如果一个人不喜欢另一个人，两个人之间就有一条边。
很容易看出，一个问题的最优解也是另一个问题的最优解。

由于问题是 NP 完全问题，因此没有已知的有效最佳解决方案，但是确实存在一些近似算法，并且如果您的人数相当少，您可能可以使用蛮力(指数时间) )解决方案。