Potrzebujesz pomocy w identyfikacji algorytmu planowania ligi

9

Próbuję utworzyć harmonogram ligi sportowej. Mam problem ze zidentyfikowaniem algorytmu, który pomógłby mi skutecznie wypełnić każde pole.

Przykładowe dane do zbudowania harmonogramu to:

  1. 10 drużyn
  2. Każda drużyna gra ze sobą 1 raz (wymagane 45 wszystkich gier)
  3. Każda drużyna gra nie więcej niż 1 raz dziennie
  4. W moich testach używam 9 dni z 5 automatami na dzień.

Tabela kombinacji (zawiera 45 kombinacji)

ID
Team1ID
Team2ID
bitAssigned

Tabela harmonogramów (zawiera 45 przedziałów czasowych)

scheduleID
homeTeamID
awayTeamID
GameDate
GameTime

Obecnie moje istniejące procedury wypełniają około 90% miejsc, pozostawiając 10% moich miejsc pustych do konfliktu planowania na podstawie powyższych zasad.

Przeglądam tabelę harmonogramów w porządku rosnącym według daty / godziny.
Moim pierwszym automatem może być sobota o 8 rano.
Przeszukuję listę zespołów, które nie zostały jeszcze zaplanowane. Następnie tworzę szereg możliwych kombinacji tych zespołów. Następnie używam tej tablicy, aby pobrać 1 losowy rekord z mojej tabeli kombinacji z kombinacji, które nie zostały jeszcze zaplanowane, i umieszczam te drużyny w harmonogramie. Następnie ustawiłem tę kombinację jako używaną.

Powtarzam pętlę w kółko i za każdym razem moja lista dostępnych drużyn zmniejsza się, a moja tablica w wyniku tego jest również mniejsza.

Uważam, że niektóre dni idą dobrze, a w inne moje ostatnie 2 ostatnie drużyny grały już w poprzednim tygodniu, więc nie są ponownie dodawane do harmonogramu.

Jedyne, czego jeszcze nie próbowałam, to „zresetować” dni konfliktu i wypróbować je od nowa, aby sprawdzić, czy dostanę lepsze miejsca docelowe.

Czy ktoś ma jakieś sugestie?

Steve
źródło
5
harmonogram turniejów round-robin
kevin cline
dzięki Kevin. masz rację. Wydaje mi się, że teraz moja tablica zaczyna się w tym samym miejscu za każdym razem i nie ma rotacji, więc nie ma uporządkowanego przepływu do parowania zespołów.
steve
1
Używam całkowicie losowego podejścia. Losowo wybierz miejsce i dwie drużyny. Jeśli reguły są spełnione, zaplanuj grę. Jeśli nie, odrzuć i spróbuj ponownie. Ustawiam limit wszystkich prób, a jeśli limit zostanie osiągnięty, odrzuć cały harmonogram i zacznij od nowa. W praktyce działa całkiem dobrze.
Cerad,
Skończyło się na tym, że poszedłem i podążałem za podejściem round robin. W 95% skończyłem pisać skrypt, aby połączyć się z bazą danych, ale podczas testowania wydaje się, że działa płynnie i zrównoważony. Dni traktuję jak „obchody”, a one pozostają ładne i zrównoważone. Mogę rozgrywać rundy w dowolnej kolejności i układać gry dla każdej rundy w dowolnej kolejności, ale przenoszenie gry z jednej rundy do drugiej ostatecznie złamałoby zasady.
steve

Odpowiedzi:

5

Oto algorytm, który sam wymyśliłem. Nie wiem, czy już istnieje, czy faktycznie jest implementacją Round Robin:

1 4    1 5   1 6   1 3   1 2
2 5    4 6   5 3   6 2   3 4
3 6    2 3   4 2   5 4   6 5

w zasadzie zaczynasz

rotacja zdj

i zawsze utrzymuj 1 w tej samej pozycji i obracaj resztą.

W ten sposób zawsze otrzymasz harmonogram niepowtarzalnych meczów. Jest to niezwykle łatwe do wdrożenia i skaluje się z dowolną liczbą przeciwników, nawet nierówną. Jeśli masz nieparzystą liczbę przeciwników, po prostu nie umieszczaj drużyny na 1 pozycji, a oni mają wolną rundę.

Pieter B.
źródło
2
jak zarządzasz saldami w domu i na wyjeździe?
Eric Cope
To tak naprawdę nie działa - w tym prostym algorytmie rotacji zespoły rotacyjne, które są w odległości 2 miejsc (2/4, 3/5), nigdy nie będą grać.
mdryden
@mdryden to działa. Sprawdź to lepiej i usuń komentarz.
Pieter B
@PieterB Myślałem, że to zadziała, ale tak naprawdę nie działa, jeśli jest nieparzysta liczba drużyn, ponieważ te, które są obok siebie (jak 4 i 5) nigdy się ze sobą nie zagrają. Możesz zobaczyć to dość łatwo na końcu z 1, a także na drugim końcu, ponieważ masz wiszącą drużynę (z pa). Dobra odpowiedź, która dotyczy również liczby nieparzystej: stackoverflow.com/a/6649732/ 6489306
ragingasiancoder
@ragingasiancoder, jeśli liczba drużyn jest nieparzysta, dodaj drużynę zastępczą. Odpowiedź, którą podłączyłeś, opisuje dokładnie to samo rozwiązanie, które przedstawiłem.
Pieter B
1

