asp.net - 好友选择算法

Question

在一个 .net 项目中，我们有一组 200 人，分为两种类型，比如说 x 和 y，他们需要分成 7 人或 8 人一组.

我们有一个网页，人们可以在上面写下他们想加入的其他成员。每个人都建立一个想要的成员列表。

在此之后，应该有一个算法来构建 7-8 成员组，考虑到人们的评分，以及以下条件:每个组至少有 2 人的每种类型( x/y).

我很确定一定有一个众所周知的算法与此类似，但没有找到。有人知道怎么做吗？

Answer 1

这个问题有味道NP-Hard ，所以我建议使用人工智能工具。

一种可能的方法是 steepest ascent hill climbing [SAHC]首先，我们将定义我们的效用函数(让它成为 u)，如问题的评论中所述。 [每个用户在群组中的好友总数]。让我们为非法解决方案定义 u(illegal) = -1。
接下来，我们定义我们的“世界”:S 是所有可能解决方案的集合]。
对于 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.

是anytime algorithm ，这意味着当你给它更多的运行时间时它会得到更好的结果，最终 [在时间无穷大] 它会找到最佳结果。