Witam! Mam spory problem z ustawieniem zawodników w kolejkach meczowych. O co chodzi? Już wyjaśniam:
W sezonie gra parzysta liczba graczy. Liczba par meczowych jakie możemy z nich utworzyć jest \(\displaystyle{ \frac{n}{2}}\) . Sezon dzieli się na \(\displaystyle{ n-1}\) kolejek oraz na \(\displaystyle{ n-1}\) kolejek rewanżowych. W każdej kolejce grają wszyscy gracze, jeden na jeden (tworzą wspomniane pary). Chodzi o to by mógł zagrać każdy z każdym, żeby w \(\displaystyle{ n-1}\) kolejkach (bez rewanżów) każdy mecz wystąpił tylko raz (1 kontra 2 to to samo co: 2 kontra 1, więc odpada), oraz że w jednej kolejce żaden z graczy nie zagra dwa razy.
Przykład dla \(\displaystyle{ n=6}\):
\(\displaystyle{ G=\left\{ 1,2,3,4,5,6\right\}}\)
Mamy 6 graczy czyli 5 kolejek (bez rewanżów):
\(\displaystyle{ 1vs2}\)
\(\displaystyle{ 3vs4}\)
\(\displaystyle{ 5vs6}\)
\(\displaystyle{ 13}\)
\(\displaystyle{ 25}\)
\(\displaystyle{ 46}\)
\(\displaystyle{ 14}\)
\(\displaystyle{ 26}\)
\(\displaystyle{ 35}\)
\(\displaystyle{ 15}\)
\(\displaystyle{ 24}\)
\(\displaystyle{ 36}\)
\(\displaystyle{ 16}\)
\(\displaystyle{ 23}\)
\(\displaystyle{ 45}\)
Jak widać każda kolejka ma unikalne mecze.
Napisałem program w C++ który wyznacza takie kolejki. Problem w tym że jego złożoność jest liniowa, i jak dla \(\displaystyle{ 6!}\) daje jeszcze radę, tak dla \(\displaystyle{ 20!}\) komputer się poddaje.
Jest może jakiś szybszy sposób na wyznaczanie tego typu kolejek meczowych? Może jest ktoś zorientowany w tym jak to wygląda np. w takiej angielskiej Barclays Premier League? Tam jest 20 zespołów, każdy gra z każdym i jest 38 kolejek (z rewanżowymi). W jaki sposób stworzyć taki terminarz?
Byłbym bardzo wdzięczny za pomoc i wskazówki!
Pozdrawiam.
[Algorytmy] Wyznaczenie kolejek meczowych
-
- Użytkownik
- Posty: 351
- Rejestracja: 2 maja 2012, o 16:16
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 1 raz
- Pomógł: 94 razy
[Algorytmy] Wyznaczenie kolejek meczowych
Problem który przedstawiasz to kolorowanie krawędziowe grafu pełnego.
Wierzchołki grafu to drużyny. Krawędzie to mecze do rozegrania. Kolor krawędzi to terminy spotkań.
Zła wiadomość jest taka że ogólny problem kolorowania grafu jest problemem NP - zupełnym. Nie są znane wielomianowe algorytmy które dają zawsze rozwiązanie optymalne (minimalną liczbę kolorów).
Dobra jest taka że Twój graf jest grafem pełnym o parzystej liczbie wierzchołków. To dosyć specyficzny graf i jego indeks chromatyczny jest równy 2n-1.
Myślę że są duże szanse aby znaleźć konkretny algorytm pod hasłem kolorowanie krawędziowe grafu.
Dwa algorytmy heurystyczne są znane jako NTL i NC
Wierzchołki grafu to drużyny. Krawędzie to mecze do rozegrania. Kolor krawędzi to terminy spotkań.
Zła wiadomość jest taka że ogólny problem kolorowania grafu jest problemem NP - zupełnym. Nie są znane wielomianowe algorytmy które dają zawsze rozwiązanie optymalne (minimalną liczbę kolorów).
Dobra jest taka że Twój graf jest grafem pełnym o parzystej liczbie wierzchołków. To dosyć specyficzny graf i jego indeks chromatyczny jest równy 2n-1.
Myślę że są duże szanse aby znaleźć konkretny algorytm pod hasłem kolorowanie krawędziowe grafu.
Dwa algorytmy heurystyczne są znane jako NTL i NC
-
- Użytkownik
- Posty: 53
- Rejestracja: 21 lut 2011, o 20:49
- Płeć: Mężczyzna
- Lokalizacja: Skierniewice
- Pomógł: 10 razy
[Algorytmy] Wyznaczenie kolejek meczowych
Oczywiście że istnieją, proste algorytmy tworzenia takich lig. Np. w tym artykule jest jakieś opisany Jest chyba nawet nietrudny do zaimplementowania.
Kod: Zaznacz cały
http://www.deltami.edu.pl/temat/informatyka/algorytmy/2011/02/27/O_rozgrywkach_ligowych