我正在尝试用 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 ?
.........................
然后我只需确保每个球员的时间段中的值之和介于数字最低的球场乘以比赛持续时间和数字最高的球场乘以比赛持续时间之间。这是我想到的限制之一,所以每一行看起来像这样,例如,玩家 0 在 2 号球场的 3 和 4 时隙进行比赛:
0 0 0 2 2 0 0 0 0 0 0 0
我尝试定义约束nvalues
这应该强制执行不超过n
不同的值符合数组,但如果我像上面看到的那样使用它,问题只会呈现一种解决方案(什么?!)。
但是我需要定义更多约束,我什至不知道如何开始:
- 对于每一行,如果确实分配了球员所在的球场,则该球场必须具有连续的编号
- 对于每一行,我只能有 0 和法院编号 [1 - nCourts]
- 列应该配对以创建一对玩家之间的匹配。
- 同一场地在同一时段范围内不能配对多次(意味着同一场地内最多只能进行一场比赛)
这就是我能想到的所有限制,但我确信还有更多。
我希望有任何建议可以帮助我继续这样做,因为现在我感觉完全无能为力,而且网上关于 Choco 的信息几乎为零,可以帮助我解决这个问题。