Vollständigesturnier: Lösungsalgorithmus bzw. mindestens eine Lösung für folgendes Problem gesucht |
16.10.2017, 12:33 | Auf diesen Beitrag antworten » | |||||
grohfuda | Vollständigesturnier: Lösungsalgorithmus bzw. mindestens eine Lösung für folgendes Problem gesucht Liebe Forumsteilnehmer, ich bin auf der Suche nach einem Lösungsalgorythmus oder wenigstens einer einzelnen Lösung für ein vollständiges Turnier. Auch wenn ich die Lösung eigentlich für etwas anderes brauche (Brettspielanalyse), möchte ich das Problem an einem anschaulichen Bespiel erläutern: Nehmen wir einmal an 12 Hasen wollen über den Frühling bis Sommer ein vollständiges Wettlauf-Turnier mit Wellläufen gegeneinander bestreiten. Mangels Platz können immer nur 4 Hasen gleichzeitig rennen. Also wird im Laufe des Sommers jeder Hase mit allen Kombinationen von jeweils 3 anderen Hasen ein Rennen absolvieren: H1, H2, H3, H4 H1, H2, H3, H5 H1, H2, H3, H6 [...] H9, H10, H11, H12 Die Anzahl der möglichen Kombinationen beträgt 12! / (8! x 4!) = 495 (bzw. 135 pro Hase) Nun sollen aber folgende Randbedingungen an das Turnier erfüllt sein: 1) Es sollen niemals die selben 4 Hasen ein zweites mal gegeneinander Laufen (2 bzw. 3 Hasen sind kein Problem), das heißtz.B. das Rennen H1, H2, H3, H4 darf es nur einmal geben. 2) Es werden jeden Tag genau 3 Rennen gestartet, wobei jeder Hase genau ein Rennen pro Tag absolviert. (Hierbei ist es egal in welchem der Tagesrennen jeder Hase jewils startet, auch die Bahnnummer ist nicht von Bedeutung. Frage 1) Wie kann hier eine Lösung aussehen? Ich vermute mal, dass das Ganze mit Backtracking lösbar ist (falls es eine Lösung gibt), leider reichen hier meine Programmierfähigkeiten nicht aus... Randbemerkung: Für 8 Hasen und 2 Rennen ist die Lösung trivial. Man nehme ein beliebiges Hasenrennen und die übrigen Hasen laufen im zweiten. Dieser Ansatz hat mich aber hier nicht weitergebracht. Frage 2) Existiert eine solche Lösung auch für 16 Hasen und 4 Rennen mit 4 Hasen bzw. 15 Hasen und 3 Rennen mit 5 Hasen? Viele Dank im Voraus. grohfuda |
|||||
|
||||||
16.10.2017, 18:01 | Auf diesen Beitrag antworten » | |||||
eulerscheZahl | Letztendlich läuft das auf ein Independent Set Problem hinaus, wobei die Kanten unmögliche Paarungen sind, also solche mit doppelten Rennen. Mein Programm schafft das und 8 Hasen und 2 Rennen in Sekundenbruchteilen, aber bei 12 und 3 habe ich es abgebrochen. Die Erkennung einer ungültigen Paarung kann man mit einer Lookup Table beschleunigen, aber ich glaube nicht, dass das reicht.
|
|||||
16.10.2017, 19:45 | Auf diesen Beitrag antworten » | |||||
Karlito | Verstehe ich es richtig, dass es eigentlich recht einfach ist, die 4er-Gruppen zu ermitteln, das Problem aber darin besteht, pro Tag 3 Rennen zu machen wobei ein Hase nie 2 mal an einem Tag rennen darf? Gruß, Karlito |
|||||
16.10.2017, 21:39 | Auf diesen Beitrag antworten » | |||||
eulerscheZahl | Ja, oder dass du an zwei Tagen das selbe Rennen aus 4 Hasen hast. Die einzelnen Tage zu ermitteln geht noch recht flott, für die gegebenen Werte (12 Hasen, 3 Rennen) könne ich auf 5775 Möglichkeiten für einen einzelnen Tag. Aber dann muss man davon 165 Tage auswählen, sodass kein Rennen doppelt ist. Wird wohl auf einen LP Solver hinauslaufen. |
|||||
Anzeige | ||||||
|
||||||
16.10.2017, 22:02 | Auf diesen Beitrag antworten » | |||||
Karlito | Ich würde einen genetischen Algorithmus probieren. Damit schonmal rumgespielt? Wäre eine Premiere für mich. Kennst Du Gegenargumente? Gruß, Karlito |
|||||
17.10.2017, 17:26 | Auf diesen Beitrag antworten » | |||||
eulerscheZahl | Ein randomisierter Ansatz könnte klappen. Hängt davor ab, wie viele Lösungen es gibt. Die einzige zu finden wird schwer, da bist du mit Bruteforce evtl sogar besser beraten. Meine Masterarbeit geht auch in die Richtung, aber nicht für Hasenrennen. CodinGame ist eine gute Anlaufstelle, um damit herumzuspielen. Hier sind soweit ich weiß alles randomisierte Algorithmen (Monte Carlo, genetische Algorithmen). Die finden ganz gute Züge. |
|||||
17.10.2017, 22:31 | Auf diesen Beitrag antworten » | |||||
Karlito | OK. Wenn ich am WE Zeit finde, probiere ich mal einen Lösungsversuch mit einem evolutionären Algorithmus. Gruß, Karlito |
|||||
22.10.2017, 18:27 | Auf diesen Beitrag antworten » | |||||
grohfuda | Würde es helfen (bzw. das Programm beschleunigen), wenn man festlegt, das Hase 1 immer im ersten Rennen des Tages läuft? Viele Grüße grohfuda |
|||||
22.10.2017, 23:19 | Auf diesen Beitrag antworten » | |||||
Karlito | Nicht wirklich. Wenn man systematisch nach einer Lösung sucht, würde man eh damit beginnen. Gruß, Karlito |
|