1

Say you have a class with 5 sections: A,B,C,D,E. Each section meets at different times, thus students registering for the course will have preference for which section they will take (they can only take one section). When students register for the course, they list 3 sections they would prefer to take, in order of preference.

Each section has n students. Let's say for simplicity that exactly n*5 students have registered for the course.

So, the question is: How do you efficiently match students to their preferred section?

I've seen some questions with similar matching scenario questions, but none quite fit and I'm afraid I don't know enough about algorithms to make up my own. BTW, this is a real problem and I know the department in question takes a few days to do it by hand.

4

3 回答 3

3

为了确定每个学生是否可以分配到首选部分，请在以下网络中构造一个整数值的最大流，其中三个Xs 代表从学生到他们喜欢的部分的容量为 1 的弧（多项式时间通过，例如，推重标签算法）。当且仅当最大流量移动m = n*5单位时，才有解决方案；然后分配取决于每个学生的哪些弧线饱和。

capacity-1 arcs            capacity-n arcs
       |                          |
       v                          v
         student 1
       / student 2       section1
       /  .           X  section2 \
source <  .           X  section3 > sink
       \  .           X  section4 /
       \ student m-1     section5
         student m

考虑到优先顺序，切换到求解最小成本流问题，仍然可以多时间求解（尽管您可能会发现通用 LP 求解器的网络单纯形模式更易于使用），它允许指定成本对于每个弧。根据您认为公平的情况为每个偏好级别选择一个分数。

我很肯定以前有人问过这个问题，但是调度问题就像雪花一样，我无法仅通过关键字找到旧问题。

于 2013-08-12T12:21:18.320 回答
0

有没有一个评分系统，如果学生 1 在 A 部分，分数是 20？（另一方面，如果学生 2 在 A 部分，分数是 15？

我在问，因为如果 A 部分只剩下一个位置，并且学生 1 和 2 都最喜欢 A 部分，那么谁先注册就会得到这个位置。而不是谁最适合（更高的分数）。

如果没有评分，您可以遍历学生并将他们放在他们喜欢的部分。如果第一个已满，请尝试他们的第二个偏好，然后是下一个。如果学生喜欢的三个部分都已填满，只需将它们注册到未填满的部分即可。

（如果有评分会有所不同，因为您必须为每个部分设置一个优先级队列并将其最大化。）

于 2013-08-12T09:20:13.533 回答
0

也许您可以将它们随机分配到各个部分。接下来，您选择随机的学生对并考虑交换它们是否会改善分布（是否会增加与他们偏好的匹配？）。您可以进行迭代，直到 X 次迭代没有任何改进。这显然是一种非常幼稚的方法，但如果您的样本很小，它可能会很快收敛。您不能保证您拥有最佳解决方案，但因此您需要一种可能无法实现的蛮力方法。

于 2013-08-12T08:29:51.350 回答