选择每对球队参加比赛，每场比赛前都有最大曝光率

问题描述 投票：0回答：1

我正在编写运动时间表生成器。给定T个团队（偶数），每回合G个游戏和R个回合，我想生成一个符合条件的时间表：

  1. 所有团队本轮比赛中玩相同数量的游戏。
  2. 团队组合在重复之前已完全用尽。

我有一种算法在大多数情况下都有效，但并非总是如此。在该问题的末尾有详细说明。 我该如何解决（或替换）此算法可对所有合理的输入都有效地起作用？

此问题类似于Sorting pairs of teams with non-repeating | Round-robin tournament和Algorithm: Selecting pairs of teams from a set of games，但有不同的要求。

例如，假设有T = 4个团队。这给了我们6种可能的游戏：

(T0,T1)  (T0,T2)  (T0,T3)  (T1,T2)  (T1,T3)  (T2,T3)

如果每轮有G = 4场比赛，那么第一轮必须not是这组比赛...

(T0,T1)  (T0,T2)  (T0,T3)  (T1,T2)

…因为T0可以玩3次，但是T3只能玩一次（违反了要求＃1）。相反，第一轮可能看起来像这样，每个团队都可以玩两场比赛：

(T0,T1)  (T2,T3)  (T0,T2)  (T1,T3)

如果在第二轮中重复相同的游戏，则将永远不会发生两个游戏(T1,T2)和(T0,T3)（违反了要求＃2）。因此，我们希望在选择新游戏之前确保将它们包含在第二轮比赛中。 T = 4，G = 4，R = 5的有效时间表是：

(T0,T1)  (T2,T3)  (T0,T2)  (T1,T3)
(T0,T3)  (T1,T2)  (T0,T1)  (T2,T3)
(T0,T2)  (T1,T3)  (T0,T3)  (T1,T2)
(T0,T1)  (T2,T3)  (T0,T2)  (T1,T3)
(T0,T3)  (T1,T2)  (T0,T1)  (T2,T3)

如所见，对于较大的值 R 可以接受的一轮游戏最终可以重复进行。

我拥有的算法如下：

  • 计算团队的所有唯一成对组合（可能的游戏）。将此列表另存为currentPool。
  • 创建一个空列表，命名为otherPool。
  • 每回合，G次执行以下操作：
    • 将这轮比赛中每支球队出现的次数加在一起，以最低的总和在currentPool中找到游戏。
    • 将游戏添加到该回合中。
    • 将游戏从currentPool移至otherPool。
      • 如果currentPool为空，则交换currentPool和otherPool。

对于T，G和R的许多合理值，此算法有效。但是，有些组合会失败。例如，在T = 6，G = 3，R = 5的情况下，它将生成此计划：

(T0,T1)  (T2,T3)  (T4,T5)
(T0,T2)  (T1,T3)  (T0,T4)
(T0,T3)  (T1,T2)  (T0,T5)
(T1,T4)  (T2,T5)  (T3,T4)
(T1,T5)  (T2,T4)  (T3,T5)

第一轮是正确的，但在第二轮中，T0出战两次，T5从未出战。问题很容易发现-在第2轮中选择(T0,T2)和(T1,T3)后，唯一可能满足要求＃1的游戏将是(T4,T5)，但是该游戏已经在第一轮中按要求使用了＃在全部15个独特的游戏用完之前，不能再使用2个。该算法开始陷入僵局，无法回溯。

最后，为了完整起见，这是所描述算法的JavaScript版本。这是成功运行的示例输出：

let schedule = singleFieldSchedule({
    teams            : 8,
    maxGamesPerRound : 12,
    rounds           : 8
})
console.log(schedule.map(round => round.map(game => `(T${game[0]},T${game[1]})`).join('  ')).join('\n') )

