ThesisWiki : Problem

ThesisHome :: Categories :: PageIndex :: RecentChanges :: RecentlyCommented :: Login/Register

Probleemomschrijving

Complexiteit

Ik probeer te berekenen hoeveel mogelijke kalenders er opgesteld kunnen worden voor 4 ploegen wanneer je weet dat
1) elke ploeg juist tweemaal tegen elke andere ploeg moet spelen: 1 maal thuis en 1 maal uit
2) er juist 2(n-1) rondes zijn
3) er per ronde juist n/2 wedstrijden gespeeld moeten worden
4) het voor een kalender niet uitmaakt welke wedstrijd er "eerst" gezet
wordt (ronde i wedstrijd_1 w_2 is hetzelfde als ronde 1 w_2 wedstrijd_1)

Een geldige kalender is zo voor 4 ploegen bv
ronde wedstrijd_1 wedstrijd_2
1 ATL-PHI NYM-MON
2 ATL-NYM PHI-MON
3 ATL-MON PHI-NYM
4 PHI-ATL MON-NYM
5 NYM-ATL MON-PHI
6 MON-ATL NYM-PHI

4 ploegen

Maximale (na´eve) bovengrens
Indien we een mogelijke kalender zouden voorstellen door een zin met 12 verschillende woorden, waarbij elk woord een geldige wedstrijd voorsteld tussen 2 ploegen en het per paar (1ste woord en 2de woord, 3de woord en 4de woord) niet uitmaakt in welke volgorde ze staan, zouden we
12! / 2^6 verschillende zinnen kunnen vormen.
7 484 400

Striktere (iets minder na´eve) bovengrens
Indien we er rekening mee houden dat niet alle combinaties van mogelijke paren tussen de 12 wedstrijden kunnen voorkomen. Indien we in een eerste ronde 12 mogelijkheden (12 wedstrijden * 2 andere wedstrijden / 2 want volgorde maakt niet uit); kan het zijn dat we in de 2de ronde nog maar 1 mogelijkheid hebben voor de keuze van het 2de game..
Bv.
1) AB CD
2) BA -> DC

Laten we daarom de 12 mogelijke rondes opsommen (we weten dat dit er 12 moeten zijn)
AB CD, AB DC, BA DC, ..

Voor de eerste ronde van alle kalenders hebben we dan 12 keuzes. Voor de 2de ronde hebben we er maar 9 meer (de gekozen ronde valt weg, combinaties met 1ste/2de game vallen weg). Voor de 3de ronde hangt het van de keuze van de 2de ronde af hoeveel mogelijkheden er nog zijn, als bovengrens nemen we hier 8. De vierde heeft als bovengrens 5, de 5de 4 en de laatste uiteindelijk 1 (logischerwijs).

Dit geeft een bovengrens van 17 280.

Nog striktere bovengrens (=betere ondergrens)
Uit pure wanhoop ben ik dan maar alle mogelijke kalenders in een boom liggen uittekenen. Gegeven een keuze voor de eerste ronde (12), kies dan een mogelijke opvolger (uit 9) en kies dan de 3de ronde uit 6 mogelijkheden. Het is de boom van die 6 mogelijkheden die ik heb liggen uittekenen voor een kalender die begint met AB CD AC BD.

Ik kreeg uiteindelijk 44 mogelijke kalenders die beginnen met AB CD AC BD. Gesteld dat dit het geval is voor alle andere kalenders in de boom, krijgen we 12*9*44 = 4752 mogelijke kalenders.

Experimenten
Uiteindelijk gaan we dan maar voor de grovere middelen.
We laten 10 000 mieren 50 keer kalenders laten opstellen.

Zo hebben we maximaal 4759 unieke kalenders gevonden. Onze striktere bovengrens is dus geen bovengrens maar een betere ondergrens te noemen.

6 ploegen

Striktere (iets minder na´eve) bovengrens
Volgens dezelfde redenering als voor 4 ploegen krijgen we 5*6 mogelijke wedstrijden (30), waarbij er (5*6)*(4*3)*(2*1) / (3!) = 120 paren gevormd kunnen worden die elk een ronde voorstellen. Een selectie van 10 van deze rondes vormt dan een kalender. Per keuze van een ronde vallen er juist 6 wedstrijden weg die niet meer gespeeld mogen worden. Er vallen dus een aantal rondes weg die gecombineerd waren met deze 6 wedstrijden: 6*(4*3)*(2*1) / (3!) = 144 = 24. Opgelet, dit aantal verminderd naarmate er meer rondes gekozen werden. Na ronde 3 neem ik 2/3 van het vorige aantal rondes.

1 2 3 4 5 6 7 8 9 10
120 * 96 * 72 * 48 * 32 * 21 * 14 * 9 * 6 * 4

Dit is nogal groot (8^13).
Valid XHTML 1.0 Transitional :: Valid CSS :: Powered by Wikka Wakka Wiki 1.1.6.2
Page was generated in 0.0134 seconds