Планирование конкурса

Question

Мне нужно составить расписание спортивного мероприятия.

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

Моя идея состояла в том, чтобы сгенерировать все возможные совпадения (для 30 команд: (30*29)/2 = 435 matches) и выбрать из этого списка 120 совпадений (8 совпадений для каждой команды: 8 * 30 / 2 = 120 matches).

Вот где мне трудно: как я могу выбрать эти 120 матчей? Я попробовал несколько простых решений (сначала сравним список, затем с последним и т. Д.), Но они не работают с 30 командами. Я также попытался сгенерировать все возможные комбинации совпадений и найти, какая из них работает, но с 30 командами это слишком много времени для расчета.

Существует ли существующий алгоритм, который я мог бы реализовать?

UPDATE

Мне нужно составить простой график без исключения. Каждая команда играет 8 матчей, и все. В конце дня не будет одного победителя.

У каждой команды будет свое расписание, и это расписание не изменится, когда они выиграют или проиграют. Планирование выполняется на весь день и является неизменным.

ОБНОВЛЕНИЕ 2

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

Итак, вот некоторые подробности:

Во время этого спортивного мероприятия есть 6 различных видов спорта (футбол, гандбол, баскетбол и т. Д.). Это означает, что есть 6 одновременных матчей. Новый раунд начинается каждые 15 минут.

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

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

Команда не может сыграть два матча подряд.

Answer 1

Вы можете посмотреть на некоторые уже известные подходы:

например. Швейцарская шахматная система

Edit:

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

Answer 2

Это довольно просто, просто объедините команду i с i-4, i-3, i-2, i-1, i+1, i+2, i+3, i+4. Это можно сделать, используя алгоритм ниже.

import java.util.*;

public class Test {

    public static void main(String[] args) {

        int TEAMS = 30, MATCHES = 8;
        int[] matchCount = new int[TEAMS];  // for a sanity check.
        List<Match> matches = new ArrayList<Match>();

        for (int team1 = 0; team1 < TEAMS; team1++)
            for (int team2 = team1 + 1; team2 <= team1 + MATCHES/2; team2++) {
                matches.add(new Match(team1, team2 % TEAMS));

                // Just for a sanity check:
                matchCount[team1]++;
                matchCount[team2 % TEAMS]++;
            }

        System.out.println(matches);

        // Sanity check:
        System.out.println(matches.size());
        System.out.println(Arrays.toString(matchCount));
    }

    static class Match {
        int team1, team2;
        public Match(int team1, int team2) {
            this.team1 = team1;
            this.team2 = team2;
        }
        public String toString() {
            return team1 + " vs " + team2;
        }
    }
}

Выход:

[0 vs 1, 0 vs 2, 0 vs 3, 0 vs 4, 1 vs 2, 1 vs 3, 1 vs 4, 1 vs 5, 2 vs 3, 2 vs 4, 2 vs 5, 2 vs 6, 3 vs 4, 3 vs 5, 3 vs 6, 3 vs 7, 4 vs 5, 4 vs 6, 4 vs 7, 4 vs 8, 5 vs 6, 5 vs 7, 5 vs 8, 5 vs 9, 6 vs 7, 6 vs 8, 6 vs 9, 6 vs 10, 7 vs 8, 7 vs 9, 7 vs 10, 7 vs 11, 8 vs 9, 8 vs 10, 8 vs 11, 8 vs 12, 9 vs 10, 9 vs 11, 9 vs 12, 9 vs 13, 10 vs 11, 10 vs 12, 10 vs 13, 10 vs 14, 11 vs 12, 11 vs 13, 11 vs 14, 11 vs 15, 12 vs 13, 12 vs 14, 12 vs 15, 12 vs 16, 13 vs 14, 13 vs 15, 13 vs 16, 13 vs 17, 14 vs 15, 14 vs 16, 14 vs 17, 14 vs 18, 15 vs 16, 15 vs 17, 15 vs 18, 15 vs 19, 16 vs 17, 16 vs 18, 16 vs 19, 16 vs 20, 17 vs 18, 17 vs 19, 17 vs 20, 17 vs 21, 18 vs 19, 18 vs 20, 18 vs 21, 18 vs 22, 19 vs 20, 19 vs 21, 19 vs 22, 19 vs 23, 20 vs 21, 20 vs 22, 20 vs 23, 20 vs 24, 21 vs 22, 21 vs 23, 21 vs 24, 21 vs 25, 22 vs 23, 22 vs 24, 22 vs 25, 22 vs 26, 23 vs 24, 23 vs 25, 23 vs 26, 23 vs 27, 24 vs 25, 24 vs 26, 24 vs 27, 24 vs 28, 25 vs 26, 25 vs 27, 25 vs 28, 25 vs 29, 26 vs 27, 26 vs 28, 26 vs 29, 26 vs 0, 27 vs 28, 27 vs 29, 27 vs 0, 27 vs 1, 28 vs 29, 28 vs 0, 28 vs 1, 28 vs 2, 29 vs 0, 29 vs 1, 29 vs 2, 29 vs 3]
120
[8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8]

