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:
- 10 drużyn
- Każda drużyna gra ze sobą 1 raz (wymagane 45 wszystkich gier)
- Każda drużyna gra nie więcej niż 1 raz dziennie
- 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?
źródło
Odpowiedzi:
Oto algorytm, który sam wymyśliłem. Nie wiem, czy już istnieje, czy faktycznie jest implementacją Round Robin:
w zasadzie zaczynasz
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ę.
źródło
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”).
źródło
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
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.
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źć.
źródło