Существует ли эффективный алгоритм для создания этого типа расписания?

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

Проблема имеет два ограничения:

  1. Каждая пара команд должна сыграть одинаковое количество домашних и выездных игр друг против друга. Например, если команда A и команда B играют в 4 игры, то 2 должны быть проведены A, а 2 - B. Предположим, что каждая пара команд играет четное количество игр друг против друга.
  2. Ни одна команда не должна иметь более трех последовательных домашних игр или трех последовательных выездных игр в любой точке графика.

Я пытался использовать грубую силу в R для решения этой проблемы, но я не могу получить ни один из своих блоков кода для своевременного решения проблемы. Есть ли у кого-нибудь совет о том, как алгоритмически справляться с одним (или обоими) из вышеуказанных ограничений?

Источник

1 ответ

Вам нужно больше исследовать простое планирование. Есть много ссылок на эти вещи. Вот основы для вашего приложения. Предположим, лига состоит из 6 команд; процесс одинаков для любого числа.

Матч 1: Просто запишите номера команд по порядку, в парах, в ринге. Свести он кольцо в две строки. Матчи верхние (домашние) и нижние (выездные).

1 2 3
6 5 4

Матчи 2-5: Команда 1 остается на месте; остальные вращаются вокруг кольца.

1 6 2
5 4 3

1 5 6
4 3 2

1 4 5
3 2 6

1 3 4
2 6 5

Это один полный цикл. Чтобы уравновесить расписание на выезде, просто поменяйте местами матчи в каждом другом матче:

1 2 3    5 4 3    1 5 6    3 2 6    1 3 4
6 5 4    1 6 2    4 3 2    1 4 5    2 6 5

Там твой первый полный раунд. Просто скопируйте это, снова переключая домашние светильники в чередующихся раундах. Таким образом, второй тур будет:

6 5 4    1 6 2    4 3 2    1 4 5    2 6 5
1 2 3    5 4 3    1 5 6    3 2 6    1 3 4

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

Если у вас нечетное количество команд, просто объявите одно из чисел как "пока" в расписании. Мне проще всего следовать, если я использую невращающуюся команду - команду 1 в этом примере.

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

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

Существует также небольшая проблема, заключающаяся в том, что вы не можете гарантировать, что ваш существующий график будет соответствовать заданным требованиям. Например, учитывая 8 команд команды в следующем порядке:

1 2 3 4
5 6 7 8

1 2 5 6
3 4 7 8

1 3 5 7
2 4 6 8

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

Источник
Другие вопросы по тегам