Блог

Для проекта я пытаюсь создать подходящую платформу для подбора студентов на семинары в соответствии с их предпочтениями. Требования к этому соответствию следующие:

• Это список семинаров. Каждый семинар имеет ограниченное количество участников, но у участников нет предпочтений
• У каждого студента есть список из трех семинаров, которые ему нравятся больше всего.
• У них два временных интервала, каждый из которых предлагает каждый семинар.
• Каждый студент должен быть подобран таким образом, чтобы его предпочтения считались как можно более оптимальными для обоих временных интервалов, например, в оптимальном случае студент получает свой первый и второй выбор каждый в одном из временных интервалов.
• Порядок временных интервалов не важен.

Я подумал об использовании алгоритма Гейла Шепли, адаптированного для решения задачи «много к одному». Но у этого решения, похоже, есть несколько проблем. С помощью алгоритма можно было бы реализовать сопоставление числа студентов с одним семинаром. Чтобы добиться того же для двух семинаров, вам придется запустить его несколько раз и удалить предпочтения, уже удовлетворенные в первом раунде. Но решение htis не имеет возможности назначить курс с более высоким приоритетом в более позднем временном интервале, если это улучшит соответствие. Кроме того, сопоставление также всегда приводило бы к оптимальным результатам в каждом раунде, но было бы возможно, что одному человеку будет присвоено высшее предпочтение в обоих раундах сопоставления, в то время как другому человеку будет присвоена менее предпочтительная группа в обоих раундах, даже если можно было бы справедливо назначить их, каждый из которых получит наивысшее предпочтение один раз.

Кто-нибудь знает хорошее решение этой проблемы?