Myślę, że robisz to wstecz. Nie zaczynaj od tabeli harmonogramów, zacznij od tabeli / tablicy / niezależnie od wszystkich kombinacji gier (45 gier). Odtąd przypisywanie gier do jednego dnia jest proste, na podstawie drużyny grającej tylko raz dziennie. A ponieważ pojedynki zdarzają się tylko raz (Drużyna A gra tylko raz Drużyna B), planowanie jest łatwe, ponieważ musisz tylko upewnić się, że pojedynek jeszcze się nie zdarzył (wpisy są w ten sposób „unikalne”).

Nieznany koder
źródło
1

Wygenerowałem poniżej harmonogram 10 pojedynczych rund drużynowych dla jednego zespołu. Zajęło mi to około 3 minut.

Informacje o harmonogramie:

10 drużyn - 1 runda robin (wyświetlane są tylko pierwsze 6 tygodni)
Data rozpoczęcia sezonu 1/6/15 - data zakończenia 3/5/15
2 mecze w każdy wtorek, 3 mecze w każdy czwartek, 5 meczów w każdym tygodniu bez dat pomijania

  • Wszystkie drużyny są rozmieszczone, aby grać w 5 przedziałach czasowych jednakowo.
  • Wszyscy grają w 9 gier.
  • Wszyscy grają jeden raz.
  • Wszystkie są rozmieszczone równomiernie jako strona główna i gość (5/4 lub 4/5). Uwaga: na koniec rundy robin 2 wszystkie drużyny grają w 18 gier (9 jako gospodarz i 9 jako gość), a wszystkie drużyny mają 2 Bye.
  • Wszystkie są rozmieszczone, aby grać równomiernie w 5 przedziałach czasowych każdego tygodnia.

Użyliśmy przestarzałego komputera z ramą główną Honeywell i niecałe 3 lata, aby złożyć to wszystko w całość. Po debugowaniu naszego oprogramowania do planowania, komputer główny zajmował wiele godzin, szukając milionów permutacji i kombinacji, aby obliczyć i stworzyć zrównoważone wzorce dla 4 do 22 zespołów, których szukaliśmy.

10 Team Division Schedule   DATE 12/20/14

DATE   DAY TIME    LOCATION  GM  HOME vs VISITOR

Jan  6 Tue 6:00pm  Field #1   1  # 1 vs #10 
Jan  6 Tue 6:00pm  Field #2   1  # 2 vs # 9 
Jan  8 Thu 6:30pm  Field #3   1  # 3 vs # 8 
Jan  8 Thu 6:30pm  Field #4   1  # 4 vs # 7 
Jan  8 Thu 6:30pm  Field #5   1  # 5 vs # 6

Jan 13 Tue 6:00pm  Field #1   2  # 6 vs # 3 
Jan 13 Tue 6:00pm  Field #2   2  #10 vs # 8 
Jan 15 Thu 6:30pm  Field #3   2  # 7 vs # 2 
Jan 15 Thu 6:30pm  Field #4   2  # 9 vs # 1 
Jan 15 Thu 6:30pm  Field #5   2  # 4 vs # 5

Jan 20 Tue 6:00pm  Field #1   3  # 7 vs # 9 
Jan 20 Tue 6:00pm  Field #2   3  # 5 vs # 2 
Jan 22 Thu 6:30pm  Field #3   3  # 6 vs #10 
Jan 22 Thu 6:30pm  Field #4   3  # 3 vs # 4 
Jan 22 Thu 6:30pm  Field #5   3  # 8 vs # 1

Jan 27 Tue 6:00pm  Field #1   4  # 9 vs # 5 
Jan 27 Tue 6:00pm  Field #2   4  # 1 vs # 7 
Jan 29 Thu 6:30pm  Field #3   4  # 2 vs # 3 
Jan 29 Thu 6:30pm  Field #4   4  # 8 vs # 6 
Jan 29 Thu 6:30pm  Field #5   4  #10 vs # 4

Feb  3 Tue 6:00pm  Field #1   5  # 4 vs # 8 
Feb  3 Tue 6:00pm  Field #2   5  # 7 vs # 5 
Feb  5 Thu 6:30pm  Field #3   5  # 1 vs # 6 
Feb  5 Thu 6:30pm  Field #4   5  #10 vs # 2 
Feb  5 Thu 6:30pm  Field #5   5  # 3 vs # 9

Feb 10 Tue 6:00pm  Field #1   6  # 3 vs # 7 
Feb 10 Tue 6:00pm  Field #2   6  # 6 vs # 4 
Feb 12 Thu 6:30pm  Field #3   6  # 5 vs # 1 
Feb 12 Thu 6:30pm  Field #4   6  # 9 vs #10 
Feb 12 Thu 6:30pm  Field #5   6  # 8 vs # 2 

Nie ma algorytmu, który rozwiązałby ogólne problemy z planowaniem związane z setkami lub tysiącami różnych rodzajów lig, sportów i potencjalnych sytuacji. Aby rozwiązać ten problem, przyjęliśmy inne podejście do obliczania harmonogramów. Zaczyna się od bardzo złożonej matematyki, aby ustalić odpowiednie pary drużyn z rundami (pojedynki), ale to był dopiero początek. Inne elementy są potrzebne, aby stworzyć użyteczny zrównoważony harmonogram, który można publikować i dystrybuować. Zawodnicy, trenerzy, rodzice itp. Muszą wiedzieć nie tylko, w kogo grają ; ale gdzie grają ; o której godzinie grają ; jeśli są w domu lub są gościem ; a dla wielu lig numer gry .

Mam nadzieję, że to pomoże Tobie i innym zrozumieć, co zajęło nam 3 lata, aby to rozgryźć.

Społeczność
źródło