WisFaq!

Re: Re: Speelschema

JaDeX,

Bedankt voor je reactie. Kan niet verder, maar waardeer het zeer. Ben zelf begonnen met programmeren :-) Heb je voor mij nog de logica van toen. Twee keer het wiel uitvinden hoeft niet toch?

Erik

Erik van Loon
5-4-2018

Antwoord

Hallo Erik,

Het is snel te zien dat het schema met de gestelde eisen (12 teams, 12 ronden, elk team niet 2 keer tegen een ander team) niet uit te breiden is naar 12 ronden. Immers: elk team heeft maar 11 mogelijke tegenstanders, dus na maximaal 11 ronden loopt het spaak. Je zult dus wat water bij de wijn moeten doen.

Wat betreft de logica: het eenvoudigst programmeren is de 'brute force' methode. Hierbij worden systematisch alle mogelijkheden afgetast. Hier zitten dan ook overbodige berekeningen bij, zoals: stel dat er geen mogelijkheid is waarbij in de eerste ronde team A en team B tegen elkaar spelen. Dan heeft het geen zin om te onderzoeken of er een mogelijkheid is waarbij team C en team D tegen elkaar spelen. Immers, je had team C en team D ook team A en team B kunnen noemen. Echter, het inbouwen van allerlei slimmigheid om te bedenken of een bepaalde berekening wel of niet zinnig is, kost veel moeite, vergissingen, testruns enz. Bij zeer complexe problemen is dit noodzakelijk, omdat de rekentijd anders absurd lang kan worden. Bij een probleem als dit is een 'dom' brute force programma waarschijnlijk sneller klaar dan dat jij al die extra's in het programma hebt ingebouwd.

Een brute force programma zou als volgt kunnen worden opgebouwd:
Definieer een 12x12 matrix M. De rijen stellen de teams A t/m H voor, de kolommen geven de 12 ronden weer. Bij aanvang zijn alle elementen 0, dit betekent: er is nog geen spel (en geen tegenstander) toegekend. Uiteindelijk moeten de elementen het nummer van het te spelen spel weergeven.
Handig is om een tweede 12x12 matrix G (Gespeeld) te definiëren om bij te houden welke teams al tegen elkaar hebben gespeeld. De startwaarden zijn 0 (=nog niet tegen elkaar gespeeld).
We definiëren ook een variabele 'spelnummer'.

Uiteraard kunnen we in de eerste ronde spel 1 toekennen aan teams A en B, spel 2 aan C en D, spel 3 aan E en F enz. Dit doen we door de elementen M(A,1) en M(B,1) de waarde 1 te geven, M(C,1) en M(D,1) worden 2 enz.
(Het eerste element, het rijnummer, geef ik even met een letter aan zodat steeds duidelijk is dat het om een teamnummer gaat. In een programmeertaal is dit natuurlijk een getal).
In de matrix G zetten we G(1,2) en G(2,1) op 1, om aan te geven dat teams A en B tegen elkaar hebben gespeeld. Dit geldt ook voor G(3,4) en G(4,3), G(5,6) en G(6,5) enz.

Nu gaan we ronde 2 vaststellen. We zetten 'spelnummer=1' en zoeken twee teams waaraan we dit spel kunnen toekennen. Hiervoor tasten we de gehele kolom 2 af, en bekijken of aan deze voorwaarden wordt voldaan:

• Is M(A,2)=0? Ja: team A is dus nog vrij
  
• Is de gehele kolom M(A,*) ongelijk aan 1? Nee: M(A,1)=1, dus in de eerste ronde heeft team A spel 1 al gespeeld. We gaan door naar het volgende team (rij 2).
  
• Is M(B,2)=0? Ja: team B is dus nog vrij
  
• Is M(B,*)ongelijk aan 1? Nee: in de eerste ronde heeft team B spel 1 al gespeeld. We gaan door naar het volgende team (rij 3).
  
• Is M(C,2)=0? Ja: team C is dus nog vrij
  
• Is M(C,*) ongelijk aan 1? Ja: team C heeft spel 1 niet eerder gespeeld.
  
• Is één van de elementen M(*,2) gelijk aan 1? Nee: team C mag spel 1 spelen. We zetten M(C,2) op 1 en gaan door naar het volgende team (rij 4).
  
• Is M(D,2)=0? Ja: team D is dus nog vrij
  
• Is M(D,*) ongelijk aan 1? Ja: team D heeft spel 1 niet eerder gespeeld.
  
• Is één van de elementen M(*,2) gelijk aan 1? Ja: M(3,2)=1, dus team C speelt spel 1. Vervolgvraag: is G(3,4)=1? Ja: team D heeft eerder tegen team C gespeeld. We kunnen spel 1 niet toekennen aan team D. We gaan door naar het volgende team (rij 5)
  
• Is M(E,2)=0? Ja: team E is dus nog vrij
  
• Is M(E,*) ongelijk aan 1? Ja: team E heeft spel 1 niet eerder gespeeld.
  
• Is één van de elementen M(*,2) gelijk aan 1? Ja: M(3,2)=1, dus team C speelt spel 1. Vervolgvraag: is G(3,5)=1? Nee: team E heeft niet eerder tegen team C gespeeld. Aan alle voorwaarden is voldaan: team E mag spel 1 spelen. We zetten M(E,2) op 1. Ook zetten we G(3,5)=1 en G(5,3)=1, om te onthouden dat C en E tegen elkaar hebben gespeeld.

Wanneer het spelnummer minder is dan 6, verhogen we het spelnummer (spelnummer wordt 2) en herhalen de procedure, net zolang totdat spel 6 is toegekend.

Al snel zal dit vastlopen: Een bepaald spel kunnen we niet plaatsen. Dan moeten we van achter naar voren keuzes wissen. We annuleren het laatst gekozen team (bijbehorend element in M wordt weer 0). Als dit een tweede team bij een spel is, moeten we ook de bijbehorende elementen in de matrix G weer op 0 zetten. Vervolgens zoeken we vooruit naar een volgend team dat aan alle criteria voldoet.

Het kan zijn dat we alle wedstrijden in een bepaalde ronde moeten wissen. Dan gaan we terug naar de voorgaande ronde, en wissen daar het laatst gekozen team. Als alles netjes verloopt, zijn er uiteindelijk twee mogelijkheden:

• We komen tot een oplossing waarbij de gehele matrix M gevuld wordt, ons speelschema is klaar.
  Of:
  
• We moeten zoveel wissen, dat we helemaal terugkomen bij de eerste ronde. Dan is geen oplossing mogelijk en moeten bijvoorbeeld meer spellen beschikbaar komen (waarbij niet elk team elk spel speelt), of meer teams (waarbij niet elk team tegen elk ander team speelt), of minder ronden worden gespeeld (ook hier speelt niet ieder team tegen elk ander team)

Hopelijk lukt het hiermee. Zo niet, dan wil ik me wellicht op zo'n programmaatje storten, maar ik kan niet beloven dat ik hier binnenkort voldoende tijd voor heb. Je zou hoe dan ook eerst moeten aangeven op welke wijze de randvoorwaarden wat versoepeld kunnen worden, want -zoals eerder opgemerkt- zijn met de getelde eisen geen 12 ronden met 12 teams mogelijk.

Aanvulling (dankzij een mede-beantwoorder): op deze site vind je een heleboel oplossingen van gelijksoortige problemen. Wellicht zit er iets bruikbaars tussen:

• Social Golfer Problem

GHvD
10-4-2018