[Algorytmy] Wyznaczenie kolejek meczowych

L24
Użytkownik
Użytkownik
Posty: 4
Rejestracja: 22 lut 2010, o 13:08
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 3 razy

[Algorytmy] Wyznaczenie kolejek meczowych

Post autor: L24 » 13 maja 2012, o 12:56

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.
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Jacek_Karwatka
Użytkownik
Użytkownik
Posty: 350
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

Post autor: Jacek_Karwatka » 13 maja 2012, o 13:42

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

marcin_smu
Użytkownik
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

Post autor: marcin_smu » 13 maja 2012, o 16:23

Oczywiście że istnieją, proste algorytmy tworzenia takich lig. Np. w tym artykule jest jakieś opisany

Kod: Zaznacz cały

http://www.deltami.edu.pl/temat/informatyka/algorytmy/2011/02/27/O_rozgrywkach_ligowych
Jest chyba nawet nietrudny do zaimplementowania.

ODPOWIEDZ