algorithm - 将人员分成团队以获得最大的满意度

Question

只是一个好奇的问题。还记得在课堂小组作业中，教授会将人们分成一定数量的小组（n）吗？

我的一些教授会从每个学生那里拿出n一份想共事和n不想共事的人的名单，然后神奇地将n学生与他们喜欢并避免与之共事的人配对他们不喜欢的人。

对我来说，这个算法听起来很像一个背包问题，但我想我会问你解决这类问题的方法是什么。

编辑：找到一篇 ACM 文章，描述的内容与我的问题完全一样。阅读第二段的似曾相识。

Answer 1

对我来说，这听起来更像是某种集团问题。

我看到问题的方式，我设置了下图：

• 顶点将是学生
• 如果以下两种情况都成立，则两个学生将被一条边连接起来：
  1. 两个学生中至少有一个想和另一个一起工作。
  2. 这两个学生中没有一个不想和另一个一起工作。

然后就是将图划分为大小为 n 的团。（假设学生人数能被 n 整除）

如果这是不可能的，我可能会让对边缘的第一个约束滑倒，并在两个人之间有边缘，只要他们都没有明确表示他们不想与另一个人一起工作。

至于有效解决此问题的方法，我不知道，但这有望让您更深入地了解问题。

Answer 2

你可以很容易地将其建模为一个聚类问题，你甚至不需要定义一个空间，你实际上可以只定义距离：

如果他们都想一起工作，让两个人非常接近。如果其中一个想要与另一个合作，请关闭。如果只是冷漠，中等距离。如果其中一方不想与另一方合作，则相距甚远。

然后你可以找到集群，是的。然后拆分任何规模过大的集群，并确信集群中的人都能很好地一起工作。

Answer 3

这个问题可以是暴力破解的，因此我的方法是首先暴力破解它，然后在我有更好的想法时修复它。

Answer 4

您可以使用几种算法。一个很好的例子就是所谓的“稳定婚姻问题”，它有一个完美的解决方案。你可以在这里读更多关于它的内容：

http://en.wikipedia.org/wiki/Stable_marriage_problem

稳定的婚姻问题只适用于两组人（婚姻案例中的男性/女性）。如果你想结对，你可以使用一个变体，稳定室友问题。在这种情况下，您创建对，但每个人都来自一个池。

但是您要求一个团队（我将其翻译为每个团队> 2人）。在这种情况下，您可以让每个人填写他们最好到最差的匹配，然后运行