Programação: algoritmo de torneio round-robin balanceado para casa / longe

Question

Programação: algoritmo de torneio round-robin balanceado para casa / longe

#1 resposta do (1 votos)

5

Estou tentando obter um algoritmo round-robin para agendamento de esportes que também garanta uma rotação casa / distância justa ou equilibrada.

Eu baseei meu algoritmo no algoritmo de agendamento round-robin :

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

No entanto, esse algoritmo não endereça o saldo H / A. Estou tentando satisfazer esses dois objetivos:

Rotação de H / A: cada equipe deve jogar um jogo em casa e um fora de casa a cada rodada, ou seja, em um torneio com 5 rodadas, uma determinada equipe deve ter a seguinte rotação: H-A-H-A-H .
Número de jogos H / A: o número de jogos em casa e jogos fora deve ser o mesmo (ou compensado por um, se o total for ímpar), então um torneio com 10 jogos por equipe deve ter 5 em casa jogos e 5 jogos fora de casa para cada equipe.

O algoritmo anterior não satisfaz nenhum desses objetivos:

Não alterna jogos H / A. Por exemplo, o primeiro time só tem jogos em casa, e os outros times recebem jogos em casa até que sejam rodados para o final da lista e apenas para fora dos jogos (e o oposto: jogos fora até chegar ao início, e só recebem jogos em casa) ). Veja o que quero dizer abaixo (1).
Ele garante um número equilibrado de jogos de A / D, mas somente se o número de rodadas for um múltiplo do número de jogos (ou número de jogos menos um), caso contrário, teremos um número de casa ou fora jogos demais (a diferença entre o número real de jogos e o próximo múltiplo).

(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)]

Fiz várias modificações diretas para obter uma abordagem mais próxima de uma rotação equilibrada:

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

Mas é claro que isso não é um algoritmo inteligente. Isso ajuda, mas não satisfaz plenamente nenhum dos dois objetivos.

Eu tenho tentado encontrar um algoritmo que resolve esse problema, mas eu não consegui encontrar um, uma surpresa, porque o agendamento de torneios é um problema comum.

Tenho dificuldade em usar programação de restrições para usar esse problema, mas não tenho certeza se essa seria a solução definitiva, talvez seja um pouco exagerado e outra abordagem mais clássica é melhor. Além disso, formular o problema como um problema de programação de restrições (ou CSP) pode se tornar um grande desafio, pelo menos para mim.

Qualquer tipo de ajuda, sugestão, insight será bem-vindo.

python algorithms scheduling combinatorics

por dabadaba 10.03.2017 / 10:49

fonte

1 resposta

Tags python algorithms scheduling combinatorics

Decide decisão para memorizar instâncias / referências já construídas Escolha entre adicionar uma dependência maven vs. copiar a classe que eu preciso

score 1 · Accepted Answer

Eu não acho que seja possível satisfazer estritamente este requisito em um sistema round-robin:

H/A rotation: each team should play a home game and an away game every other round, i.e. in a tournament with 5 rounds, a given team should have the following rotation: H-A-H-A-H.

Digamos que você tenha um sistema round-robin em que cada equipe participe de uma partida a cada rodada e cada equipe tenha uma programação alternada perfeitamente alternada. Sejam A e B equipes que jogam em casa no primeiro turno. Então eles estarão jogando em casa em cada round ímpar e jogando fora todos os rounds. Nunca haverá uma rodada em que A jogue em casa e B jogue fora ou vice-versa. Consequentemente, se A e B não compartilharem o local da casa, então A e B nunca se enfrentarão. O sistema é falho.

Acho que atribuir a localização da equipe (Home ou Away) às linhas do algoritmo round robin padrão e alterná-las deve funcionar razoavelmente bem.

Assim, para a primeira rodada (e para cada rodada ímpar), você teria as equipes da casa na primeira linha e as equipes ausentes na segunda linha:

Round 1. (1 plays 14, 2 plays 13, ... )
1  2  3  4  5  6  7 (Home)
14 13 12 11 10 9  8 (Away)

Para a segunda rodada (e para cada rodada), você teria times fora na primeira linha e equipes da casa na segunda linha:

Round 2. (1 plays 13, 14 plays 12, ... )
1  14 2  3  4  5  6 (Away)
13 12 11 10 9  8  7 (Home)

Alternar para casa e para longe pode ser implementado usando o primeiro algoritmo e alterando essa linha

pairings.append((teams[i], teams[len(teams) - i - 1]))

em algo parecido com isto

if turn % 2:
    home = teams[i]
    away = teams[len(teams) - i - 1])
else:
    home = teams[len(teams) - i - 1])
    away = teams[i]
pairings.append((home, away))