(T0,T1) (T2,T3) (T4,T5) (T6,T7) (T0,T2) (T1,T3) (T4,T6) (T5,T7) (T0,T3) (T1,T2) (T4,T7) (T5,T6)
(T0,T4) (T1,T5) (T2,T6) (T3,T7) (T0,T5) (T1,T4) (T2,T7) (T3,T6) (T0,T6) (T1,T7) (T2,T4) (T3,T5)
(T0,T7) (T1,T6) (T2,T5) (T3,T4) (T0,T1) (T2,T3) (T4,T5) (T6,T7) (T0,T2) (T1,T3) (T4,T6) (T5,T7)
(T0,T3) (T1,T2) (T4,T7) (T5,T6) (T0,T4) (T1,T5) (T2,T6) (T3,T7) (T0,T5) (T1,T4) (T2,T7) (T3,T6)
(T0,T6) (T1,T7) (T2,T4) (T3,T5) (T0,T7) (T1,T6) (T2,T5) (T3,T4) (T0,T1) (T2,T3) (T4,T5) (T6,T7)
(T0,T2) (T1,T3) (T4,T6) (T5,T7) (T0,T3) (T1,T2) (T4,T7) (T5,T6) (T0,T4) (T1,T5) (T2,T6) (T3,T7)
(T0,T5) (T1,T4) (T2,T7) (T3,T6) (T0,T6) (T1,T7) (T2,T4) (T3,T5) (T0,T7) (T1,T6) (T2,T5) (T3,T4)
(T0,T1) (T2,T3) (T4,T5) (T6,T7) (T0,T2) (T1,T3) (T4,T6) (T5,T7) (T0,T3) (T1,T2) (T4,T7) (T5,T6)

function singleFieldSchedule({teams=8, maxGamesPerRound=12, rounds=8}={}) {
    const uniquePairs = a => a.reduce((res,o1,i,a) => res.concat(a.slice(i+1).map(o2 => [o1,o2])), [])
    const teamNames = Array.from(Array(teams).keys())
    const fullExposure = uniquePairs(teamNames)
    const zeroTeamCounts = teamNames.map(n => [n,0])

    // Calculate how many games can be played by each team while keeping things fair
    const gamesPerTeam = Math.floor(maxGamesPerRound / teams * 2)
    const gamesPerRound = gamesPerTeam * teams/2    

    const schedule = []

    const pools = [fullExposure, []]
    let poolIndex = 0
    for (let r=0; r<rounds; ++r) {
        const round = []
        schedule.push(round)
        const gamesPerTeam = new Map(zeroTeamCounts)
        for (let g=0; g<gamesPerRound; ++g) {
            let pool = pools[poolIndex]
            if (!pool.length) pool = pools[poolIndex=((poolIndex+1)%2)]

            // Find the game whose teams have been seen the least
            let bestGameSum = Infinity
            let bestGameIndex
            for (i=0; i<pool.length; ++i) {
                const game = pool[i];
                // We square the times seen to favor a game where each team has been seen once
                // over a game where one team has been seen twice and the other team has never been seen
                const gameSum = gamesPerTeam.get(game[0])**2 + gamesPerTeam.get(game[1])**2
                if (gameSum < bestGameSum) {
                    bestGameSum = gameSum
                    bestGameIndex = i
                }
            }
            let bestGame = pool.splice(bestGameIndex, 1)[0]
            round.push(bestGame)
            gamesPerTeam.set(bestGame[0], gamesPerTeam.get(bestGame[0])+1);
            gamesPerTeam.set(bestGame[1], gamesPerTeam.get(bestGame[1])+1);

            // Put this game into the 'other' pool, to be used once this pool of games is used up
            pools[(poolIndex+1) % 2].push(bestGame)
        }

        // Check to see if any team got screwed this round
        const shortedTeams = teamNames.filter(t => gamesPerTeam.get(t)<gamesPerTeam)
        shortedTeams.forEach( t => {
            const ct = gamesPerTeam.get(t)
            console.warn(`Team ${t} only got to play ${ct}/${gamesPerTeam} games in round #${r}`)
        })
    }

    return schedule
}
algorithm combinatorics schedule
1个回答
0
投票

我在理论上没有完美的解决方案，但是我有多项式时间方法应该会更好。

其核心是最大匹配的Blossom Algorithm。在每个回合中，将其与代表尚未玩过的游戏的边缘一起使用。这将更有可能找到可能因当前算法而失败的简单案例的有效解决方案。特别是，您已确保团队不能一轮进行2场比赛，并且尽可能多地使用未使用的游戏。

但是我们可以通过使用a variation to find maximal weight matchings来对此进行改进。如果将每个边的权重设为G^i，其中G是打的比赛数，i是自上一场比赛以来的回合数，则团队不能一轮进行2场比赛，并且我们会玩尽可能多的旧游戏。

此算法可保证您的第一个条件，并真诚地努力到第二个条件都做好。但这并不能保证第二。 （但是，如果您确实有早期重复的话，它们会很好地散开。）

如果您有很多发子弹，则可以根据重量条件进行测试，以确保每轮平均使用正确的次数。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.