基于偏好的分组算法

Question

我希望找到一种方法来按优先顺序将人们分类.

例如,假设有100名学生将分别分配五个班级中的一个:

• 科学 - 40个席位
• 数学 - 15个席位
• 历史 - 15个席位
• 电脑 - 20个座位
• 写作 - 10个席位

每个学生都有三个首选课程,按优先顺序排列.什么是最好的方法来分开学生,以便尽可能多的人获得他们的第一和第二选择课程,同时确保没有班级有太多的学生为房间.

我想过通过以下方法接近它:

1. 将所有学生按其首选课程分组
2. 看哪些班级的学生太多,哪些班级太少
3. 检查超额预订课程中的学生是否有第二选择课程,这些课程预订不足
4. 相应地移动这些学生
5. 用第三选择类重复2-4

虽然我觉得这是一个合理的实现,但我想知道是否有其他算法以更好的方式解决这个问题.我尝试过全面搜索,但我找不到任何可以解决这类问题的东西.

Answer 1

从你的描述来看，这听起来很像稳定婚姻问题的一种变体

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