Оптимизация расписания номеров / временных интервалов

Question

Люди могут выбрать до 5 из 25 лекций заранее. Все эти лекции проводятся в один день в пяти комнатах на пяти временных интервалах. Каждая (предпочтительная) лекция, которую слушатель может посетить, делает ее немного счастливее, каждая лекция, которую он выбрал, но не может посещать (потому что другая предпочтительная лекция находится в том же временном интервале), делает его немного несчастнее. Список предпочтительных лекций не взвешен (по крайней мере, владельцам регистраций не было приказано упорядочить свои предпочтения, но если это облегчит задачу, я могу предположить, что первый выбор имеет наивысший приоритет и так далее, что информация доступна).
Есть ли способ максимизировать общее счастье или приближение, не пробуя каждый возможный график? Я нашел пустую заглушку для проблемы больниц / жителей в Википедии, которая в значительной степени похожа на подобную проблему (?)

Проблема больниц / жителей, также известная как проблема приема в колледж, отличается от проблемы стабильного брака тем, что «женщины» могут принимать «предложения» от более чем одного «мужчины» (например, больница может принять несколько жителей, или колледж может принять входящий класс более чем одного студента). Алгоритмы решения проблемы больниц / жителей могут быть ориентированы на больницу (оптимально для женщин) или ориентированы на резидентов (оптимально для мужчин).

Answer 1

Это может быть излишним для ваших требований, но вы можете рассмотреть генетический алгоритм , как описано в Планировании конференции PDC 2008 Майка Свансона с использованием генетического алгоритма .

Он обсуждает эту технику в 32-минутном интервью на Канале 9 , озаглавленном Алгоритмы и структуры данных: Майк Свансон - Генетический планировщик сеансов .

Answer 2

Я не думаю, что вы предоставили всю информацию. Если у вас есть всего 25 лекций (при условии отсутствия дубликатов, как это не было описано) с 5 временными интервалами и 5 комнатами, то каждый посетитель всегда пропускает по 4 лекции в каждом слоте. Учитывая, что вы не предусмотрели каких-либо ограничений вместимости лекций, и вы прямо сказали, что они не взвешены, нет никакой разницы в совокупном (или даже личном) счастье между всеми, кто посещает одну и ту же лекцию, распределяя участников (равномерно или неравномерно) по все 5 одновременных лекций.