Моделирование теннисных матчей с Choco (CSP)

Question

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

То, как я пытаюсь это сделать, у меня следующее:

// Set of timeslots when the event is held (i.e. 10am-10pm)
int nTimeslots = 12;

// Courts available: court #1, #2 and #3
int nCourts = 3;

String[] players = { "Novak", "Andy", "Roger", "Stan", "Rafel", "Kei", "Tomas", "David" };
int nPlayers = players.length;

// Timeslots when each player cannot play for whatever reason
int[][] unavailability = {
    { 0, 1, 5 },
    { 8, 10, 11 },
    { 1, 2, 11 },
    { 0, 1 },
    { 2, 3, 4, 5, 6 },
    { 3, 4, 9, 10, 11 },
    { 4, 5 },
    { 2, 3 }
};

// Number of timeslots each match will occupy
int matchDuration = 2;

// This will hold the final combinations
// rows -> players, columns -> timeslots, matches[i][j] -> court where the player plays at that timeslot (0 means the player does not play at that time)
IntVar[][] matches;

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

Потратив много времени на это, я не смог продвинуться дальше, чем это:

for (int player = 0; player < nPlayers; player++) {
    for (int timeslot = 0; timeslot < nTimeslots; timeslot++) {
        for (int playerUnavailbleTimeslot : unavailability[player]) {
            if (playerUnavailbleTimeslot != timeslot) {
                solver.post(IntConstraintFactory.arithm(matches[player][playerUnavailbleTimeslot], ">=", 0));
            } else {
                for (int i = 0; i < matchDuration; i++)
                    if (playerUnavailbleTimeslot - i >= 0)
                        solver.post(IntConstraintFactory.arithm(matches[player][playerUnavailbleTimeslot - i], "=", 0));
            }
        }
    }
}

IntVar matchesSum = VariableFactory.enumerated("Matches sum", 1 * matchDuration, nCourts * matchDuration, solver);
for (int player = 0; player < nPlayers; player++) {
    solver.post(IntConstraintFactory.sum(matches[player], matchesSum));
    //solver.post(IntConstraintFactory.nvalues(matches[player], VariableFactory.fixed(2, solver)));
}

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

0 0 ? ? ? 0 ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? 0 0 0 0 ?
.........................

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

0 0 0 2 2 0 0 0 0 0 0 0 

Я пытался определить ограничение nvalues предполагается, что не более n различные значения соответствуют массиву, но если я использую его так, как вы можете видеть выше, проблема просто отдает одно решение (что?!).

Однако мне нужно определить больше ограничений, которые я даже не знаю, как начать:

• Для каждой строки площадка, на которой играет игрок, должна иметь последовательные номера, если действительно эта площадка назначена
• Для каждой строки я могу иметь только 0 и номер суда [1 - nCourts]
• Столбцы должны спариться, чтобы создать совпадения между парой игроков.
• Один и тот же корт не может быть спарен более одного раза для одного и того же диапазона временного интервала (то есть в суде одновременно может проходить не более одного матча)

Это все, что я могу представить с точки зрения ограничений, но я уверен, что есть и другие.

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

Answer 1

Я бы начал с записи в математике, что вы хотите.

Не уверен, что это полезно, но вот моя реализация, решающая ее как задачу математического программирования. Он не использует ограничение программирования, но все может выглядеть так же, как в Choco:

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

Результаты выглядят так:

Числа в таблице являются номерами судов (-1 означает, что не допускается). В этом расписании все играют три раза.