Ich versuche einen Sportliga-Planer zu erstellen. Ich habe Probleme, einen Algorithmus zu identifizieren, mit dem ich jeden Steckplatz effizient ausfüllen kann.
Beispieldaten zum Erstellen des Zeitplans wären:
- 10 Teams
- Jedes Team spielt 1 Mal gegeneinander (insgesamt 45 Spiele erforderlich)
- Jedes Team spielt nicht mehr als 1 Mal pro Tag
- Bei meinen Tests verwende ich 9 Tage mit 5 Slots pro Tag.
Kombitabelle (enthält 45 Combos)
ID
Team1ID
Team2ID
bitAssigned
Zeitplantabelle (enthält 45 Zeitfenster)
ScheduleID
HomeTeamID
AwayTeamID
GameDate
GameTime
Momentan füllen meine vorhandenen Prozeduren ungefähr 90% der Slots und lassen 10% meiner Slots für einen Planungskonflikt leer, der auf den oben genannten Regeln basiert.
Ich durchlaufe meine Zeitplantabelle in aufsteigender Reihenfolge von Datum und Uhrzeit.
Mein erster Slot könnte Samstag um 8 Uhr sein.
Ich frage eine Liste von Teams ab, die noch nicht geplant wurden. Ich mache dann eine Reihe möglicher Kombinationen dieser Teams. Ich verwende dieses Array dann, um 1 zufälligen Datensatz aus meiner Kombinationstabelle aus Kombinationen zu ziehen, die noch nicht geplant wurden, und platziere diese Teams auf dem Zeitplan. Ich habe diese Kombination dann wie verwendet eingestellt.
Ich wiederhole die Schleife immer wieder und jedes Mal, wenn meine Liste der verfügbaren Teams kleiner wird und mein Array dadurch auch kleiner wird.
Ich stelle fest, dass einige Tage gut verlaufen, und an anderen Tagen haben meine letzten beiden verbleibenden Teams bereits in einer Vorwoche gespielt, sodass sie nicht wieder in den Zeitplan aufgenommen werden.
Das einzige, was ich bisher noch nicht versucht habe, ist, die Konflikttage zurückzusetzen und erneut zu versuchen, um zu sehen, ob ich bessere Platzierungen bekomme.
Hat jemand irgendwelche Vorschläge?
quelle
Antworten:
Hier ist ein Algorithmus, den ich selbst erfunden habe. Ich weiß nicht, ob es bereits existiert oder tatsächlich die Round-Robin-Implementierung ist:
Im Grunde fängst du mit an
und halten Sie die 1 immer in der gleichen Position und drehen Sie den Rest.
Auf diese Weise erhalten Sie immer einen Zeitplan mit einzigartigen Spielen. Dies ist extrem einfach zu implementieren und lässt sich mit einer beliebigen Anzahl von Gegnern skalieren, auch wenn diese ungleichmäßig sind. Wenn Sie eine ungerade Anzahl von Gegnern haben, platzieren Sie einfach kein Team auf Position 1 und es hat eine freie Runde.
quelle
Ich denke du machst es rückwärts. Beginnen Sie nicht mit der Zeitplantabelle, sondern mit einer Tabelle / einem Array / einer beliebigen Spielkombination (den 45 Spielen). Von dort aus ist es ein einfacher Vorgang, die Spiele einem Tag zuzuweisen, basierend auf einem Team, das nur einmal am Tag spielt. Und da Matchups nur einmal stattfinden (Team A spielt Team B nur einmal), ist die Planung einfach, da Sie nur sicherstellen müssen, dass das Matchup noch nicht stattgefunden hat (die Einträge sind auf diese Weise "eindeutig").
quelle
Ich habe unten den 10-Team-Single-Round-Robin-Zeitplan erstellt. Ich habe ungefähr 3 Minuten gebraucht.
Zeitplaninfo:
10 Teams - 1 Round Robin (nur die ersten 6 Wochen werden angezeigt)
Saisonstartdatum 06.01.15 - Enddatum 05.03.15
2 Spiele jeden Dienstag, 3 Spiele jeden Donnerstag, 5 Spiele jede Woche ohne Überspringdaten
Wir haben einen veralteten Honeywell-Mainframe-Computer verwendet und knapp 3 Jahre, um das Ganze zusammenzustellen. Nach dem Debuggen unserer Planungssoftware benötigte der Hauptrechner viele Stunden, um Millionen von Permutationen und Kombinationen zu durchsuchen und die ausgewogenen Muster für 4 bis 22 Teams zu berechnen und zu erstellen, nach denen wir suchten.
Es gibt keinen Algorithmus, der die allgemeinen Planungsprobleme löst, die mit Hunderten oder Tausenden verschiedener Arten von Ligen, Sportarten und potenziellen Situationen verbunden sind. Um dieses Problem zu lösen, haben wir einen anderen Ansatz zur Berechnung der Zeitpläne gewählt. Es beginnt mit der sehr komplexen Mathematik, um die richtigen Round-Robin-Team-Paarungen (Match-Ups) zu bestimmen, aber das war erst der Anfang. Andere Teile werden benötigt, um einen nützlichen, ausgewogenen Zeitplan zu erstellen, der veröffentlicht und verteilt werden kann. Spieler, Trainer, Eltern usw. müssen nicht nur wissen, gegen wen sie spielen . aber wo sie spielen ; was Zeit sie spielen ; wenn sie zu Hause oder Besucher sind ; und für viele Ligen eine Spielnummer .
Ich hoffe, dies hilft Ihnen und anderen zu verstehen, was wir 3 Jahre gebraucht haben, um herauszufinden.
quelle