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

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

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

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

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

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

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



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

	Имя	Пожелания
			

Размер популяции

Число поколений

Точность вычисления

Знаков после запятой: 2

Рассчитать

Эффективность рассадки

 

Файл очень большой, при загрузке и создании может наблюдаться торможение браузера.

Загрузить 

 Ссылка  Сохранить  Виджет