5

我正在编写一个算法来匹配不同群体的学生。每组名额有限。每个学生提供他们的前 5 组选择。然后将学生按预定顺序分组（年龄较大的学生和出勤率高的学生被优先考虑）。没有要求完全填充组，但不能填充通过容量。

我研究过类似的婚姻问题，例如 Gale-Shapely 稳定婚姻算法，但我遇到的问题是组比学生少得多，每个组可以接受多个学生。

实现这种算法以找到完全优化的解决方案的最佳方法是什么，使得学生分组没有更好的安排？在算法复杂度方面，我将大约 600 名学生分成 10-20 个小组。

4

4 回答 4

1

NB 接近的投票是非常错位的。解决模棱两可问题的算法选择和设计绝对是编程的一部分。

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

你出去与学生匹配职位。所以二分图中的两种节点类型是这些。

该算法的最简单语句需要一个完整的加权二分图，每个集合中的节点数相等。你可以把它想象成一个方阵。权重是元素。行是学生。列是位置。

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

@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 时才开始“获胜”。

这些天可能有更好的选择。

于 2016-02-19T14:45:02.843 回答
1

数学上最完美的

非常基于意见。

简单（几乎）总是获胜。这里

这是一个伪代码： 

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
于 2016-02-19T14:03:03.460 回答
1

我会修改背包问题（背包问题，维基百科）以使用 K 个组（背包）而不是一个组。您可以为他们的偏好分配“价值”，点数将是背包的最大“重量”。有了这个，您可以回溯以检查问题的最佳解决方案。

我不确定您需要解决问题的效率如何，但我认为这会奏效。

于 2016-02-19T13:52:17.833 回答
0

对于每个组：

  • 创建一个有序集合并添加所有学生（您必须设计启发式方法，它将对集合内的学生进行排序，如果该组在他们的选择范围内，则可以是出勤水平乘以 1，否则为 0）。

  • 将第 n 个学生填满小组

但是有些细节你没有解释。例如，如果有学生因为与其他优先级更高的学生一起填满而无法进入他们的 5 个选择中的任何一个，会发生什么情况？

于 2016-02-19T13:52:00.950 回答