Seuraa 
Viestejä979
Liittynyt27.8.2007

Aloin tässä pohtimaan sellaista yksinkertaista turnausta, jossa n kappaletta pelaajia pelaa kerran toisiaan vastaan ja ottelut järjestetään peräkkäin siten, että kunkin pelaajan pelit olisivat levittäytyneet mahdollisimman tasaisesti.

Googlettamalla varmaan systeemistä löytyy paljonkin tietoa, mutta itse en keksinyt mitään yleispätevää sääntöä, jolla tällainen järkevä turnaus voitaisiin muodostaa. Sain muodostettua vain joukon pelilistoja, joita sitten liimaillaan sopivasti perääkäin, että saadaan kaikki pelit käytyä läpi. Onko palstalaisilla mitään nokkelaa ideaa? Tuskin tää nyt mikään NP-täydellinen ongelma on

" sähkö (se sähkö, jota tuotetaan mm. voimalaitoksissa) ei ole energiaa "
- Vastaaja_s24fi

“Jos et ole kaksikymppisenä vihreä, sinulla ei ole sydäntä. Mutta jos et ole nelikymppisenä perussuomalainen, sinulla ei ole aivoja.”
- Cargo

Kommentit (14)

abskissa
Seuraa 
Viestejä3654
Liittynyt9.10.2008

Tehtävän voi myös muotoilla niin, että miten muodostetaan symmetrinen n*n -matriisi, jossa diagonaalialkiot ovat nollia (merkityksettömiä), muut alkiot ovat kokonaislukuja välillä [1, n*(n-1)/2] ja jossa samoilla riveillä ja sarakkeilla ei olisi peräkkäisiä numeroita tai että samoilla riveillä ja sarakkeilla olevat numerot olisivat mahdollisimman hajallaan. Tuota hajallaan oloa voisi varmaan täsmentääkin.

Siis esimerkiksi n=5 tapauksen voi hajoittaa tällaiseksi matriisiksi:

[code:2or307ki]
A B C D E
A # 1 6 9 3
B 1 # 4 7 10
C 6 4 # 2 8
D 9 7 2 # 5
E 3 10 8 5 #
[/code:2or307ki]

Tätä vastaava otteluohjelma on (numeroiden positioita järjestyksessä lukien)

1: A-B
2: C-D
3: A-E
4: B-C
5: D-E
6: A-C
7: B-D
8: C-E
9: A-D
10: B-E

Tässä ohjelmassa ei ole peräkkäisiä otteluita yhdelläkään osanottajalla, mikä tuossa matriisissa näkyy siten, että millään rivillä tai sarakkeella ei ole peräkkäisiä numeroita.

Aika nopeasti tuohon jotain näppituntumaa saa kokeilemallakin, joten eiköhän se optimaalinen algoritmikin jostain löydy.

Jees voisi tyhmemmilleen tiivistää, miten tuo Ramseyn lause tähän liittyy. Ei sytytä...

We're all mad here.

Neutroni
Seuraa 
Viestejä30813
Liittynyt16.3.2005

Tuo voisi olla hyvä kohde geneettiselle algoritmille. Kehitä jonkinlainen hyvyysfunktio, joka rankaisee sen mukaan kuinka monta ottelua on kahden saman joukkeen ottelun välissä. Arvo vaikka tuhat satunnaista järjestystä, pane ne paremmuusjärjestykseen tuolla hyvysfunktiolla. Raakkaa huonompi puolisko ehdotuksista ja korvaa ne paremman puoliskon kopiolla, jossa vaihdetaan yksi tai muutama ottelua. Toista riittävän monta iteraatiota ja saat varmasti riittävän hyvän tuloksen.

Tuo on epätehokas ja epäelegantti tapa, mutta sen vahvuus on siinä, että ongelmasta ja sen ratkaisusta ei tarvita syvällistä tietämystä, että pystytään panemaan ratkaisuehdotukset paremmuusjärjestykseen. Eli se säästää koodaamis- ja opsikeluvaivaa kellojaksojen kustannuksella. Mutta sillä tuskin on väliä, laskeeko kone jonkin turnauksen pelit millisekunnissa vai sekunnissa.

Läskiperse
Seuraa 
Viestejä950
Liittynyt11.12.2010

If ymmärsin tehtävän, helpoin tapa on käyttää xor-operaatiota. Allah on esimerkki 13 joukkueen parituksesta. 0 ja yli 13 korvataan risuaidalla, koska pitää olla jokin 2^N pläjäys:

