Алгоритм: выбор пар команд из набора игр

Question

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

Допустим, у меня есть набор команд 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 игр против других команд в пуле.Идеальное расписание должно гарантировать, что ни одна команда не проведет вторую игру, прежде чем каждая команда проведет хотя бы одну игру.Планировщик выбирает игры по одной за раз и назначает им дату.Таким образом, идея состоит в том, чтобы планировщик следил за играми, запланированными в этой «волне», и никогда не выбирал игру, которая помешала бы каждой команде играть ровно один раз в текущей волне.Планировщик также использует кучу других эвристик, так что я не могу явно упорядочить игры и привести их в порядок.

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

Answer 1

Это Задача максимального соответствия в теории графов.Есть несколько известных алгоритмов для ее решения.

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

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

Answer 2

Важно сделать некоторые предположения, чтобы уточнить, что представлено ниже.
Сначала , предположим, что мы говорим о 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

-