Třídící algoritmus, aby doubleheaders back-to-back

Question 1

V souvislosti sports scheduling mám seznam her, kde týmy hrají více než 1x hra, potenciálně. Pokud je to ten případ, jejich hry by měly být back-to-back. Protože to je možná ne feasable vzhledem k povaze párování, alespoň by měly být co nejblíže k sobě.

Toto je příklad počáteční párování, kde každý tým hraje 2x:

[('t05', 't09'), ('t07', 't03'), ('t01', 't09'), ('t03', 't01'), ('t07', 't05'), ('t02', 't06'), ('t04', 't06'), ('t10', 't08'), ('t10', 't04'), ('t08', 't02')]

Všimněte si, že to není double round-robin konfiguraci, kde každý tým hraje každý druhý dvakrát v domov a pryč hry. To je prostě konfigurace, kde týmy hrají dvě hry.

Snažím se implementovat algoritmus na tyhle hry, aby každý tým hry je co nejblíže k sobě. To je první, jednoduchý přístup:

matches = list(matches)
c = collections.Counter([t for m in matches for t in m.teams])
for t, n in c.iteritems():
    if n > 1:
        # matches containing the team t
        indices = [i for i, m in enumerate(matches) if t in m.teams]
        for i in indices:
            # bring these matches to the front
            matches.insert(0, matches.pop(i))
return matches

Tohle je výsledek:

[('t10', 't04'), ('t10', 't08'), ('t01', 't09'), ('t05', 't09'), ('t08', 't02'), ('t07', 't03'), ('t07', 't05'), ('t02', 't06'), ('t04', 't06'), ('t03', 't01')]

Samozřejmě, že to není moc dobrý, jak je to jednostranné a je přínosem více týmů na konci seznamu tím, že umístí své hry, v přední části seznamu. S one-sided myslím, že to vypadá na jen jeden tým v každé hře a funguje třídění pro tým, bez ohledu na druhý tým, který bude zlomit zpět-k-zpět rovnováhu pro druhý tým.

To by byl ideální případ maximalizace pomocí programování s omezujícími podmínkami, například pomocí python-constraint nebo pyomo. Ale já jsem opravdu špatný na modelování constraint satisfaction problémy (CSP), takže jsem neměl ponětí, kde začít s tímto případem.

Nějaké nápady?

Question 2

Rekurzivní funkce může vyzkoušet různé uspořádání v dynamickém programovacím módu, který upřednostňuje spojení hry v průběhu přestávky v pořadí.

Tento není nijak zvlášť optimalizované, ale měl by fungovat dostatečně rychlý pro malé seznamy her:

def gameOrder(games,prevGame=None):
    if len(games)==1: return games    # base condition (only one game)
    best,breaks = games,len(games)-1  # track best order and number of breaks
    for strict in (1,0):              # prioritize connections over breaks
        for i,game in enumerate(games): # each game as 1st in sequence
            if breaks <= strict: return best  # minimum breaks reached
            if strict and prevGame and prevGame.isdisjoint(game): 
                continue # does not connect to previous (strict)
            seq = [game]+gameOrder(games[:i]+games[i+1:],set(game)) # sort rest
            brk = sum(set(g1).isdisjoint(g2) for g1,g2 in zip(seq,seq[1:]))
            if brk < breaks:
                breaks,best = brk,seq # track best so far
    return best # return best found

Výstup:

games = [('t05', 't09'), ('t07', 't03'), ('t01', 't09'), ('t03', 't01'), 
         ('t07', 't05'), ('t02', 't06'), ('t04', 't06'), ('t10', 't08'), 
         ('t10', 't04'), ('t08', 't02')]

print(gameOrder(games)) # only one break between (t07,t05) and (t02,t06)
[('t05', 't09'), ('t01', 't09'), ('t03', 't01'), ('t07', 't03'), 
 ('t07', 't05'), ('t02', 't06'), ('t04', 't06'), ('t10', 't04'), 
 ('t10', 't08'), ('t08', 't02')]

Všimněte si, že tím je zajištěno, že tolik týmů, jak je to možné, mají po sobě jdoucí hry. To nemusí být nejlepší řešení, pokud je vaším cílem je, aby se minimalizovalo nejhorším případě "vzdáleností" mezi hry pro všechny týmy, nebo minimalizovat průměrnou hru vzdálenost na tým.

Alain T. · Answer 1 · 2021-11-12T19:26:55

Rekurzivní funkce může vyzkoušet různé uspořádání v dynamickém programovacím módu, který upřednostňuje spojení hry v průběhu přestávky v pořadí.

Tento není nijak zvlášť optimalizované, ale měl by fungovat dostatečně rychlý pro malé seznamy her:

