匹配算法(Java)

Question

我正在编写一个算法来匹配不同群体的学生.每个群体的斑点数量有限.每个学生提供他们的前5个小组选择.然后将学生按预定顺序分组(年龄较大的学生和完全出勤的学生优先考虑).不需要完全填充组,但是不能填充通过的容量.

我已经研究过类似的婚姻问题,例如Gale-Shapely稳定的婚姻算法,但我遇到的问题是群体远远少于学生,每个群体都可以接受多个学生.

实现这样一种算法的最佳方法是找到一个完全优化的解决方案,这样学生就没有更好的安排？在算法复杂性方面,我将大约600名学生分成10-20组.

Answer 1

注意：势均力敌的投票结果是非常错误的。解决模糊问题的算法选择和设计绝对是编程的一部分。

我认为最小权重二分匹配比稳定婚姻（也称为匈牙利方法或算法或最大权重匹配，它可以通过否定权重为您提供最小权重匹配）走得更远。

您要与学生进行职位匹配。所以二部图中的两个节点类型就是这些。

该算法最简单的表述需要一个完整的加权二分图，每组中的节点数相等。您可以将其视为方阵。权重是元素。这两排都是学生。列是位置。

该算法将从每行/列中选取一个元素，以使总和最小化。

@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 倍。5000左右才开始“赢”。

如今可能有更好的选择。