Блог

Я пытаюсь создать планировщик для спортивной лиги, и я хотел бы распределить команды по группам, чтобы каждая команда получала по одной игре на группу. Я думаю, что то, что я пытаюсь сделать, — это существующая проблема в информатике, но я не знаю, как она называется, и у меня проблемы с поиском информации об этом. В любом случае, вот ситуация:

Допустим, у меня есть набор команд A = {1,2,3,...,n} и набор пар этих команд B = {(1,2), (1,3), (2,4), (6,9),...} . У B нет всех возможных комбинаций команд из A. Предположим, что A имеет четное количество команд. Моя программа пытается создать подмножество B (назовем это подмножеством S) таким образом, чтобы каждая команда из A появлялась в S ровно один раз. Он делает это, перемещая пары из B в S по одному за раз. Предположим, что он уже поместил несколько пар в S. Как я могу узнать, возможно ли успешно создать S, учитывая текущую ситуацию?

Пример:

 A = {1,2,3,4}, B = {(1,2), (1,3), (1,4), (3,4)}

If after one move, S = {(1,2)}, then it can be completed by moving (3,4).
If after one move, S = {(1,3)}, then it cannot be completed.
  

Обновить:
Этот алгоритм будет одной из эвристик, которые я использую в своем генераторе расписаний. Цель состоит в том, чтобы неявно разделить расписание на «волны», где у каждой команды по одной игре на волну. Итак, предположим, что у меня есть пул из 16 команд, и у каждой команды будет по 5 игр против других команд в пуле. Идеальное расписание должно гарантировать, что ни одна команда не проведет вторую игру до того, как каждая команда проведет хотя бы одну игру. Планировщик выбирает игры по одной и назначает им дату. Итак, идея состоит в том, чтобы планировщик отслеживал игры, запланированные в этой «волне», и никогда не выбирал игру, которая помешала бы каждой команде сыграть ровно один раз в текущей волне. Планировщик также использует множество других эвристик, поэтому я не могу явно упорядочить игры и упорядочить их.

Прошу прощения, если это неясно или не очень строго. Не стесняйтесь обращаться за разъяснениями, и я сделаю все возможное, чтобы объяснить дальше.

Это проблема максимального соответствия в теории графов. Существует несколько известных алгоритмов для решения этой проблемы.

В вашем проблемном графике G (V — набор вершин, E — набор ребер), где V = A, E = B. Также добавьте противоположные ребра к графику. Вес каждого ребра равен 1.

Я предлагаю вам использовать венгерский алгоритм для двудольных графов и алгоритм Эдмонда для других.

Важно сделать некоторые предположения, чтобы прояснить то, что представлено ниже.
Сначала предположим, что мы говорим о 16 командах в лиге настольного тенниса, и вам нужно расписание, в котором все команды играют по пять игр, не дублируя ни одного соперника.
Во-вторых, вы хотите, чтобы все 16 команд завершили игру в каждом сете, прежде чем какая-либо команда сыграет снова.
В-третьих, вы хотите, чтобы все команды были распределены для игры за 8 столами, а не чтобы одна команда всегда играла за одним столом.

Если я правильно понял предположения, то вам нужны первые 5 «наборов» (вы называете каждый набор волной) игр из сбалансированного кругового расписания из 16 команд. Это даст вам командные матчи турнирного типа, в которых каждая команда играет по 5 игр против 5 разных команд. Каждый сет (или волна) состоит из 8 игр, и ни одна команда не всегда играет за одним столом, и команды не играют игры в следующем сете, пока все команды не закончат играть текущий сет.

Ниже приведены первые 5 «наборов» из сбалансированного расписания из 16 команд, которое я создал для вас. Проверьте это.

 16 TEAM SCHEDULE       DATE 8/3/14            

DATE   DAY  TIME    LOCATION    GM#  HOME VS VISITOR

___ __ ___ _______  Table #1     1   #1  v  #16
___ __ ___ _______  Table #2     1   #2  v  #15
___ __ ___ _______  Table #3     1   #3  v  #14
___ __ ___ _______  Table #4     1   #4  v  #13
___ __ ___ _______  Table #5     1   #5  v  #12
___ __ ___ _______  Table #6     1   #6  v  #11
___ __ ___ _______  Table #7     1   #7  v  #10
___ __ ___ _______  Table #8     1   #8  v  #9

___ __ ___ _______  Table #1     2   #13 v  #2
___ __ ___ _______  Table #2     2   #15 v  #1
___ __ ___ _______  Table #3     2   #16 v  #14
___ __ ___ _______  Table #4     2   #12 v  #3
___ __ ___ _______  Table #5     2   #11 v  #4
___ __ ___ _______  Table #6     2   #10 v  #5
___ __ ___ _______  Table #7     2   #9  v  #6
___ __ ___ _______  Table #8     2   #7  v  #8

___ __ ___ _______  Table #1     3   #6  v  #7
___ __ ___ _______  Table #2     3   #16 v  #12
___ __ ___ _______  Table #3     3   #15 v  #13
___ __ ___ _______  Table #4     3   #14 v  #1
___ __ ___ _______  Table #5     3   #2  v  #11
___ __ ___ _______  Table #6     3   #4  v  #9
___ __ ___ _______  Table #7     3   #5  v  #8
___ __ ___ _______  Table #8     3   #3  v  #10

___ __ ___ _______  Table #1     4   #8  v  #3
___ __ ___ _______  Table #2     4   #14 v  #12
___ __ ___ _______  Table #3     4   #1  v  #13
___ __ ___ _______  Table #4     4   #9  v  #2
___ __ ___ _______  Table #5     4   #10 v  #16
___ __ ___ _______  Table #6     4   #11 v  #15
___ __ ___ _______  Table #7     4   #4  v  #7
___ __ ___ _______  Table #8     4   #5  v  #6

___ __ ___ _______  Table #1     5   #3  v  #6
___ __ ___ _______  Table #2     5   #13 v  #11
___ __ ___ _______  Table #3     5   #15 v  #9
___ __ ___ _______  Table #4     5   #2  v  #7
___ __ ___ _______  Table #5     5   #10 v  #14
___ __ ___ _______  Table #6     5   #16 v  #8
___ __ ___ _______  Table #7     5   #12 v  #1
___ __ ___ _______  Table #8     5   #4  v  #5

-