好友选择算法
好友选择算法
提问于 2011-08-22 22:23:06
在.net项目中，我们有一个由两种类型的200人组成的小组，比如x和y，他们需要被分成7人或8人一组。
我们有一个网页，人们在那里写下他们想要加入的其他成员。每个人都会建立一个想要的成员列表。
在此之后，应该有一个考虑人民评分和以下条件的算法来构建7-8成员组:每个组至少有两个每种类型的人(x/y)。
我很确定一定有类似于此的著名算法，但没有找到。有人知道怎么做吗？
回答 1
Stack Overflow用户
回答已采纳
发布于 2011-08-22 22:41:44
这个问题有NP-Hard的味道，所以我建议使用人工智能工具。
一种可能的方法是steepest ascent hill climbing SAHC首先，我们将定义我们的效用函数(假设它是u)，如问题的注释中所提到的。每个用户在群组中的好友总数。让我们为非法解决方案定义u(illegal) = -1。
接下来，我们定义我们的“世界”：S is the group of all possible solutions]。
对于S中的每个解决方案，我们定义：
next(s)={all possibilities moving one person to a different group}
我们现在要做的就是随机重启运行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，这意味着当你给它更多的运行时间时，它会得到更好的结果，最终在无限的时间它会找到最优的结果。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/7148928
复制相关文章
相似问题
腾讯云开发者
