[PHP] Wedstrijdprogramma optimaliseren mbt veldcapaciteit

[WaarAnders]

Ik probeer automatisch het wedstrijdprogramma van een paar poules te maken. Het aantal poules en het aantal teams daarin verschillen. (x teams per poule en y poules). Het maken van de poules is niet zo'n probleem. Dit heb ik gedaan door de verschillende teams in mysql te zetten met een eigen entry en per entry een poule_id.

De wedstrijden genereren is ook niet moeilijk (iedereen tegen iedereen uit de poule, maar niet tegen jezelf en wedstrijden die je al gehad hebt). Het moeilijke (voor mij dan) is om te zorgen dat alle teams tegen elkaar spelen in een bepaald aantal rondes (optimale hoeveelheid), dat de veld capaciteit dus optimaal gebruikt wordt.

Er moet rekening gehouden worden met:
-1 team kan maar 1 wedstrijd per ronde spelen
-1 team moet niet al zijn wedstrijden achter elkaar spelen (gevolg zou zijn dat het laatste team uit de poule een ochtend niks zit te doen. Het programma moet dus eerlijk verdeeld zijn over de dag (om maar een tijdsperiode te noemen).
-Veldcapaciteit (z)

De variabelen x,y en z zijn bekend (worden ingegeven door gebruiker). Ik wil het script dus laten uitzoeken wanneer een wedstrijd moet plaats vinden om zo efficient mogelijk om te gaan met de veldcapaciteit. Iemand enig idee hoe ik dit aan moet pakken? Na uren proberen (en achter concluderen dat mijn idee niet kon werken) kom ik er niet meer uit.

-Wedstrijden uit db halen, vervolgens random maken lost het probleem van 1 team, 1 wedstrijd per ronde niet op. Wel verdeeld het de wedstrijden.
-Per ronde uit de db halen en aanvullen met de volgende poule lost het probleem van spreiding niet op (en komt aan het einde van de dag niet goed uit).
Ik vermoed dat het een combinatie moet worden. Wie helpt me op weg?

Als er onduidelijkheden/vragen zijn hoor ik het wel.

[Infinitive]

Dit klinkt mij typisch als een linear programmeren probleem in de oren (of het ook als dusdanig geformuleerd kan worden is een andere vraag). Echter, dat is niet iets wat je even uit je losse pols schudt, dus tenzij je er wat van weet, zou ik niet in die richting gaan zoeken. Waarschijnlijk dat er ook een eenvoudigere mogelijkheid beschikbaar is.

Er zijn een aantal zaken in je vraagstelling die niet geheel duidelijk zijn, zoals een veldcapaciteit waar je het verder niet over hebt.

Wat in me op komt is dat je eerst alle mogelijkheden om paren van 2 te maken uit een verzameling ter groote van y enumereerd en vervolgens deze verzameling dusdanig sorteerd dat je veldcapaciteit optimaal is (ik weet niet of je dat met sortering kan oplossen, maar het is maar een idee).

[ Voor 4% gewijzigd door Infinitive op 19-09-2006 12:04 ]

[NMe]

Het ontwerpen van programma's en algoritmen mag in Software Engineering & Architecture besproken worden. Zie ook Waar hoort mijn topic?

PRG>>SEA

[WaarAnders]

ok, excuses voor dat

Die partijen van 2 zijn er en hebben een wedstrijd_id gekregen in een nieuwe tabel. Nu moet nog worden ingevuld in welke ronde deze partij gespeeld wordt.

Veldcapaciteit = aantal van die Wedstrijd_id's per ronde

Maar op welke manier selecteren?

[Verwijderd]

Zou je die uiteindelijke indeling niet gewoon aan de eindgebruiker overlaten?

Je kunt wel een hoop helpen (je weet welke teams, poules, wedstrijden er zijn, welke timeslots en velden) maar de uiteindelijke verdeling kun je m.i. beter aan een mens overlaten dan aan een algorithme.
Je kan die persoon wel een leuk en snel te gebruiken UI bieden om de boel in te delen, en eventueel een indelingsvoorstel doen, maar meer ook niet.

Problemen als "teams mogen nooit 2 wedstrijden achter elkaar spelen, behalve wanneer 't niet anders kan" en "team A begint om 9 uur, maar team A komt uit Appelscha, en 't tournooi is in Roosendaal, en vorig jaar waren ze er ook pas om half 11" zijn softwarematig nogal lastig om aan te pakken...

[MBV]

@Afterlife: tja, je kan natuurlijk overwegen om die automagische generatie eerst te laten doen, en dan op een slimme manier handmatig bijwerken (d.m.v. meer restricties of handmatige wisselingen).

@TS: Dit is duidelijk een van de NP-complete problemen, oftewel je kan niet (binnen redelijke tijd) het absolute maximum uitrekenen voor grotere getallen. Er zijn mooie zoek-algoritmen voor, maar als je van die theorie nog niets weet zou ik je aanraden om de gebruiker op een eenvoudige manier het schema te laten invullen. Een tip voor een algoritme ga ik je niet geven: ben nu bezig met het vak, en leraren bewaren de beste oplossing altijd voor het laatste

[joepP]

Of dit probleem NP-compleet is hangt sterk van de randvoorwaarden af.

Laten we beginnen met het maken van een perfecte indeling voor een enkele poule, wat feitelijk het basisprobleem van de TS is. Hiervoor kan je gebruik maken van een simpel trucje: de ketting. Dit is het makkelijkst uit te leggen met een oneven aantal teams. Je begint met de volgende configuratie:

code:

  5 -- 4       4 -- 3
 /     |      /     |
1      | ==> 5      | ==> ...
 \     |      \     |
  2 -- 3       1 -- 2

In de eerste ronde is team 1 vrij, speelt 2-5, en 4-3. Daarna draai je de ketting een slag door. In ronde twee speelt 1-4 en 2-3. Je herhaalt dit trucje nog drie maal om je volledige speelschema te krijgen. Bij een even aantal teams houd je een team uit de ketting, en laat je dat team tegen het vrije team spelen.

Jouw probleem is niet heel veel moeilijker. Je kan beginnen met het perfecte schema voor elke groep op te stellen. Dit schema zie je als een lange keten van wedstrijden, bijvoorbeeld 1-6, 2-5, 4-3, 1-4, 2-3, 5-6, etc. Nu moet je steeds afwisselend wedstrijden van verschillende poules achter elkaar zetten, zodat je de veldcapaciteit goed benut. Stel je hebt bijvoorbeeld vier poules A-D, met 4,4,5,5 teams en dus 6, 6, 10 en 10 wedstrijden. Dit kan je verdelen als (bijvoorbeeld) A, B, C, D, C, D, A, B, C, D, C, D, A, B, etc. In de meeste gevallen zul je nu weinig problemen hebben met je timeslots, en anders kan je nog handmatig iets omwisselen of een veld leeghouden.

Een alternatief is om te proberen zoveel mogelijk de wedstrijden uit dezelfde poule tegelijk te laten spelen. Dan ga je dus complete speelrondes inplannen in plaats van losse wedstrijden.

[jvdmeer]

Dit is bijna een off-topic reactie hier, maar ik heb een paar jaar lang zelf toernooi-indelingen gemaakt voor een redelijk toernooi (1 dag, 21 velden, 30 poules, ca 200 teams, 500 wedstrijden).
Daarbij had ik nog restricties dat elke jeugdteam geleidt wordt door een senior-speler (uit een seniorenteam) en dat deze twee (of eigenlijk 4 (ook voor de tegenpartij)) teams niet tegelijkertijd mochten spelen. Daarnaast moest elk seniorenteam ook nog voor 6 wedstrijden een scheidsrechter verzorgen. Deze te fluiten wedstrijden mochten natuurlijk niet samenvallen met te spelen wedstrijden, en er ook niet direct aan sluiten. Er moest hier dus minimaal een ronde tussen zitten. Daarnaast mocht men niet een wedstrijd van dezelfde vereniging fluiten.

Al deze restricties in acht genomen, heb ik overwogen om e.e.a. te automatiseren. Maar ik zag daar zoveel problemen in om dit netjes door de computer te laten oplossen, dat ik het handmatig heb gedaan.

En mijn ervaring is dat ik dit zonder ervaring met het handje deed in ongeveer 4 uur. Daar was dus niet tegenaan de programmeren. Bedenk dus altijd voordat je aan een algoritme begint hoeveel tijd het je gaat kosten en hoeveel het je oplevert.

In mijn geval van drie toernooien per jaar vond ik het niet rendabel.

Maar zoals ik al zei dit is een beetje off-topic.

[MBV]

maar lekker moeilijke algebra erop loslaten is toch veel leuker?

[WaarAnders]

De wedstrijden zijn ingedeeld. Nu moeten ze alleen nog in het schema gepland worden.

Ik zat zelf te denken aan het uit de database halen van het team dat het minste gespeeld heeft. Dat minste wordt bepaald door een kolom aantal wedstrijden waar je dus steeds 1 bij optelt als de wedstrijd ingepland is. Zwaar voor db maar het wordt niet vaak gebruikt en draait lekker op me eigen laptop.

[joepP]

Waarom misbruik je in godsnaam de database tijdens het maken van een indeling?

Alles lekker in het geheugen laden vanuit de database, daar de boel optimaliseren, en daarna weer terugschrijven. Volgens mij scheelt dat je een factor 1000 in performance, als het niet meer is...

[WaarAnders]

omdat het dan opgeslagen wordt, ook als het afgebroken wordt, bijvoorbeeld voor verbindingsproblemen

[MBV]

Als je je DBMS goed instelt, laadt hij al alles in het geheugen (mits dat past dus). Dan heb je het voordeel dat sommige dingen in databases beter zijn ontwikkeld dan in PHP