0

我正在尝试使用匈牙利算法根据学生的喜好将学生分类。

在我的数据集中，大约有 550 名学生，每个学生都有一个排名前 5 的偏好列表。每个首选项都是一个对应于一个类的 ID。每个班级都有最小和最大容量（在我的例子中，最小上限为 15 人，最大上限为 27 人），数据集中有 21 个班级。

这是每个学生的示例数据集：

电子邮件 第一选择 第二选择 第三选择 第四选择 合适的选择
电子邮件@gmail.com 4 7 1 8 21
email2@gmail.com 6 9 14 17 2

这是每个类的示例数据集：

班级名称 班级号 最小帽 最大上限
班级标题1 1 15 27
类标题2 2 15 27
班级标题3 3 15 27

我需要将学生分类到他们喜欢的班级，同时还要遵循最小容量和最大容量。为此，我打算使用匈牙利算法。

因为有大约 550 名学生和 21 个班级，并且为了让匈牙利算法起作用，我打算制作这些班级的“副本”。我会首先为每个班级（如班级 1.1、1.2、1.3、1.4、2.1、2.2、2.3 等）制作 15 个副本，以满足班级的最低要求，然后将更多副本添加到其中最受欢迎的班级直到有相同数量的学生和班级副本。

然后，根据学生的副本和偏好，我正在考虑制作一本字典并使用该算法的实现。

我有几个问题：

  1. 这个计划是一个好的计划还是有更好的解决方案来解决我遇到的问题？
  2. 如何制作所有链接回原始 ID 的类的副本？
  3. 在将其实现到算法中时，我应该将学生的偏好放入字典中（如 GitHub 链接所示），但如果现在有 1.1 之类的 ID，人们的选择是 1，并且没有像这样的实际类算法，我应该如何解决？

提前谢谢您，如果您需要任何澄清，请告诉我

4

2 回答 2

0

  1. 我认为这应该可行，尽管我会做一个改变。不要从每个类的最小副本开始，而是从最大值开始。有 550 名学生和 21 个班级，所有班级都将几乎满员。您不必担心最低限度。

  2. 就像你说的那样会起作用。1 类变为 1.1、1.2 和 1.3，您可以轻松地将其反转。

  3. 由于您要“复制”类，因此您也必须“复制”ID。如果班级 1 变为 1.1、1.2 和 1.3，则更喜欢班级 1 的学生应该以相同的优先级链接到班级 1.1、1.2 和 1.3。

我看到的主要问题是 Python 很慢，看起来你有 550 个学生 * 5 个选择 * 21 个班级 * 27 个容量 = 1,559,250 个连接。这将占用大量内存和大量时间，并且该存储库上的未解决问题并没有让我对它能够计算这一点充满信心。我自己测试了一些具体案例，但其中一个案例陷入了无限循环。如果您想为此使用 Python，我建议您改用Brian M. Clapper 的实现，因为我也测试过它并且没有遇到任何问题。

于 2022-01-19T18:29:07.203 回答
0

因为学生只陈述了 5 个选项，所以可能无法完美匹配。如果您不希望产生完美的匹配，那么您可以使用serial dictatorship。它会比匈牙利算法快得多。

一个伪代码：

students = list of students
for stud in students:
    if the number of students yet to be matched is greater than total of minimum quotas:
        if [classes in stud's preference list that have not reached max capacity]:
            stud is assigned to their most preferred among them
            update the class's remaining seats
        else:
            stud is unmatched
    else:
        if [classes in stud's preference list that have not reached min capacity]:
            stud is assigned to their most preferred among them
            update the class's remaining seats
        else:
            stud is unmatched
于 2022-01-20T00:21:33.173 回答