V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Alalajiyh
V2EX  ›  算法

有没有大佬帮我解答一个关于比赛分组的算法问题?

  •  
  •   Alalajiyh · 284 天前 · 1316 次点击
    这是一个创建于 284 天前的主题,其中的信息可能已经有所发展或是发生改变。

    背景:

    我们麻将群准备举办一个麻将比赛,总共有 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
    shinonome
        1
    shinonome  
       284 天前
    太复杂了吧,直接瑞士轮呗
    Alalajiyh
        2
    Alalajiyh  
    OP
       283 天前
    @shinonome 主办方要求要这么排,我只是想知道有没有什么好的方法来解决这个问题
    zhaozhou
        3
    zhaozhou  
       283 天前
    也许第一步可以按照下表来安排每日出战的 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 次。
    zhaozhou
        4
    zhaozhou  
       282 天前
    | |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 |
    zhaozhou
        5
    zhaozhou  
       282 天前
    | |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
    .
    .
    .
    zhaozhou
        6
    zhaozhou  
       282 天前
    每一行都往右移动一格到下一个非零队伍开始组一个四人局
    Alalajiyh
        7
    Alalajiyh  
    OP
       281 天前 via Android
    @zhaozhou 好像是我没看懂?这个方法是如何保证每个队伍与任意队伍相遇的次数相同的
    zhaozhou
        8
    zhaozhou  
       281 天前
    又推了几天,简单的平移确实不能保证两两只相遇四次
    aGVqaWFAbnVtYWcubmV0
    base64
    进一步交流?
    zhaozhou
        9
    zhaozhou  
       281 天前
    Alalajiyh
        10
    Alalajiyh  
    OP
       279 天前 via Android
    @zhaozhou 可以的,兄弟辛苦了
    Alalajiyh
        11
    Alalajiyh  
    OP
       279 天前 via Android
    @zhaozhou 这个是什么账号?还是邮箱吗?
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1679 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 21ms · UTC 16:46 · PVG 00:46 · LAX 08:46 · JFK 11:46
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.