logo标签列表

课程分配算法

algorithmvariable-assignment
12
我需要为M门课程分配N个人，每个人指定了他们的第一和第二选择，每门课程有一个最大出席人数。每个人只能参加一门课程。算法应该找到一个解决方案，其中：
  1. 尽可能多地将人员指派到其首选课程之外的其他课程
  2. 尽可能多地将人员分配到他们的第一选择中（考虑1优先级更高）。
对于少于最大出席人数的首选者，将所有这些人员分配给该课程。
对于其他课程： 1. 将选择该课程作为第一选择的随机人员放入该课程，直到该课程已满。 2. 对于少于空位数的第二选择，将所有这些人员分配给该课程。 3. 对于其他课程： 1. 在他们的第一选择（然后是第二选择）中寻找已选择其他仍有空位的课程的人（如果找到多个，则选择选择剩余空位最多的课程），将此人移至他们的第二选择，并分配缺失的人员。
我仍然认为由于最后一步，这个算法不会找到问题的最优解。有没有想法如何使其更好？是否还有其他算法可以解决这个问题？
顺便提一下，在我上学时，我制作了一张所有课程及其先修课程的图表。这使得非常清晰，哪些事情是最关键的，并帮助混合难易程度不影响毕业日期 :-) - phkahler
假设课程A和课程B的最大容量都是1，有5个人选择了AB，那么还有3个人没有得到他们喜欢的课程。这三个人会被分配到其他课程吗？还是他们会保持未分配状态？ - Pops
@Lord Torgamus：他们不应该被分配到任何课程。 - neo
4个回答
6
如果可能的话，请将每个人放在他们的第一选择课程中。如果有人没有得到第一选择，则将他们放在第二选择中。现在，我们可能会有一些人没有得到任何选择（“失败者”）。找到一个已经得到他的第一选择课程，并且也是“失败者”的第二选择的人。这个人将被重新分配到他的第二选择，而“失败者”将占据他的位置。如果没有这样的人，那么你的问题就无法解决。请注意，这最大化了得到第一选择的人数。如果你得到了第二选择，那么它意味着以下两种情况之一：1.其他人已经将你的第一选择作为他的第一选择；2.其他人将你的第一选择作为他的第二选择，但只是因为他的第一选择被其他学生的第一选择填满了。
2
这类似于稳定婚姻问题。
给定 n 个男人和 n 个女人，每个人都用唯一的数字将异性成员按偏好顺序排名为 1 到 n。将男人和女人组合在一起，使得没有两个异性会比他们当前的伴侣更喜欢对方。如果没有这样的人，所有的婚姻都是“稳定的”。
更新：
考虑到@bdares的评论以及课程有限的容量，将问题视为稳定匹配将很困难。
我会将其解决为基于第一选择人数的目标函数的线性规划，并将课程大小作为约束条件。
6
相似，但我认为有很大的不同……课程本身并没有偏好于哪些学生，“稳定婚姻问题”的简单解决方案因此不适用。 - user684934
0

第一个问题可以建模为最大基数二分图匹配问题。第二个问题可以建模为加权二分图匹配问题（也称为分配问题）。

0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接