java - 匹配算法 (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 名学生(选择核心学术类(class))。我花了很多时间编写一个花哨的 O(N^2 log N) 版本，当 N=1000 时，它的速度慢了大约 3 倍。它只是在大约 5,000 点时才开始“获胜”。

现在可能有更好的选择。