朋友选择算法

Question

在一个 .net 项目中，我们有一个由两种类型（假设为 x 和 y）的 200 人组成的群体，需要将他们分成每组 7 或 8 人。

我们有一个网页，在这个网页上，人们可以写下他们想要和哪些成员在一组。每个人都会建立一个想要加入的成员列表。

之后，应该有一个算法来构建 7-8 人小组，考虑到人们的评级和以下条件：每个小组至少有 2 个 x 类型和 2 个 y 类型的人。

我相信肯定有一个类似于这样的著名算法，但我没有找到。有人知道如何做吗？

- Eugene Marin

---

什么是度量标准？如果没有完美的解决方案，如何评估哪个解决方案比另一个更好？ - amit

每个人都会选择朋友，最好的情况是让尽可能多的人与他们选择的朋友在一起组成一个团体。当然，也要考虑到类型条件。 - Eugene Marin

那么，指标应该是每个用户u中的Sigma(#friends_in_group(u))？[仅适用于合法解决方案]？ - amit

我找不到很久以前看到的关于微软如何在距离非常遥远的场地为多名演讲者选择最佳演讲时间表的文章/视频。你可能需要研究通用算法来找到最佳解决方案。根据你的严格标准，你的样本似乎足够小，可以创建所有可能的解决方案，然后从中选择最佳选项。 - Bernhard Hofmann

Answer 1

这个问题看起来很 NP-Hard，所以我建议使用人工智能工具。

一种可能的方法是先使用 steepest ascent hill climbing [SAHC]。我们将按照问题评论中提到的方法定义我们的效用函数（让其为u）：每个用户所在小组中的好友总和。我们设定当解决方案非法时u(illegal)=-1。 接下来，我们定义我们的“世界”：所有可能解决方案的组合S is the group of all possible solutions。 对于S中的每个解决方案，我们定义：
next(s)={将一个人移到另一个组的所有可能性} 现在我们只需要使用随机重启的 SAHC 即可。

1. best<- -INFINITY 
2. while there is more time
3. choose a random legal solution
4. NEXT <- next(s)
5. if max{ U(NEXT) } < u(s): //s is the top of the hill
   5.1. if u(s) > best: best <- u(s) //if s is better then the previous result - store it.
   5.2. go to 2. //restart the hill climbing from a different random point.
6. else:
   6.1. s <- max{ NEXT } //climb on the steepest hill.
   6.2. goto 4.
7. return best //when out of time, return the best solution found so far.

这是一个“随时算法”，也就是说，你给它运行的时间越长，它得到的结果就越好，最终（在无限时间内）它将找到最优解。

- amit

---

当然，你可以使用任何不依赖于梯度的优化器，而不是SAHC（模拟退火、遗传算法等）。 - static_rtti