Несколько дней назад я задал вопрос о том, как превратить проблему планирования занятий в университете в проблему булевой удовлетворенности.

(Планирование классов для булевой выполнимости [сокращение за полиномиальное время])

Я получил ответ от @Amit, который был очень элегантным и легко кодируемым. По сути, его ответ был таким: вместо рассмотрения курсов он рассматривал временные интервалы.

Поэтому для i-го курса он просто указал все возможные интервалы для этого курса. И мы получаем решение, когда для каждого курса существует хотя бы один истинный интервал и когда ни один интервал не перекрывает другой.

Этот метод работает очень хорошо, когда мы рассматриваем только курсы и ничего больше. Я обобщаю это, кодируя комнату внутри интервала.

например, вместо [8-10] сказать, что курс может происходить между 8 и 10 часами утра.

Я использовал [0,00801 - 0,01001], чтобы сказать, что курс может проходить между 8 и 10 часами в комнате 1.

Я уверен, что вы в настоящее время блуждаете "зачем использовать двойной?" хорошо, потому что вот моя проблема:

Чтобы продолжить обобщать этот метод, я также кодирую n ° учителя в этом интервале.

Я использовал [1.00801 - 1.01001], чтобы сказать, что курс может проходить между 8 и 10 часами в комнате 1 и преподаваться учителем № 1.

Вот что я получил сейчас:

таким образом [1.008XX - 1.010XX] может происходить в то же время, что и [2.008YY - 2.010YY], что верно, если учитель 1 преподает в комнате X между 8 и 10 часами утра, учитель 2 может преподавать также в Y между 8 утра и 10 утра, если и только если комната доступна.

Проблема в том, что с помощью этого метода я не могу гарантировать, что XX и YY будут разными и что YY будет доступен, потому что [1.008XX - 1.010XX] не перекрываются [2.008XX - 2.010XX], так что пока решатель считаю это возможным.

И я до сих пор не имею ни малейшего понятия о том, как обеспечить это, используя этот метод интервала ... Мне нужен способ кодирования {Interval, room и teacher-id} для того, чтобы:

учитель не может быть в 2 местах в одном интервале.не может быть 2 учителя в одной комнате за один и тот же интервал.по крайней мере, 1 интервал верно по курсу.

Заранее спасибо за помощь, С наилучшими пожеланиями!

Контрольный вопрос: Планирование классов для булевой выполнимости [Сокращение полиномиального времени] Заключительная часть