Алгоритм порядка соответствия

Question

Фон

Спортивный клуб, в котором я участвую, попросил у меня помощи с ИТ-поддержкой для предстоящего соревнования.

Соревнование состоит из команд из которыхточное число не обязательно известно до дня соревнования.Отсюда необходимость в программной помощи.

Все команды встретятся с каждой другой командой в ряде матчей .Таким образом, количество матчей составляет N за 2 (все комбинации по 2), где N - количество команд.

У нас есть неизвестное количество доступных кортов дляиграть матчи дальше.Вероятно, это число будет 1 или, возможно, 2, но я бы хотел общее решение.

Соревнование будет проходить в ходах .На каждом ходу будет сыгран один матч на каждом корте .

Например, если есть два корта и пять команд (A, B, C, D, E) схема поворота может выглядеть следующим образом:

Turn      Court 1     Court 2
--------------------------------
 1        A vs B      C vs D
 2        A vs C      D vs E
 3        A vs D      B vs E
 4        B vs D      C vs E
 5        A vs E      B vs C

Проблема

Моя задача, таким образом, состоит в том, чтобы найти алгоритм для генерации набора поворотов, который подчиняется следующим простым правилам:

1. Все команды должны встречаться со всеми остальными командами ровно один раз во время соревнования.
2. Команда не может сыграть два матча в один ход (то есть она не может играть одновременно на корте 1 и 2).)
3. Ходы, в которых играет конкретная команда, должны быть распределены по всему соревнованию.

Подробное правило 3

Правила 1 и 2 довольно просты,и у меня уже есть решение для этого.Это правило 3, которое вызывает у меня проблемы.Я попытаюсь показать, что это значит:

Допустим, у меня 5 команд (как указано выше), но только 1 корт.Есть 10 матчей за 10 ходов.Один из возможных вариантов:

Turn   Court 1
 1     A vs B
 2     A vs C
 3     A vs D
 4     A vs E
 5       .
 .       .
 .       .
 10      .

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

Идеи?

Answer 1

Как насчет простого жадного решения, когда у вас есть значение усталости для каждой команды.

Сначала усталость для всех команд устанавливается равной 0. В ходе хода nr 1 проведите начальный матч для разных кортов и установите значение усталости для этих команд, равное текущему ходу (сначала 1 соответствовать).

В свою очередь, номер 2 выбирает команды с наименьшей усталостью (сохраняя команды, например, в очереди с приоритетами), которые не играли друг против друга, и сопоставляет их. Установите значение усталости на текущее значение поворотов.

На вашем примере вы получите:

Turn     Court 1   Team:fatigue
0           -      A:0 B:0 C:0 D:0 E:0
1        A vs B    C:0 D:0 E:0 A:1 B:1
2        C vs D    E:0 A:1 B:1 C:2 D:2
3        E vs A    B:1 C:2 D:2 E:3 A:3
4        B vs C    D:2 E:3 A:3 B:4 C:4
5        D vs E    A:3 B:4 C:4 D:5 E:5
6        A vs C    B:4 D:5 E:5 A:6 C:6 // Dont match A with B since they already played, jump to team C
.

Сохранение свежих команд всегда на старте. Поскольку у вас, вероятно, не будет более 100 команд, этого должно быть достаточно.

Answer 2

Ленивый подход состоит в том, чтобы использовать ваше текущее решение, а затем рандомизировать временные интервалы (строки в презентации) X раз, отслеживая при этом некоторый критерий утомляемости и сохраняя лучшее решение, найденное до сих пор. С другими решениями вам нужно быть осторожным, чтобы вы могли полностью использовать все суды.