问调度:平衡的主场/客场循环赛算法
EN

Software Engineering用户

提问于 2017-03-10 01:49:19

回答 1查看 4.5K关注 0票数 6

我试图实现一个循环算法的体育调度，也保证公平或平衡的主场/客场轮换。

我的算法基于循环调度算法：

def round_robin(teams, rounds):
    # bye
    if len(teams) % 2:
        teams.append(None)

    schedule = []
    for turn in range(rounds):
        pairings = []
        for i in range(len(teams) / 2):
            pairings.append((teams[i], teams[len(teams) - i - 1]))
        teams.insert(1, teams.pop())
        schedule.append(pairings)

    return schedule

然而，该算法不解决H/A平衡问题。我正试图达到这两个目标：

H/A轮换:每队应每隔一轮进行一次主场比赛和客场比赛，即在一场有5轮的比赛中，一支球队应该有以下轮换：H-A-H-A-H。
H/A游戏数:主场比赛和客场比赛的次数应该相同(如果总数为奇数，则由一场比赛抵消)，所以每支球队10场比赛应该有5场主场比赛和5场客场比赛。

以前的算法不能满足上述任何一个目标：

它不能替代H/A游戏。例如，第一队只有主场比赛，而其他队只有主场比赛，直到他们被轮换到列表的末尾，然后只有客场比赛(相反:客场比赛一直到开始，然后只有主场比赛)。以下是我的意思(1)。
它确实保证了H/A游戏数量的均衡，但只有当回合数是游戏数(或游戏数减去1)的倍数时，否则我们会得到太多的主场或客场游戏(实际游戏数和下一次游戏数之间的差额)。

(1)

[(1, 8), (2, 7), (3, 6), (4, 5)]
[(1, 7), (8, 6), (2, 5), (3, 4)]
[(1, 6), (7, 5), (8, 4), (2, 3)]
[(1, 5), (6, 4), (7, 3), (8, 2)]
[(1, 4), (5, 3), (6, 2), (7, 8)]
[(1, 3), (4, 2), (5, 8), (6, 7)]
[(1, 2), (3, 8), (4, 7), (5, 6)]

为了更接近平衡的旋转，我做了几次直接的修改：

def round_robin(teams, rounds):
    # bye
    if len(teams) % 2:
        teams.append(None)

    schedule = []
    for turn in range(rounds):
        pairings = []
        for i in range(len(teams) / 2):
            pairing = (teams[i], teams[len(teams) - i - 1])
            # alternate first team
            if i == 0 and turn % 2:
                pairing = pairing[::-1]
            # alternate based on the team's previous round appearance
            if schedule and None not in pairing:
                previous_round = list(sum(schedule[-1], ()))
                for team in pairing:
                    if team in previous_round and pairing[previous_round.index(team) % 2] == team:
                        pairing = pairing[::-1]
            pairings.append(pairing)
        teams.insert(1, teams.pop())
        schedule.append(pairings)

    return schedule

当然，这不是一个聪明的算法。这是有帮助的，但并不能完全满足这两个目标。

我一直试图找到一种解决这个问题的算法，但我没有找到一个算法，这是一个令人惊讶的问题，因为比赛调度是一个常见的问题。

我有使用约束编程来解决这个问题的方法，但我不完全确定这将是最终的解决方案，也许这有点过分，另一种最经典的方法更好。此外，将问题描述为约束编程问题(或CSP)可能是一个相当大的挑战，至少对我来说是这样。

任何形式的帮助，建议，洞察力都将受到欢迎。

algorithms

python

scheduling

combinatorics

回答 1

Software Engineering用户

发布于 2019-02-13 15:28:50

我最终会有这样的结果。德福可能需要一些清理和去复制。

import collections
teams = [1, 2, 3, 4, 5, 6, 7, 8, 9]
rounds = 8
schedule = []

teams.insert(0, None)
d = collections.deque(teams)
dl = list(collections.deque(d))
pl = list(zip(dl[::2], dl[1::2]))
schedule.append(pl)

for turn in range(rounds):
    d.rotate(1)
    # Swap bye week back to top
    d[1] = d[0]
    d[0] = None
    dl = list(collections.deque(d))
    pl = list(zip(dl[::2], dl[1::2]))

    schedule.append(pl)

print(schedule)

产出似乎是正常的：

[(None, 1), (2, 3), (4, 5), (6, 7), (8, 9)], 
[(None, 9), (1, 2), (3, 4), (5, 6), (7, 8)], 
[(None, 8), (9, 1), (2, 3), (4, 5), (6, 7)], 
[(None, 7), (8, 9), (1, 2), (3, 4), (5, 6)], 
[(None, 6), (7, 8), (9, 1), (2, 3), (4, 5)], 
[(None, 5), (6, 7), (8, 9), (1, 2), (3, 4)], 
[(None, 4), (5, 6), (7, 8), (9, 1), (2, 3)], 
[(None, 3), (4, 5), (6, 7), (8, 9), (1, 2)], 
[(None, 2), (3, 4), (5, 6), (7, 8), (9, 1)],