学生与实验室配对

Question

我们在一所大学的MSc项目中遇到了一个实际问题，在这个项目中，学生必须被分配到实验室。所涉及的人数不是很大，所以我不是在寻找一个快速的解决方案，而是一个容易理解的解决方案，以便学生和组长都能得到建议的配对的理由。

给定2份清单

 S1 Li,Lj,Lk
 S2 Lu,Lv,Lw
 .
 Sn

在这里，每个学生S已经列出了他们的前3名实验室的优先顺序。所以，理想情况下，学生S1应该是在i实验室，如果那个实验室不想要他，那么他就会想在实验室j，等等。

和

 L1 Si,Sj,Sk
 L2 Su,Sv,Sw,Sx,Sy
 .
 Lm

每个实验室都会列出他们想在实验室里学习的学生。因此，在这里，实验室1首先要学生我，如果他选择了这个实验室(在他的前3选择之一)。请注意，实验室可以挑选尽可能多的学生。

限制是每个学生只能在一个实验室，但每个实验室可能有0,1或更多的学生。

目标是产生一个匹配(Si，Lj)，其中所有的学生被分配到一个实验室和配对导致最大的满意。

满意度分数被定义为

Z=sum_{i=1..n}( sum_{j=1...m} (abs( i-j))

从直觉上看，这试图将尽可能多的学生和实验室与他们的最佳选择结合起来。

因此，我为这个优化算法寻找一个算法，它寻求一个解，就是最小化Z。

可能的部分解决办法如下：

定义一个名为L长度赋值的数组，并将其初始化为所有false

第一，匹配第一选择，抛弃这些学生。

for each s in {S1,..,Sn}:
      Assigned[s]=False
Assigned[s]=j
repeat until all(Assigned)==True:
for each s in S:
     if RANK(Lj,s)==1:
          Assigned[s]=j # i.e. pair student s with lab Lj
          del(S,s) # delete s from the list S

函数秩(Lj，s)返回实验班学生首选列表中的位置。如果学生不在实验室j中所需的学生列表中，则返回无穷大。

我不知道如何从这里开始，或者这种方法是否将Z分数降到最低。

任何帮助都将不胜感激。

Answer 1

在我看来，您正在试图解决problem的一个实例，因此可以通过例如algorithm来解决。分配问题以agents和任务的形式进行讨论。在这里，一个代理人可能是一个学生，一个任务，一个在实验室里的空闲时间。如果您有比学生更多的免费插槽，那么您可以创建虚拟学生，其中分配给任何虚拟学生的费用总是相同的。

你可能想看看problem和它所指的医院/居民问题。这看起来像是在试图解决你所看到的那种问题，但它可能并没有使用你的特别的满足感。这些解决方案已经足够长的时间来测试潜在的政治问题，而你没有提到这些问题。人们对自己的喜好有什么动机去撒谎吗？该解决方案是否会导致两名学生同意在作业完成后交换分配的位置？