匹配算法 (Java)
Matching Algorithm (Java)
我正在编写一个算法来匹配不同组的学生。每组名额有限。每个学生提供他们的前 5 个小组选择。然后将学生按预定顺序分组（年龄较大的学生和出勤率高的学生优先）。不要求组满，但不能满满。
我研究过类似的婚姻问题，例如 Gale-Shapely 稳定婚姻算法，但我遇到的问题是组数远远少于学生，每个组可以接受多个学生。
实现这种算法以找到完全优化的解决方案的最佳方法是什么，这样就没有更好的学生分组安排？就算法复杂度而言，我将大约 600 名学生分成 10-20 个小组。
每组：
创建一个有序集合并添加所有学生（您必须设计启发式算法，将学生排列在集合内，如果该组在他们的选择范围内，则可以是出勤率乘以 1， 0 否则）。
用前 n 名学生填满小组
但是有些细节你没有解释。例如，如果有学生因为与其他优先级更高的学生填满而无法输入他们的 5 个选项中的任何一个，会发生什么情况？
我会修改背包问题 (Knapsack problem, wikipedia) 以处理 K 个组（背包）而不是一个。您可以将 "value" 分配给他们的偏好，并且点数将是背包的最大值 "weight"。有了这个，您可以回溯以检查什么是问题的最佳解决方案。
我不确定您需要这个问题的效率如何，但我认为这会奏效。
the most mathematically perfect
非常基于意见。
简单（几乎）总是赢。 here
这是一个伪代码：
students <-- sorted by attendance
for i=0 to n in students:
groups <-- sorted by ith student's preference
for j=0 to m in groups:
if group j has space then add student i to group j; studentAssigned=true; break;
if studentAssigned=false;
add i to unallocated
for i=0 to k in unallocated
allocate i to a random group that is not filled
NB 非常接近的选票错位了。解决一个模糊问题的算法选择和设计绝对是编程的一部分。
我认为使用最小权重二分匹配比稳定婚姻（也称为匈牙利方法或算法或最大权重匹配，它可以通过取负权重来为您提供最小权重匹配）走得更远。
您正在与学生匹配职位。所以二分图中的两种节点类型就是这些。
最简单的算法语句需要一个完整的加权二分图，每个集合中的节点数相等。您可以将其视为方阵。权重是元素。排的是学生。列是位置。
算法将从每个 row/column 中选择一个元素，以使总和最小化。
@nava 的提议基本上是 MWBM 的贪婪版本，并不是最优的。真正的匈牙利算法会给你一个最优的答案。
处理您的职位比学生少的事实很容易。根据需要向 "real" 个位置添加尽可能多的 "dummy" 个位置。将所有这些连接到所有具有超高权重边缘的学生。算法只会在所有真实位置匹配后才选择它们。
诀窍是选择边缘权重。让我们称第 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 倍。刚开始 "winning" 大约 5,000。
现在可能有更好的选择。
我正在编写一个算法来匹配不同组的学生。每组名额有限。每个学生提供他们的前 5 个小组选择。然后将学生按预定顺序分组（年龄较大的学生和出勤率高的学生优先）。不要求组满，但不能满满。
我研究过类似的婚姻问题，例如 Gale-Shapely 稳定婚姻算法，但我遇到的问题是组数远远少于学生，每个组可以接受多个学生。
实现这种算法以找到完全优化的解决方案的最佳方法是什么，这样就没有更好的学生分组安排？就算法复杂度而言，我将大约 600 名学生分成 10-20 个小组。
每组：
创建一个有序集合并添加所有学生（您必须设计启发式算法，将学生排列在集合内，如果该组在他们的选择范围内，则可以是出勤率乘以 1， 0 否则）。
用前 n 名学生填满小组
但是有些细节你没有解释。例如，如果有学生因为与其他优先级更高的学生填满而无法输入他们的 5 个选项中的任何一个，会发生什么情况？
我会修改背包问题 (Knapsack problem, wikipedia) 以处理 K 个组（背包）而不是一个。您可以将 "value" 分配给他们的偏好，并且点数将是背包的最大值 "weight"。有了这个，您可以回溯以检查什么是问题的最佳解决方案。
我不确定您需要这个问题的效率如何，但我认为这会奏效。
the most mathematically perfect
非常基于意见。
简单（几乎）总是赢。 here
这是一个伪代码：
students <-- sorted by attendance
for i=0 to n in students:
groups <-- sorted by ith student's preference
for j=0 to m in groups:
if group j has space then add student i to group j; studentAssigned=true; break;
if studentAssigned=false;
add i to unallocated
for i=0 to k in unallocated
allocate i to a random group that is not filled
NB 非常接近的选票错位了。解决一个模糊问题的算法选择和设计绝对是编程的一部分。
我认为使用最小权重二分匹配比稳定婚姻（也称为匈牙利方法或算法或最大权重匹配，它可以通过取负权重来为您提供最小权重匹配）走得更远。
您正在与学生匹配职位。所以二分图中的两种节点类型就是这些。
最简单的算法语句需要一个完整的加权二分图，每个集合中的节点数相等。您可以将其视为方阵。权重是元素。排的是学生。列是位置。
算法将从每个 row/column 中选择一个元素，以使总和最小化。
@nava 的提议基本上是 MWBM 的贪婪版本，并不是最优的。真正的匈牙利算法会给你一个最优的答案。
处理您的职位比学生少的事实很容易。根据需要向 "real" 个位置添加尽可能多的 "dummy" 个位置。将所有这些连接到所有具有超高权重边缘的学生。算法只会在所有真实位置匹配后才选择它们。
诀窍是选择边缘权重。让我们称第 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 倍。刚开始 "winning" 大约 5,000。
现在可能有更好的选择。