根据偏好分组

Question

我试图带一组20个人（标记为1 - 20），并将它们分成五个子组，每个子组基于这些人希望与之相关的表达偏好。

20人组中的每个人可以表示0,1,2,3或4个偏好。例如，person1可以选择0（与他们无关），或14（与person14组在一个组中），或者可以表示与14,20,6和7中的人在一个组中。理想情况下，每个具有偏好将在至少有一个选择的组中。

关于算法的想法？

Answer 1

您遇到的问题与C＃没有真正相关，该算法与语言无关。

这个问题的经典实现是backtracking。

更多信息：

• Constraint satisfaction problems on Wikipedia
• 推荐：Chapter 5 from Artificial Intelligence - A Modern Approach 2nd edition

另一种方法（我会去为这个）：Genetic Algorithms。

Answer 2

这可能是一个太多的要求在SO，但认为这个问题很有趣，所以这里有一些想法。

由于维克多Hurdugaci说，这主要是独立于语言的算法问题（虽然我很乐意看到下面LINQ实现我的例子！）

在你的问题不能得到所描述的问题完美的结果，即它是一个优化问题（所以你不能用约束满足算法来解决它）。您必须找到一种算法，该算法根据指示结果有多好的某个函数（称为适应函数）从所有可能结果集中找到最佳结果。

天真蛮力解决方案（伪代码）

我们先从一组人（这里：4把事情简单化）：

people = { a, b, c, d } 

我们可以找到的所有可能的亚组固定大小（此处：2）使用choose操作：

groups = people.choose(2) // = { {a,b} {a,c} {a,d} {b,c} {b,d} {c,d} } 

我们可以发现USI亚组的所有可能的组合再次纳克choose操作：

combi = groups.choose(4/2) // = { {ab,ac} {ab,ad} {ab,bc} {ab,bd} 
          //  {ab,cd} {ac,ad} {ac,bc} {ac,bd} 
          //  {ac,cd} {ad,bc} {ad,bd} {ad,cd} 
          //  {bc,bd} {bc,cd} {bd,cd} } 

显然，人不能在同一时间两个组，所以我们删除所有无效组合：

combi2 = combi.select(g => g.bigUnion().size == 4) 
          // = { {ab,cd}, {ac,bd}, {ad,bc} } 

现在你必须要找到基于“最佳”项目在一些健身功能上，即考虑到偏好而得分最高的组合。

result = combi2.maximumBy(g => fitness(g)) 

例如，如果a有b，和b，c和d偏好没有任何偏好，然后calculateScore应该返回一个更高的分数为{ab,cd}比{ac,bd}和{ad,bc}。

改进方案

有一个数的算法，用这种优化问题的解决。我认为一个Hill climbing算法很适合这里。