def gameOrder(games,prevGame=None):
    if len(games)==1: return games    # base condition (only one game)
    best,breaks = games,len(games)-1  # track best order and number of breaks
    for strict in (1,0):              # prioritize connections over breaks
        for i,game in enumerate(games): # each game as 1st in sequence
            if breaks <= strict: return best  # minimum breaks reached
            if strict and prevGame and prevGame.isdisjoint(game): 
                continue # does not connect to previous (strict)
            seq = [game]+gameOrder(games[:i]+games[i+1:],set(game)) # sort rest
            brk = sum(set(g1).isdisjoint(g2) for g1,g2 in zip(seq,seq[1:]))
            if brk < breaks:
                breaks,best = brk,seq # track best so far
    return best # return best found

Výstup:

games = [('t05', 't09'), ('t07', 't03'), ('t01', 't09'), ('t03', 't01'), 
         ('t07', 't05'), ('t02', 't06'), ('t04', 't06'), ('t10', 't08'), 
         ('t10', 't04'), ('t08', 't02')]

print(gameOrder(games)) # only one break between (t07,t05) and (t02,t06)
[('t05', 't09'), ('t01', 't09'), ('t03', 't01'), ('t07', 't03'), 
 ('t07', 't05'), ('t02', 't06'), ('t04', 't06'), ('t10', 't04'), 
 ('t10', 't08'), ('t08', 't02')]

Všimněte si, že tím je zajištěno, že tolik týmů, jak je to možné, mají po sobě jdoucí hry. To nemusí být nejlepší řešení, pokud je vaším cílem je, aby se minimalizovalo nejhorším případě "vzdáleností" mezi hry pro všechny týmy, nebo minimalizovat průměrnou hru vzdálenost na tým.

To je opravdu působivé vzít, díky! Zajímalo by mě, jestli bych mohl upravit tak, že pokud se spojení nemůže stát a rozbít se stane, bez ohledu na to, co, další, že by se mohl pokusit udržet her co nejblíže k sobě, než se "vzdát" a nechat to v jakékoliv pozici, oni skončit. V podstatě "minimalizaci" přestávky tím, že drží ty hry blíže k sobě.
Ano, je to možné. Budete muset použít n-tice, jako měření "nejlepší". N-tice by použít počítat přestávky, pokud to je první (hlavní) složky a můžete vypočítat celkové (nebo průměrná) vzdálenost z předchozí hry, týmy jako druhá složka). Na if brk < breaks: podmínkou by použití těchto n-tic namísto jediné celé číslo. Všimněte si, že minimální přestávky dosáhli optimalizace by také měly být revidovány.
Vypadá to dobře? gist.github.com/kpagcha/91f136b9925157b5f6fb30db1ee1cb9d snažím se přemýšlet, jak základní stav by měl být změněn, jinak to bude zastavit při pohledu na "blíže" hry, když nim úlevy je dosaženo. Chceme dál pracovat trochu těžší. Možná srovnání s počáteční hodnotě vzdálenosti až "dost dobrý" zlepšení bylo dosaženo prahu? (např. vzdálenost byla snížena na polovinu), Ale co když to není feasable a to trvá příliš dlouho? To bychom nechtěli, že.
Stav by měl být if (brk,dst) <= (breaks,distance): tak, že vzdálenost je pouze vzít v úvahu při brk a přestávky jsou stejné. (tj. n-tice srovnání). Také if breaks <= strict: break stav/optimalizace musí být revidován, protože to bude bránit nejlepší vzdálenost výběr, když tam je jen jedna přestávka.
Nevěděl, o n-tice srovnání! Jo, to je to, co jsem myslel o přestávce stavu. Mělo by to jen pokračovat v hledání pro 0 přestávky zda přísný nebo ne?
Vzhledem k tomu, že vzdálenost vylepšení mohou ještě získat, i když přísná, já bych navrhnout dělá pouze jeden průchod (tedy žádné striktní/unstrict) a přerušit smyčku pouze tehdy, když výsledek nemůže být lepší (tj. přestávky==0 nebo vzdálenosti<x), kde x je prahová hodnota, že se můžete rozhodnout, v závislosti na výkonu hledáte.
No ale dostat se na breaks == 0 neznamená to, že vzdálenost nemůže být optimalizován už to dělá? Tam bude ještě být týmy, jejichž hry jsou daleko od sebe, protože "spojení" bere v úvahu pouze 1 tým, ale hra je tvořena 2.
Když přestávky je nulová, budete mít kompletní smyčky, takže jeden z týmů z první hry bude bezkonkurenční tým poslední zápas. Všechny nulové-prolomit řetězy bude mít tato vlastnost sot není možné zlepšení, které mají jiný tým na každém konci..

Třídící algoritmus, aby doubleheaders back-to-back

Otázka

Nejlepší odpověď

V jiných jazycích

Tato stránka je v jiných jazycích

Populární v této kategorii

Oblíbené položky v této kategorii