当前位置：文江博客话题详情

我有一个算法问题，与尽可能公平地轮流安排团队有关

发布于 2024-08-12 00:10:26 字数 294 浏览 4 评论 0原文

我有一个学校项目，我必须想出一种算法来安排 4 支球队在一个球场上打排球，以便每支球队的比赛时间尽可能接近相同。

如果你总是让获胜者留下来并轮换失败者，那么排名第四的球队将永远不会参加比赛，而排名第一的球队永远会参加比赛。目标是让每个人玩相同的时间。

最简单的答案是球队 1 与球队 2 比赛，然后球队 3 与球队 4 比赛并不断切换，但球队 1 永远不会与球队 3 或 4 比赛，依此类推。

因此，我正在尝试找出一种算法，允许每个人在某个时刻与其他人比赛，而不会让一支球队比任何其他球队都坐得更多。

建议？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

花期渐远 2024-08-19 00:10:26

怎么样：制作一个大小为 NC2 的哈希表 H，在本例中为 6。它看起来像：

H[12] = 0
H[13] = 0
H[14] = 0
H[23] = 0
H[24] = 0
H[34] = 0

我假设生成密钥是微不足道的。

现在要安排一场比赛，请扫描哈希并选择具有最低值的密钥（一次通过）。由键表示的球队参加比赛，您将值加一。

编辑：
要添加另一个约束，即任何球队都不应等待太长时间，请创建另一个散列 W：

W[1] = 0
W[2] = 0
W[3] = 0
W[4] = 0

在每场比赛之后，将未参加比赛的球队的 W 值增加 1。

现在，当选择最少参加比赛的球队时，如果有多个球队组合的比赛分数较低，请从此哈希值中获取帮助来确定接下来必须参加哪支球队。

How about this: Make a hashtable H of size NC2, in this case, 6. It looks like:

H[12] = 0
H[13] = 0
H[14] = 0
H[23] = 0
H[24] = 0
H[34] = 0

I am assuming it would be trivial to generate the keys.

Now to schedule a game, scan through the hash and pick the key with the lowest value (one pass). The teams denoted by the key play the game and you increment the value by one.

EDIT:
To add another constraint that no team should wait too long, make another hash W:

W[1] = 0
W[2] = 0
W[3] = 0
W[4] = 0

After every game increment the W value for the team that did not play, by one.

Now when picking up the least played team if there are more than one team combo with low play score, take help from this hash to determine which team must play next.

回复收藏 0 原文

半步萧音过轻尘 2024-08-19 00:10:26

好吧，你应该玩 1-2 3-4、1-3 2-4、1-4 2-3，然后重新开始。

回复收藏 0 原文

成熟的代价 2024-08-19 00:10:26

如果有 N 支球队，并且您希望所有球队都玩一次，那么您需要运行“N 选择 2”= N*(N-1)/2 场比赛。

要枚举它们，只需将球队放入有序列表中，让第一支球队与其他球队比赛，然后让第二支球队与列表中位于其下方的所有球队比赛，依此类推。如果您想分散比赛，以便各队在比赛之间有相似的休息时间，请参阅高德纳。

回复收藏 0 原文

月棠 2024-08-19 00:10:26

查看关于循环调度的维基百科条目。

回复收藏 0 原文

像极了他 2024-08-19 00:10:26

假装这是一个小型体育联盟，并重复“季节”......
（在欧洲的大多数体育联赛中，所有球队在一个赛季中都会与所有其他球队进行几次比赛）

回复收藏 0 原文

三寸金莲 2024-08-19 00:10:26

团体冠军赛安排的平衡循环算法的要求可以在这里找到：
星座算法 - 平衡循环
算法的要求可以通过以下四个约束来定义：

1) 全部与全部
每支球队必须与分区/联赛中的其他球队只交手一次。
如果该分区由n支球队组成，则冠军将在n-1轮中进行。

2) 主/客场交替规则
如果可能的话，应保留分区联赛中每支球队主客场交替的顺序。对于分区联赛中的任何一支球队，在连续比赛顺序中最多出现一次HAHA，出现节奏的BREAK，即连续两轮比赛中出现HH或AA比赛。

3）最后一个槽位号的规则
槽位编号最高的团队必须始终位于网格的最后一行。对于随后的每次迭代，网格的最高槽数交替左右位置；左栏（主场）和右栏（客场）。
用于制定联赛赛程的系统是“逆时针循环”。在冠军赛一轮的比赛结构中，一个赛区的球队数量为偶数。如果一个赛区中有奇数支球队，则将在网格/环的最高槽位中插入一支 BYE/Dummy 球队。

4) HH 和 AA 非终结符且非首字母
对于该分区中的任何球队，Cadence HH 或 AA 不得在比赛开始或结束时发生。