algorithm - 将学生与实验室配对

Question

我们在一所大学的理学硕士类(class)中遇到了一个实际问题，其中一名学生必须被分配到实验室。涉及的人数不是很多，所以我不是在寻找一个快速的解决方案，而是一个易于理解的解决方案，这样学生和组长都可以为所提议的配对提供理由。

给定 2 个列表

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

这里每个学生 S 都按偏好顺序列出了他们的前 3 个实验室。所以理想情况下，学生 S1 会喜欢在实验室 i 中。如果那个 Lab 不想要他，那么他会想在 Lab j 等等。

和

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

每个实验室列出他们希望在实验室中的学生的位置。所以在这里，如果学生 i 选择了这个实验室(在他的前 3 个选择之一)，实验室 1 将首先想要学生 i。请注意，实验室可以挑选尽可能多的学生。

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

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

满意度得分定义为

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

直觉上，这会尝试将尽可能多的学生和实验室与他们的最佳选择配对。

所以我为这个优化算法寻求一种算法，该算法寻求最小化 Z 的解决方案。

可能的部分解决方案如下:

定义一个长度为L的数组Assigned，并初始化为全假

首先，匹配第一个选择并丢弃这些学生

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

函数 RANK(Lj,s) 返回 Lab j 学生在首选列表中的位置。如果学生 s 不在实验室 j 的期望学生列表中，则返回无穷大。

我不确定如何从这里开始，或者这种方法是否会最小化分数 Z。

如有任何帮助，我们将不胜感激。

Answer 1

在我看来，您正在尝试解决 https://en.wikipedia.org/wiki/Assignment_problem 的一个实例因此可以通过例如解决https://en.wikipedia.org/wiki/Hungarian_algorithm .分配问题根据代理和任务进行讨论。在这里，代理人可能是学生，任务可能是实验室中的空闲位置。如果您有比学生更多的空闲槽，那么您可以创建虚拟学生，其中将任何虚拟学生分配给任何空闲槽的成本始终相同。

您可能希望查看 https://en.wikipedia.org/wiki/Stable_marriage_problem以及它指出的医院/居民问题。这看起来像是在尝试解决您正在查看的问题，但它可能不会使用您的特定满意度分数。这些解决方案已经存在了足够长的时间，可以针对您未提及的潜在政治问题进行测试。人们是否有任何动机对自己的偏好撒谎？该解决方案是否会导致两个学生同意他们想在作业后交换分配给他们的位置的情况？