Люди могут выбрать до 5 из 25 лекций заранее. Все эти лекции даются в один день в пяти комнатах в пяти временных слотах. Каждая (предпочтительная) лекция, которую может прослушать слушатель, делает ее немного счастливее, каждая лекция, которую он выбрал, но не может присутствовать (потому что другая предпочтительная лекция находится в одном и том же временном интервале) делает его немного неудовлетворительным. Список предпочтительных лекций не взвешен (по крайней мере, владельцам регистрации не приказали приказать свои предпочтения, но если это облегчит ситуацию, я могу предположить, что первый выбор имеет наивысший приоритет и т. Д., Эта информация доступна).
Есть ли способ максимизировать общее счастье или приближение, не пытаясь выполнить все возможные расписания? Я нашел пустую заглушку для проблемы больницы/жителей на википедии, которые в значительной степени походит на аналогичные проблемы (?)оптимизация расписания номеров/временных интервалов
ответ
Это может быть излишним для ваших требований, но вы можете подумать о genetic algorithm, как описано в статье Майка Суонсона PDC 2008 Conference Scheduling Using a Genetic Algorithm.
Он обсуждает технику в 32-минутном интервью на Channel 9 под названием Algorithms and Data Structures: Mike Swanson - Genetic Session Scheduler.
бит неопределенный, но я дам ему +1 как можно скорее (15 rep, позвольте мне посмотреть, могу ли я ответить на любой вопрос здесь). Я все еще надеюсь на более «прямой» подход (или доказательство того, что этого не происходит). Я имею в виду графики конференций ... это такая необычная проблема?;-) – chendral
Нет, это не необычная проблема, но создание расписания - это проблема «NP hard» (что означает многочленное время ... очень долго). Хотя вы можете использовать эвристический подход, это может быстро уйти от вас, поскольку это в основном грубая сила. Генетический алгоритм, вероятно, будет работать лучше всего для вас, так как Грант говорит –
Итак, он * * np-hard и есть только выбор между (хорошими) приближениями или грубой силой ... – chendral
Я не думаю, что вы предоставили все информация. Если у вас есть 25 полных лекций (при отсутствии дубликатов, как это не было описано) с 5 временными интервалами и 5 комнатами, тогда всегда будет проходить 4 лекции, пропущенных в каждом слоте любым участником. Учитывая, что вы не предоставили никаких ограничений по емкости для лекций, и вы явно сказали, что они не взвешены, нет никакой разницы в совокупном (или даже личном) счастье между всеми, кто посещает ту же лекцию, которая распределяет участников (равномерно или неравномерно) все 5 параллельных лекций.
Вопрос не ограничивает количество номера. Без этого ограничения 14 лекций могут быть в слоте А и только 3 лекции в слоте B, чтобы облегчить максимальное наслаждение посетителям. – jmucchiello
«Люди могут выбрать до 5 из 25 лекций». Поэтому для них не нужно всегда пропустить 4 лекции. Все их предпочтительные 5 лекций находятся в разных временных слотах, и они совершенно счастливы. Все их предпочтительные лекции проходят в один временной промежуток, и они очень грустны и не будут присутствовать вообще. – chendral
«Вопрос не ограничивает количество комнат. Без этого ограничения« Неправильно. «Все эти лекции даются в один день в пяти комнатах» Есть только пять комнат. 5 комнат, 5 временных интервалов, 25 лекций, все комнаты, занятые в любой момент времени (возможно, если никто не хочет эту лекцию, проигнорируйте это) – chendral
О, пожалуйста, это полностью домашний вопрос, который здесь прекрасен, но вы должны пометить их как таковые. –
«О, пожалуйста, это полностью вопрос о домашнем задании», если это не так. – chendral
В реальном мире есть дополнительные ограничения: могут ли все лекторы читать свои лекции на всех временных интервалах? Есть ли две или более лекции, предоставленные одним и тем же лектором, снова устраняя возможные комбинации? Вместимость номера? – jmucchiello