Если вам нужна более рандомизированная установка, вы можете просто назначить случайное число от 1 до 30 для каждой команды.

---

Обновление Чтобы справиться с добавленными ограничениями: Пусть матч i будет спортивным i mod 6 .

Answer 3

Вы уверены, что не смогли получить 32 команды :-)?

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

С 30 командами, вы можете сделать так, чтобы 2 команды играли «дружно» и имели преимущество в первом раунде. Но организация становится намного сложнее.

Answer 4

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

1. Разделите 30 команд на 5 групп, каждая из 6 команд: A B C D E

2. Для первого периода играют группы A и B.

3. Затем C & D, E & A, B & C, D & E для следующих 4 пятнадцатиминутных сегментов.

Итак, в конце 5 * 15 минут: каждая команда играла дважды, по крайней мере, один перерыв между перерывами.

Есть 20 периодов, и все сыграли 8 раз.

Должно быть легко позволить команде в группе B, например, играть против 8 других команд из 17 других команд в группах A, B и C.

Например, играть команды А против соответствующих команд В, затем, команды В против соответствующих команд С, затем перевернуть списки, затем в группах, затем МОД 2, МОД 3 между группами и внутри групп.

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

Answer 5

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

Вот пример для 10 команд и 5 раундов, решение показано в виде массива, где, если значение расписания [i] [j] равно нулю, команды не играют вместе, а если это число, то это показывает, в каком раунде они играют вместе.

   1  2  3  4  5  6  7  8  9  10
1 [0, 5, 0, 4, 0, 3, 0, 2, 0, 1]
2 [5, 0, 4, 0, 3, 0, 2, 0, 1, 0]
3 [0, 4, 0, 3, 0, 2, 0, 1, 0, 5]
4 [4, 0, 3, 0, 2, 0, 1, 0, 5, 0]
5 [0, 3, 0, 2, 0, 1, 0, 5, 0, 4]
6 [3, 0, 2, 0, 1, 0, 5, 0, 4, 0]
7 [0, 2, 0, 1, 0, 5, 0, 4, 0, 3]
8 [2, 0, 1, 0, 5, 0, 4, 0, 3, 0]
9 [0, 1, 0, 5, 0, 4, 0, 3, 0, 2]
10[1, 0, 5, 0, 4, 0, 3, 0, 2, 0]

Таким образом, из этой таблицы в первом туре играют команды (1, 10), (2, 9), (3, 8), (4, 7), (5, 6), во втором раунде команды ( 1, 8), (2, 7), (3, 6) ... и т. Д.

Для создания этой таблицы алгоритм достаточно тривиален, вот код Python:

#!/bin/env python

def simpleNRooks(size, rounds, schedule):
    ''' Place n rooks on board so that they don't hit each other in each round,
        nor reuse the spots from previous rounds '''
    for i in range(size):
        for j in range(rounds):
            if size-j*2-i-1 < 0:
                schedule[i][2*size-j*2-i-1] = j + 1
            else:
                schedule[i][size-j*2-i-1] = j + 1

# parameters
teams = 10
matches = 5

# prepare the schedule, 0's designate free space  
schedule = [[0 for i in range(teams)] for j in range(teams)]

simpleNRooks(teams, matches, schedule)

print 'Final schedule'
for i in range(teams):
    print schedule[i]

Если вы хотите получить другую структуру данных (например, список пар по раундам), вы можете использовать тот же принцип, но изменить циклы.

Answer 6

Алгоритм Брокера может работать. Как ни странно, я не могу найти хорошее описание в сети, поэтому я попытаюсь объяснить систему.

По сути, каждая команда запрашивает у каждой команды счет за матч, и выбирается матч, набравший наибольшее количество очков. Это повторяется для каждой команды и матча. Полученное расписание сохраняется и рассчитывается общий балл. Затем с разными начальными точками (т. Е. Вы можете просто рандомизировать командный порядок), это делается снова, и, если общий балл выше, вместо этого выбирается этот график. Вы повторяете это до тех пор, пока не найдете график, приносящий высокий балл, или после заранее определенного количества попыток.

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

Оценка может пойти примерно так:

1. Если место для команды одинаковое: 100 очков (т.е. если для обоих = 200).
2. Для поездок между объектами оценка определяется для обеих команд в зависимости от длины, то есть A -> B и B -> A 50 очков (они рядом), A -> C и C -> A 30 очков (не так близко ) B -> C и C -> B 0 баллов (путешествия мы хотим сделать как можно меньше).
3. Если команда еще не занималась этим видом спорта: 100 очков.
4. Если команда занималась этим видом спорта один раз: 50 очков.

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

Answer 7

Я не знаю о существующей реализации, но вот возможное решение для вас:

Создайте три группы из 9 команд и объедините их в одну со всеми остальными, чтобы каждая играла против всех остальных. Каждая из 27 команд теперь играет в 8 игр.

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

Изменить некоторые игры каждой команды:

1-2 -> 1-10, 2-10 
3-4 -> 3-10, 4-10 
5-6 -> 5-10, 6-10 
7-8 -> 7-10, 8-10