Как реализовать алгоритм трехмерного двустороннего сопоставления в PHP

Question

Мне нужно реализовать алгоритм трехмерного двудольного сопоставления.У меня есть этот код , который представляет собой двухмерный алгоритм двойного сопоставления.Я был в состоянии преобразовать его в PHP, и он отлично работает.Однако я только что понял, что в моей программе мне нужно сопоставить курсы с комнатами для определенных временных интервалов .Если я использую алгоритм двухмерного сопоставления, уже назначенные комнаты не могут быть использованы для курсов в других временных интервалах.Я хочу иметь возможность провести матч, в котором одна и та же комната может быть снова использована для другого курса, если временной интервал будет другим.Как я могу изменить этот код, чтобы использовать в качестве входных данных граф с тремя измерениями: graph [u] [v] [w], где u - индекс курса, v - индекс комнаты, а w - индекс временного интервала?

Answer 1

Двухстороннее сопоставление не работает таким образом. «Би» означает два. Тем не менее, вы можете легко преобразовать график в двудольный. Вместо того, чтобы думать о курсах слева и комнатах справа, думайте так: курсы все равно останутся слева, но справа будут объединены узлы комнаты и временного интервала. Как это -

Course CSE 101------Room 301 Time 10:00 - 11:00
              \
               \
                \               
                 \
                  \
Course CSE 145------Room 301 Time 11:00 - 12:00
              \
               \
                \            
                 \
                  \-Room 301 Time 12:00 - 13:00 

Если вы работаете над проблемой реального мира, будут другие ограничения, такие как назначение 3 классных комнат для курса в неделю, 2 класса одного и того же курса не должны проводиться в один день и т. Д. В таких случаях вам придется перейти от двудольной модели графа к сетям общего потока.