Таблица рассадки по парам

Калькулятор строит таблицу пар для рассадки студентов или учащихся по парам с учетом их пожеланий.

Калькулятор был создан по запросу пользователя.

Задача была сформулирована следующим образом: «Я учитель, и прошу каждого из моих учеников выбрать двух человек, с которыми они бы хотели сидеть вместе. Затем мне нужно записать все комбинации на бумагу и попытаться их организовать. Некоторые дети более популярны в классе и их имена появляются чаще, и с другой стороны есть дети, с которыми никто не хочет сидеть. Каждый раз это довольно трудное решение, поэтому я часто меняю рассадку. Если бы можно было ввести список учеников с их пожеланиями, и получить итоговую комбинацию, это бы здорово сэкономило бы мне время».

Очевидно, что эту задачу нельзя решить методом полного перебора всех комбинаций. Даже для 14 учеников количество комбинаций очень велико - 9166452815*6 = 681,080,400.

Чтобы решить эту задачу я использовал так называемый генетический алгоритм (подробнее про генетические алгоритмы можно прочитать здесь — Как из мухи сделать слона. ). Как и в случае с любым эвристическим алгоритмом, он не обязательно выдаст оптимальное решение, но в большинстве случаев решение должно быть достаточно хорошим для практических целей.

Конечно, есть алгоритмы для точного решения — это из теории графов, алгоритмы нахождения максимального паросочетания, но в реализации они достаточно сложны. Как минимум сложнее чем реализованный здесь генетический алгоритм.
Что касается генетического алгоритма, то можно поиграться с его параметрами «число поколений» и «размер популяции», чтобы посмотреть, найдет ли он другие решения. По умолчанию результат для 14 студентов выглядит неплохо.

PLANETCALC, Таблица рассадки студентов по местам по парам

Таблица рассадки студентов по местам по парам

Таблица предпочтений

arrow_upwardarrow_downwardИмяarrow_upwardarrow_downwardПожелания
Размер страницы:

Знаков после запятой: 2
Эффективность рассадки
 

Creative Commons Attribution/Share-Alike License 3.0 (Unported) PLANETCALC, Таблица рассадки по парам

Комментарии