Сопряжение студентов с лабораториями

Question

У нас есть практическая проблема в программе MSc в университете, где студент должен быть назначен в лабораторию. Цифры не очень большие, поэтому я не ищу быстрое решение, а просто понятное решение, чтобы как ученики, так и лидер группы могли быть предоставлены обоснование предлагаемого спаривания.

Учитывая 2 Список

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

Здесь каждый студент S перечислил свои лучшие 3 лаборатории в порядке предпочтения. Итак, ученик S1 в идеале хотел бы быть в Lab i. Если эта Лаборатория не хочет его, тогда он захочет быть в Лаборатории j и так далее.

и

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

Где каждая лаборатория списки студентов в том, что они хотели бы в лаборатории. Итак, здесь Lab 1 сначала захочет студент i, если он выбрал эту лабораторию (в одном из его лучших 3 вариантов). Обратите внимание, что лаборатория может выбрать как можно больше учеников.

Ограничение состоит в том, что каждый учащийся может находиться только в одной лаборатории, но каждая лаборатория может имеет 0,1 или более студентов.

Цель состоит в том, чтобы создать совпадение (Si, Lj), в котором все ученики назначаются лаборатории, а спаривание приводит к наибольшему удовлетворению .

удовлетворения оценки определяются как

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

Наглядно это пытается спариваться как много студентов и лабораторий с их лучшим выбором.

Так я ищу алгоритм для этой оптимизации алгоритма, который ищет решение, которое является минимизация Z.

Возможное частичное решение заключается в следующем:

Определяем массив под названием Assigned длины L. И инициализировать это все ложные

Во-первых, матч первого выбора и отбрасывать этим студентам

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. Если ученик не находится в списке желаемых учеников в лаборатории 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 и проблему с больницами и жильцами, на которую он указывает.Похоже, он пытается решить проблему, на которую вы смотрите, но, вероятно, не использует ваш конкретный счет удовлетворения. Эти решения были достаточно круглыми, чтобы их можно было протестировать против возможных политических проблем, о которых вы не упоминаете. Есть ли стимул для людей лгать о своих предпочтениях? Будет ли решение привести к ситуации, когда два студента соглашаются с тем, что они хотят поменять местами свои назначенные слоты после назначения?