我正在编写一个算法来匹配不同群体的学生.每个群体的斑点数量有限.每个学生提供他们的前5个小组选择.然后将学生按预定顺序分组(年龄较大的学生和完全出勤的学生优先考虑).不需要完全填充组,但是不能填充通过的容量.
我已经研究过类似的婚姻问题,例如Gale-Shapely稳定的婚姻算法,但我遇到的问题是群体远远少于学生,每个群体都可以接受多个学生.
实现这样一种算法的最佳方法是找到一个完全优化的解决方案,这样学生就没有更好的安排？在算法复杂性方面,我将大约600名学生分成10-20组.
我认为你将获得最小重量二分匹配而不是稳定婚姻(也称为匈牙利方法或算法或最大重量匹配,它可以通过否定权重给你最小重量匹配).
你出去与学生匹配职位.因此,二分图中的两个节点类型就是这些.
最简单的算法陈述需要一个完整的加权二分图,每组中的节点数相等.您可以将其视为方阵.权重是要素.行是学生.列是位置.
该算法将从每个行/列中挑选单个元素,使得总和最小化.
@nava的提议基本上是MWBM的贪婪版本,并不是最佳选择.真正的匈牙利算法将为您提供最佳答案.
要处理你的职位比学生少的事实很容易.对于“真实”的位置,根据需要添加尽可能多的“虚拟”位置.将所有这些连接到所有具有超高重量边缘的学生.算法将仅在匹配所有实际位置后选择它们.
诀窍是选择边权重.让我们调用学生将被考虑为第i名学生的职位O_i.然后让R_ip成为同一个学生在第p个位置的排名.最后,W_ip是连接第i个学生到第p个位置的边缘的权重.你会想要这样的东西：
W_ip = A * R_ip + B * O_i
您可以选择A和B来指定学生偏好的相对重要性以及他们排名的顺序.听起来秩序非常重要.因此,在这种情况下,你希望B足够大,完全覆盖学生的排名.
A = 1,B = N^2,where N is the number of students.
一旦你实现了一个实现,实际上很有趣的是调整参数以查看有多少学生获得了什么偏好等等.你可能想稍微调整一下参数以放弃一些订单.
当我正在研究这个问题时(90年代后期),我唯一能找到的开源MWBM是一个古老的FORTRAN库.它是O(N ^ 3).它在几秒钟内处理了1,000名学生(选择核心学术课程).我花了很多时间编写一个花哨的O(N ^ 2 log N)版本,结果证明N = 1000的速度大约慢了3倍.它只在约5,000开始“赢”.
这些天可能有更好的选择.
