将人分成团队以获得最大的满足感。

Question

将人分成团队以获得最大的满足感。

algorithmknapsack-problemsatisfiability

11

一个好奇的问题。还记得那些在课堂小组作业时，教授会将人们分成固定数量(n)的小组吗？

我的一些教授会从每个学生那里获取一个希望合作的n人名单和一个不想与之合作的n人名单，然后神奇地组成n人的小组，让学生与他们喜欢的人匹配，并避免与他们不喜欢的人一起工作。

对我来说，这个算法听起来很像一个背包问题，但我想问一下你们在处理这种问题时采用的方法是什么。

编辑: 找到了一篇ACM文章，描述了与我问题完全相同的内容。请阅读第二段以获取似曾相识的感觉。

- Jon W

1

听起来不错；我的教授总是让我和班上最懒惰的人一起工作，结果我总是要做太多的工作。;-) - James McNellis

@james 有时候这是学习的最佳方式。 ;) - Jon W

7

@Jweede: 这可能是学习的好方法，让你意识到(1)人们可能会利用你，以及(2)你的上司不会认可你的努力工作。 - o0'.

你对 n 的使用相当普遍。每个学生都必须喜欢和讨厌同样数量的人吗？ - IVlad

@IVlad 确实。理想情况下，一个人会选择3个他们喜欢的人和3个他们不喜欢的人。然而在实践中，“n”只是一个最大值。 - Jon W

@Lo'oris：不幸的是，我的大学没有明确提供那门课程。但我认为这是我们以某种方式都要学习的东西。 - Jon W

4个回答

3

您可以将这个问题轻松地建模为聚类问题，甚至无需定义空间，您实际上只需要定义距离即可：如果两个人都想一起工作，那么他们就很亲近；如果其中一个人想和另一个人一起工作，那么他们就很亲近；如果双方都不感兴趣，那么就是中等距离；如果任何一方不想与另一方合作，那么就是远距离。然后，您可以轻松地找到聚类群集。接着，分割掉过大的聚类，有信心这些聚类中的人员都能够愉快地一起工作。

- JSchlather

1

这个想法很有趣。在抽象空间中使用距离，使我们不必尝试绘制点（这将需要首先解决问题）。由于对群集进行分区大约需要O（大小）的时间，我认为我们可以相当有效地解决问题。但需要调整距离，以考虑对称性（你应该更愿意与喜欢你的人一起工作，而不是与你喜欢但不关心你的人一起工作）。如果我们估计爱恨等同于中等-中等，则需要5个距离而不是3个。 - Matthieu M.

1

这个问题可以通过暴力破解来解决，因此我的方法是先进行暴力破解，然后在我有更好的想法时再进行修复。

- o0'.

嗯，好的，我们知道如何暴力破解它。那怎么能算是一个答案呢？ - WhirlWind

1

我认为 Knuth 会同意你的观点。 - Jon W

2

@WhirlWind：他并没有特别问我们会使用什么算法，他问的是“你们解决这类问题的方法是什么”。而这就是我的方法。 - o0'.

2

这个问题可以使用暴力破解法，耶，这意味着它肯定是可计算的。 - JSchlather

0

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

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

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

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

- Roy van Rijn

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Sebastian Paaske Tørholm · Accepted Answer

对我来说，这更像是某种团伙问题。

我认为问题的解决方式如下，我会建立以下图形：

- 顶点将是学生。 - 如果两个学生都满足以下两个条件，则它们之间将连接一条边：

1. 至少有一个学生想要与另一个学生一起工作。 2. 两个学生中没有一个不想与另一个学生一起工作。

- 然后，将图形划分为大小为n的团体。（假设学生人数可被n整除）

如果无法实现这一点，我可能会让边缘上的第一个约束条件失效，并且只要两个人中没有人明确表示不想与另一个人一起工作，它们之间就会有边缘。

至于有效地解决这个问题的方法，我不知道，但这应该可以让您更接近问题的洞察力。