Таблица рассадки по парам
Калькулятор строит таблицу пар для рассадки студентов или учащихся по парам с учетом их пожеланий.
Калькулятор был создан по запросу пользователя.
Задача была сформулирована следующим образом: «Я учитель, и прошу каждого из моих учеников выбрать двух человек, с которыми они бы хотели сидеть вместе. Затем мне нужно записать все комбинации на бумагу и попытаться их организовать. Некоторые дети более популярны в классе и их имена появляются чаще, и с другой стороны есть дети, с которыми никто не хочет сидеть. Каждый раз это довольно трудное решение, поэтому я часто меняю рассадку. Если бы можно было ввести список учеников с их пожеланиями, и получить итоговую комбинацию, это бы здорово сэкономило бы мне время».
Очевидно, что эту задачу нельзя решить методом полного перебора всех комбинаций. Даже для 14 учеников количество комбинаций очень велико - 91×66×45×28×15×6 = 681,080,400.
Чтобы решить эту задачу я использовал так называемый генетический алгоритм (подробнее про генетические алгоритмы можно прочитать здесь — Как из мухи сделать слона. ). Как и в случае с любым эвристическим алгоритмом, он не обязательно выдаст оптимальное решение, но в большинстве случаев решение должно быть достаточно хорошим для практических целей.
Конечно, есть алгоритмы для точного решения — это из теории графов, алгоритмы нахождения максимального паросочетания, но в реализации они достаточно сложны. Как минимум сложнее чем реализованный здесь генетический алгоритм.
Что касается генетического алгоритма, то можно поиграться с его параметрами «число поколений» и «размер популяции», чтобы посмотреть, найдет ли он другие решения. По умолчанию результат для 14 студентов выглядит неплохо.
Таблица рассадки студентов по местам по парам
Таблица предпочтений
| Имя | Пожелания | ||
|---|---|---|---|
Комментарии