Я пытаюсь смоделировать проблему с Choco, чтобы получить комбинации возможных матчей в теннисе (или любом другом виде спорта).
Как я пытаюсь это сделать, у меня есть следующее:
// 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, которая могла бы помочь мне прояснить это.