[code:1hr52cva]
+ A B C D E F G H I J K L M N O P
A # 1 2 3 4 5 6 7 8 9 10 11 12 13 # #
B 1 # 3 2 5 4 7 6 9 8 11 10 13 12 # #
C 2 3 # 1 6 7 4 5 10 11 8 9 # # 12 13
D 3 2 1 # 7 6 5 4 11 10 9 8 # # 13 12
E 4 5 6 7 # 1 2 3 12 13 # # 8 9 10 11
F 5 4 7 6 1 # 3 2 13 12 # # 9 8 11 10
G 6 7 4 5 2 3 # 1 # # 12 13 10 11 8 9
H 7 6 5 4 3 2 1 # # # 13 12 11 10 9 8
I 8 9 10 11 12 13 # # # 1 2 3 4 5 6 7
J 9 8 11 10 13 12 # # 1 # 3 2 5 4 7 6
K 10 11 8 9 # # 12 13 2 3 # 1 6 7 4 5
L 11 10 9 8 # # 13 12 3 2 1 # 7 6 5 4
M 12 13 # # 8 9 10 11 4 5 6 7 # 1 2 3
N 13 12 # # 9 8 11 10 5 4 7 6 1 # 3 2
O # # 12 13 10 11 8 9 6 7 4 5 2 3 # 1
P # # 13 12 11 10 9 8 7 6 5 4 3 2 1 #
[/code:1hr52cva]

Läskiperse
Seuraa 
Viestejä950
Liittynyt11.12.2010

Ylempi ratkaisu on väärin. Eikö kukaan huomannut? Nyt otteluparituksessa sekoilee 16 joukkuetta, kun sai olla vain 13 joukkuetta. 2^N tapaukset ovat helppoja, mutta muut ovat paljon kimurantimpia. Miten siis 13 joukkuetta paritetaan validisti?

abskissa
Seuraa 
Viestejä3654
Liittynyt9.10.2008
Läskiperse
Miten siis 13 joukkuetta paritetaan validisti?

Niin, yksi malli oli tuossa jo linkitetyssä Wikipedia-artikkelissa. Lyhyesti homma menee näin:

1. Numeroidaan joukkueet 1-13 ja otetaan mukaan lisäksi "dummy"-joukkue x. Tämä tarvitaan siksi, että algoritmi edellyttää parillisen määrän joukkueita.

2. Jaetaan joukkueet kahteen seitsemään joukkueen "riviin":

[code:3idqpkwa]1 2 3 4 5 6 7
8 9 10 11 12 13 x[/code:3idqpkwa]

Tässä on ensimmäisen kierroksen otteluparit:

1 - 8
2 - 9
...
6 -13

Joukkue 7, joka on paritettu x:n kanssa, huilaa tämän kierroksen

3. Pidetään nyt joukkue numero 1 paikallaan ja pyöräytetään muita yksi pykälä myötäpäivään:

[code:3idqpkwa]1 8 2 3 4 5 6
9 10 11 12 13 x 7[/code:3idqpkwa]

Tästä saadaan toisen kierroksen otteluparit:

1 - 9
8 - 10
2 - 11
...
6 - 7

Joukkue 5 huilaa tämän kierroksen.

4. Toistetaan kohtaa 3, kunnes on palattu ensimmäisen kierroksen järjestykseen.

We're all mad here.

Läskiperse
Seuraa 
Viestejä950
Liittynyt11.12.2010

Tuota paritusmetodia käytetään ainakin myös pikashakissa, jossa peliaika <= 15 min.

Turnauksessa paritus onkin sitten paljon monisäkeisempi, koska korkeimmalle selolle ei kannata parittaa vähiten seloja edustavaa (ex. Sergei Ivanov (2360) vs Läskiperse (1534)), jne.

Julius
Seuraa 
Viestejä279
Liittynyt24.3.2013

Entäs mitä silloin tehdään, kun on kuusi tuntia aikaa ja yksi kierros laskentoineen ja vaihtoineen kestää 30 minuuttia. Kuudessa tunnissa pystytään pelaamaan 12 kierrosta. Osallistujia on kuitenkin 32 joukkuetta/yksilöä. Kaikki eivät ehdi pelata kaikkia vastaan.

Miten tuollaisesta saadaan selville kolme parasta ja kolme huonointa suurella todennäköisyydellä? Kaikki pelaavat koko 6 tuntia, yhtään joukkuetta tai osallistujaa ei pudoteta missään vaiheessa.

Miten tehdään paritus?

abskissa
Seuraa 
Viestejä3654
Liittynyt9.10.2008
Julius
Entäs mitä silloin tehdään, kun on kuusi tuntia aikaa ja yksi kierros laskentoineen ja vaihtoineen kestää 30 minuuttia. Kuudessa tunnissa pystytään pelaamaan 12 kierrosta. Osallistujia on kuitenkin 32 joukkuetta/yksilöä. Kaikki eivät ehdi pelata kaikkia vastaan.

Miten tuollaisesta saadaan selville kolme parasta ja kolme huonointa suurella todennäköisyydellä? Kaikki pelaavat koko 6 tuntia, yhtään joukkuetta tai osallistujaa ei pudoteta missään vaiheessa.

Miten tehdään paritus?


Mielenkiintoinen asetelma. Ensin pitää varmaan lähteä liikkeelle siitä, miten määritellään paremmuus. Voidaanko esimerkiksi olettaa paremmuus transitiiviseksi: jos A voittaa B:n ja B voittaa C:n, niin A katsotaan C:tä paremmaksi ilman keskinäistä ottelua.

Jos transitiivisuus hyväksytään, asetelmaan voi purra jokin lajittelualgoritmi.

We're all mad here.

Suosituimmat

Uusimmat

Uusimmat

Suosituimmat