Я работал над этим общим алгоритмом распределения для студентов.
Псевдокод для него (реализация Python):
for a student in a dictionary of students:
for student preference in a set of preferences (ordered from 1 to 10):
let temp_project be the first preferred project
check if temp_project is available
if so, allocate it to him and make the project unavailable to others
break
Проще говоря, это попытается распределить проекты, начиная с наиболее предпочтительных. Как это работает, из набора, скажем, 100 проектов, вы перечисляете 10, которые вы хотели бы сделать. Таким образом, 10-й проект был бы не «наименее предпочтительным», а наименее предпочтительным в выбранном ими наборе, что не так уж и плохо.
Очевидно, что если он не может выделить проект, студент просто возвращается к базовому варианту, который является распределением Нет, с рангом 11.
То, что я делаю, - это вычисление «качества» распределения на основе взвешенной суммы рангов. Таким образом, чем ниже цифры (то есть более предпочтительные проекты), тем лучше качество распределения (т. Е. Больше студентов предпочитают проекты).
Это в основном то, что у меня сейчас есть. Все просто и работает.
Сейчас я работаю над этим алгоритмом, который пытается минимизировать вес распределения локально (этот псевдокод немного запутан, извините).
Единственная причина, по которой это, вероятно, сработает, заключается в том, что мое "пространство поиска", как оно есть, не особенно велико (просто очень общее, анекдотическое наблюдение, заметьте). Поскольку проект относится только к моему департаменту, у нас есть свои ограничения. Таким образом, количество студентов не может превышать 100, а количество предпочтений не будет превышать 10.
for student in a dictionary/list/whatever of students:
where i = 0
take the (i)st student, (i+1)nd student
for their ranks:
allocate the projects
and set local_weighting(N) to be sum(student_i.alloc_proj_rank, student_i+1.alloc_proj_rank)
these are the cases:
if N is 2 (i.e. both ranks are 1):
then i += 1 and
and continue above
if N > 2 (i.e. one or more ranks are greater than 1):
let temp_N be N:
pick student with lowest rank
and then move him to his next rank
and pick the other student and reallocate his project
temp_N is sum of the the ranks
if temp_N is < N:
then allocate those projects to the students
i += 1
and move on for the rest of the students
Обновлено с учетом комментариев:
Что я пытаюсь сделать:
Я пытаюсь добиться "минимального распределения веса" между группами по два студента за раз (т.е. по местному)
Распределение веса представляет собой сумму рангов, назначенных студентами. Мы хотим, чтобы студенты получили свои самые высоко оцененные проекты в целом. Таким образом, если у студента А есть проект, он занял 1 место, а у студента Б - проект, который он оценил 5, то их локальный вес распределения равен 6. Если мы переместим студента А в его проект ранга 2, и, следовательно, студент В переместится в ее ранг. 3 проект, то вес теперь составляет 5,5 <6, что лучше в целом. </p>
Итак, я начинаю со своей коллекции учеников, а затем начинаю их перебирать
Я начинаю с первого и второго ученика и выделяю им свои проекты
Затем я вычисляю вес, как описано выше. Учитывая, что вес равен рангу, если оба ранжируются на 1, вес 2. Это настолько хорошо, насколько это возможно, и мы хотим перейти ко второму и третьему ученикам.
Теперь, если вес больше 2, что означает, что один или несколько проектов ранжируются больше 2, мы пытаемся получить лучшую версию.
Таким образом, мы берем ученика с наименьшим рангом, а затем переводим его / ее вниз на один ранг (поэтому, если он / она был рангом 1, это понижает его до ранга 2)
И затем мы пытаемся перераспределить другого ученика на другое звание.
Теперь, если вес лучше, чем предыдущий, тогда мы допустим, что это будет новый вес, и пусть у них будут эти проекты. Если это хуже или равно, тогда мы просто переходим к следующему дуэту студентов.
Локально, для студентов, эта штука продолжает пытаться, пока не наберет минимальный вес и не сможет добиться большего успеха.
Надеюсь, это объясняет, что я пытаюсь сделать?
Итак, вопросы:
Это своего рода модификация имитированного отжига, но любые комментарии по этому поводу приветствуются.
Как бы я отследил, какой студент (i) и какой (i + 1)
Если мой общий список учеников равен 100, то это может привести к путанице (i + 1) = 101, поскольку ее нет. Как я могу обойти это?
Есть ли непосредственные недостатки, которые могут быть обнаружены?
Дополнительная информация:
Мой словарь для студентов устроен так:
students[student_id] = Student(student_id, student_name, alloc_proj, alloc_proj_rank, preferences)
where preferences is in the form of a dictionary such that
preferences[rank] = {project_id}