1

我有特定数量的团队。我希望每支球队在 4 个指定时间与 4 个不同的对手进行 4 场比赛。

复杂性在于没有球队可以同时进行两场不同的比赛。例如，如果团队 1 像这样玩

team1 vs team2，team1 vs team3，team1 vs team4，team1 vs team5，

那么 team2 已经占用了第一个时间段，因此 team2 可以这样玩

（team2 vs team1），team2 vs team3，team2 vs team4, team2 vs team5

但是这里出现了问题，team3 将在第二个时间段与 team1 和 team2 一起比赛，这是无法做到的。

我不知道这个算法可以叫什么，但我正在寻找算法来实现它。

我搜索了循环赛和其他比赛，如匹配算法以及婚姻问题，但我认为我的问题不同。如果我错了，请纠正我。

任何帮助是极大的赞赏。

4

3 回答 3

3

我得出的结论是，如果团队数量是奇数，则没有解决方案。设 N 为团队的数量。我们总共需要N*4/2比赛，每支球队有四场比赛，但每场比赛需要两支球队。要N*2在四个时隙中进行匹配，我们必须平均N/2每个时隙的匹配。我们floor(N/2)一次最多可以进行比赛。如果 N 是奇数，floor(N/2) < N/2.

一个仅适用于甚至 N 的解决方案（如果存在）会有用吗？

于 2012-12-20T05:10:40.480 回答
3

该算法适用于任意数量的团队。
假设一场比赛有 6 支球队。
在此处输入图像描述

该解决方案基本上告诉您如何填充 6x6 矩阵，矩阵中的每个条目是行与列中的团队之间的匹配。
考虑算法中的一些规则
1. 从左到右和从上到下递增矩阵中的值。mat[0][0] = 1
2. 无论何时，然后在处i == j填充矩阵。基本上，在 3 处不会有 任何条目。每当矩阵中的条目达到 6 时，将其设为 1 我们将遵循此规则并开始按列填充矩阵。意味着首先我们将填充第 0 列的每一行，然后移动到第 1 列，依此类推。 - At ，应用规则 2。所以填写 - At ，填写下一个数字，即 2 ，类似地[n-1][j][i][j]i==j


[0][0]
[0][0]mat[n-1][0] = 0
mat[1][0][2][0], [3][0], [4][0]
- 现在第 1 列，从值 2 开始
- mat[1][0] = 2;
- 在mat[1][1]应用规则 2 时，填充当前列的最后一行，即mat[n-1][1] = 3

如果您希望每支球队只与其他球队打一场比赛，请使用下三角形。
如果你想让每支球队都和其他球队打 2 场比赛，一个主客场使用下三角和上三角。

希望你们理解我的解决方案。
干杯

于 2017-10-20T18:42:05.190 回答
1

一个简单的算法：

Round 1
1  2  3  4
8  7  6  5

然后旋转2-8个位置...

Round 2
1  8  2  3
7  6  5  4

Round 3
1  7  8  2
6  5  4  3

http://en.wikipedia.org/wiki/Round-robin_tournament#Scheduling_algorithm

（如果有奇数，可以通过添加一个虚拟配对来表示再见，但是正如 Patricia Shanahan 指出的那样，并非每支球队都会参加每一轮比赛。所以偶数球队和至少六支球队是需要满足要求。）

于 2012-12-20T05:16:07.323 回答