有没有大佬帮我解答一个关于比赛分组的算法问题？ - V2EX
Alalajiyh
·
2024-01-26
·
via 算法
这是一个创建于 870 天前的主题，其中的信息可能已经有所发展或是发生改变。
背景：
我们麻将群准备举办一个麻将比赛，总共有 10 个队伍参赛，假设这 10 个队伍分别为 A,B,C,D,E,F,G,H,I,J ；
要求：
1 ，总共安排 30 场对战，每天两场，总共 15 天，每个队伍出战 12 次；每个队伍遇到其他每个队伍的次数相同，即任意两个队伍之间的相遇 4 次。
2 ，每天两场比赛同时进行，8 个队伍参赛，两个队伍轮空。每个队伍每天只能参加一场。
问题：如何安排每天的赛程？
我个人上班摸鱼的时候想了一些办法，虽然找到满足要求的结果了，但是觉得并不是最优解，所以来虚心请教下。
已知所有相遇可能性为 C10,2 = 45 ，每场对战的不同相遇数为 C4,2 = 6;
我使用的方法是，最后的结果使用一个二维数组来存放，每个元素代表每天的两场对战。例如：[[ABCD,EFGH],[ABCD,EFGH]...]。
每次挑选两个相遇来组合成一次对战。要求这两次相遇没有同一个队伍，并且如果本场对战是当天的第二场，还要先排除第一场已经参赛的队伍。先将总共 30*6 = 180 个相遇放到待选池中，每次从池中选择一个相遇时，优先选择最终结果中已选择的相遇次数最少的相遇来组成一场对战。
然后我用 js 写了个实现，最后还是使用不同的待选池序列尝试了一千多万次才找出满足条件的结果。想问问有没有更好的办法
相遇 队伍 对战 待选池11 条回复 • 2024-01-31 09:34:46 +08:00
 |
|
3
zhaozhou 2024 年 1 月 27 日
也许第一步可以按照下表来安排每日出战的 8 支队伍:
| | A | B | C | D | E | F | G | H | I | J | SUM |
|----- |--- |--- |--- |--- |--- |--- |--- |--- |--- |--- |----- |
| D1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 8 |
| D2 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 8 |
| D3 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 8 |
| D2 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 8 |
| D5 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 8 |
| D6 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 8 |
| D7 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 8 |
| D8 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 8 |
| D9 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 8 |
| D10 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 8 |
| D11 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 8 |
| D12 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 8 |
| D13 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 8 |
| D14 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 8 |
| D15 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 8 | 然后再保证 12 天的组合中同一支队伍出现不超过 4 次。 |
|
|
4
zhaozhou 2024 年 1 月 28 日
| |A | B | C | D | E | F | G | H | I | J |SUM|
|----- |--- |--- |--- |--- |--- |--- |--- |--- |--- |--- |-----|
| D1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 8 |
| D2 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 8 |
| D3 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 8 |
| D4 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 8 |
| D5 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 8 |
| D6 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 8 |
| D7 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 8 |
| D8 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 8 |
| D9 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 8 |
| D10 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 8 |
| D11 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 8 |
| D12 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 8 |
| D13 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 8 |
| D14 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 8 |
| D15 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 8 |
|
|
|
5
zhaozhou 2024 年 1 月 28 日
| |A | B | C | D | E | F | G | H | I | J |
|----- |--- |--- |--- |--- |--- |--- |--- |--- |--- |--- |
| D1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | => BCDE, FGIJ
| D2 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | => CDEF, GHJB
| D3 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | => DEFG, HJCD
| D4 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | => EFGH, JACD
| D5 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | => FGHI, JADE
.
.
.
|
|
|
6
zhaozhou 2024 年 1 月 28 日
每一行都往右移动一格到下一个非零队伍开始组一个四人局
|
|
|
8
zhaozhou 2024 年 1 月 29 日
又推了几天，简单的平移确实不能保证两两只相遇四次
aGVqaWFAbnVtYWcubmV0
base64
进一步交流？
|
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。
