Дизайн турниров динамических команд

Question

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

Тип расписания, которое я хотел бы составить, должен соответствовать Balanced-Tournament Design. Это означает:

• каждая команда играет в каждой локации
  • Иногда места не всегда равны. Например, центральный корт на Уимблдоне. Сбалансированный турнир должен позволить каждому играть в любом месте достаточное количество раз.
• каждая команда играет любую другую команду
  • Главный продукт большинства турниров с круговым турниром
• каждая команда "дома" и "в гостях" и равное количество раз
  • В командных видах спорта часто нужна команда дома и в гостях. Например, в бейсболе команда хозяев получает последние биты в каждом иннинге. Это может быть преимуществом, поэтому сбалансированный турнир должен позволять каждой команде иметь такое же количество раз.

Я имел большой успех, используя Ортогональные Латинские Квадраты и Факторизованный Сбалансированный Дизайн Турниров, и нашел достойный способ для создания таких турниров.

Тем не менее, я хотел бы сделать что-то немного другое:

• Игроки сгруппированы (например, основаны на навыке или позиции). Команде нужен один игрок из каждой группы (например, один игрок каждой позиции или уровня квалификации)
• Каждый раунд команды и матчи воссоздаются так, что
  • Количество раз, когда два человека играют друг с другом, сведено к минимуму
  • Количество раз, когда два человека играют друг против друга, сведено к минимуму

Это похоже на турниры Individual-Pairs, но в моей задаче в командах может быть более 2 игроков, и игроки сгруппированы так, что каждой команде требуется игрок из каждой группы. Изменяя команды в каждом раунде, один игрок может "выиграть" турнир, выиграв больше игр, чем любой другой игрок.

Более формально это можно описать следующим образом (я открыт для изменения этой записи, если у кого-то есть лучший способ представить это):

• Есть p игроки, разделенные на g группы, каждая из которых состоит из t=p/g игроки.
• Группы помечены Gi={Pi1, Pi2, ... Pit} где
  • i это номер группы (0<=i<=g)
• Игроки помечены Pij где
  • i группа, к которой принадлежит игрок (0<=i<=g)
  • j номер игрока в группе i (0<=j<=t)
• Расписание будет содержать r=t-1 туры
• Каждый раунд t команды и m=t/2 совпадения должны быть созданы
• Команды помечены Tij={P1a, P2b, ... Pgc} где
  • i это раунд для этой команды (0<=i<=r)
  • j номер команды в раунде i(0<=j<=t)
  • Каждая команда состоит из ровно одного игрока из каждой группы
• Спички помечены Mij={Tia, Tib} где
  • i раунд этот матч для (0<=i<=r)
  • j номер матча в раунде i (0<=j<=m)
• Минимизируйте следующее
  • Сколько раз два игрока в одной группе играют вместе
    • В команде может быть только один игрок из каждой группы, поэтому это должно быть 0
  • Сколько раз два игрока в разных группах играют вместе
    • В течение турнира два игрока не должны входить в одну команду более одного раза.
  • Сколько раз два игрока в одной группе играют друг против друга
    • Должен быть точно один, если r=t-1
  • Количество раз, когда два игрока в разных группах играют друг против друга
    • По моему опыту, это может быть в два раза

Если это окажется слишком сложным, я более чем готов обсудить более конкретный случай, когда:

• каждая команда состоит из 4 игроков (g=4)
• количество команд "мало", от 5 до 12 (от 20 до 48 игроков)
• количество раундов не должно быть t-1,
  
  • Если это t-1тогда игрок может (и должен) играть против всех других игроков той же группы ровно один раз. Это может быть невозможно создать, поэтому я бы принял решение, где r максимизируется таким образом, что игрок никогда не играет против другого игрока в той же группе более одного раза (т.е. некоторые игроки в группе могут никогда не играть друг против друга).

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

Спасибо!

Answer 1

Я только что натолкнулся на ваш пост и подумал, что передам вам URL. Это лучший сайт, который я знаю за помощь с графиками. Я надеюсь, что это поможет вам так же, как и мне!

Раунд Расписание Робин Турнир