基于偏好的分组算法

Question

我希望找到一种方法，通过偏好将人们分为不同的班级。

例如，有100名学生，每个学生都将被分配到五个班级中的一个：

科学 - 40个座位 数学 - 15个座位 历史 - 15个座位 计算机 - 20个座位 写作 - 10个座位

每个学生都有三个按顺序排列的首选班级。最佳方法是如何划分学生，以便尽可能多的人获得他们的第一和第二选择的课程，同时确保没有班级的人数超过房间容量。

我考虑采用以下方法：

1.将所有学生按照他们的第一选择班级分组。 2.查看哪些班级学生太多或太少。 3.检查已经报满的班级中是否有学生选择的第二班级还有空余位置。 4.移动这些学生到相应的班级。 5.重复步骤2-4，处理第三选择的班级。

虽然我认为这是一种合理的实现方式，但我想知道是否有其他更好的算法来解决这个问题。我已经搜索了很多地方，但我找不到任何可以解决这种问题的东西。

- user2338460

---

这类算法的一个“问题”是，通过选择受欢迎（且规模较小）的课程作为第二和第三选择来强制实现第一选择的安置是很容易“作弊”的。我对能够解决这个问题的解决方案非常感兴趣（尽管我目前没有想到方法）。 - Joost

请注意，这个问题被称为“医院/居民”、“学生-项目分配”或“大学招生”问题，它是更一般的“稳定婚姻问题”的变体。这里有一个优秀的资源，概述了许多大学级别的研究成果，并提供了截至2000年的几种解决方案的实现。 这正是NMRP今天使用的算法。 - Zediiiii

@Zediiiii：稳定婚姻和医院/居民问题与原始问题不同，因为它们需要组对学生进行排名（在某种意义上是不公平的）。有关解决方案，请参见https://cs.stackexchange.com/questions/93886/which-algorithm-can-calculate-an-optimal-allocation-of-students-to-projects。我在评论中提供了自己的实现。 - maiphi

Answer 1

根据您的描述，这听起来非常像稳定婚姻问题的变体之一。

查看维基链接，您将看到Gale-Shapley算法的描述，这是一个很好的解决方案。

- Roger Rowland

---

我喜欢这个。所以你可以说学生们向班级提出申请，如果班级已满，则接受申请。然后，由于其他人的原因而被踢出班级的学生必须向他们的下一个选择提出申请，直到所有大小都匹配？唯一的关键是如何排序它们？按字母顺序还是随机的？ - glh