Sto cercando di ottenere un algoritmo round-robin per la programmazione sportiva che garantisca anche una rotazione casa / distanza equa o bilanciata.
Ho basato il mio algoritmo sull'algoritmo round-robin scheduling :
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
Tuttavia, questo algoritmo non affronta il saldo H / A. Sto cercando di soddisfare questi due obiettivi:
-
Rotazione H / A: ogni squadra deve giocare una partita in casa e una partita in trasferta a turno alterno, cioè in un torneo con 5 round, una squadra specifica dovrebbe avere la seguente rotazione:
H-A-H-A-H. -
Numero di partite H / A: il numero di partite in casa e partite in trasferta dovrebbe essere lo stesso (o compensato da uno se il totale è dispari), quindi un torneo con 10 partite per squadra dovrebbe avere 5 a casa partite e 5 partite in trasferta per ogni squadra.
L'algoritmo precedente non soddisfa nessuno di questi obiettivi:
-
Non alterna i giochi H / A. Ad esempio, la prima squadra ha solo partite casalinghe e le altre squadre ottengono partite casalinghe fino a quando non vengono ruotate verso la fine della lista e solo in trasferta (e viceversa: partite in trasferta fino all'inizio, quindi solo partite in casa ). Vedi cosa intendo in basso (1).
-
Garantisce un numero bilanciato di partite H / A ma solo se il numero di round è un multiplo del numero di giochi (o il numero di giochi meno uno), altrimenti otteniamo un numero di casa o di distanza giochi troppi (la differenza tra il numero effettivo di giochi e il prossimo multiplo).
(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)]
Ho apportato diverse modifiche dirette per ottenere un approccio più ravvicinato a una rotazione bilanciata:
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
Ma ovviamente questo non è un algoritmo intelligente. Aiuta, ma non soddisfa pienamente nessuno dei due obiettivi.
Ho cercato di trovare un algoritmo che risolva questo problema, ma non sono riuscito a trovarne uno, una vera sorpresa perché la pianificazione dei tornei è un problema comune.
Ho pensato di usare la programmazione dei vincoli per usare questo problema, ma non sono del tutto sicuro che questa sarebbe la soluzione definitiva, forse è un po 'eccessivo e un altro approccio più classico è migliore. Inoltre, la formulazione del problema come problema di programmazione dei vincoli (o CSP) può rivelarsi una vera sfida, almeno per me.
Qualsiasi tipo di aiuto, suggerimento, intuizione sarà il benvenuto.