c# - 按偏好拆分组

Question

我正在尝试将一组 20 人（标记为1 - 20）分成 5 个子组，每组 4 人，具体取决于这些人希望与谁在一起的偏好。

20 人小组中的每个人都可以表达 0、1、2、3 或 4 种偏好。例如，person1可以选择 0（不喜欢与谁在一起）或 14（在person14与在一个至少有一个选择的群体中。

关于算法的想法？

Answer 1

您遇到的问题与 C# 无关，算法与语言无关。

这个问题的经典实现是回溯。

更多信息：

• 维基百科上的约束满足问题
• 推荐：人工智能第 5 章 - 现代方法第 2 版

另一种方法（我会这样做）：遗传算法。

Answer 2

这可能在 SO 上问得太多了，但认为这个问题很有趣，所以这里有一些想法。

正如Victor 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} }

我们可以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}。

改进的解决方案

有几种算法可以处理这种优化问题。我认为爬山算法很适合这里。