Eine komplexe Frage?
mir steht folgender spielplan zur verfügung:
1. Spieltag
Gladbach - Leverkusen
Dortmund - Frankfurt
Leipzig - Bochum
Hoffenheim - Hertha
Freiburg - Stuttgart
Augsburg - Hannover
Wolfsburg - München
Mainz - Union
Hamburg - Heidenheim
2. Spieltag
Leverkusen - Leipzig
Stuttgart - Mainz
München - Freiburg
Frankfurt - Hoffenheim
Heidenheim - Augsburg
Hannover - Dortmund
Union - Hamburg
Bochum - Gladbach
Hertha - Wolfsburg
3. Spieltag
Leipzig - Union
Dortmund - Heidenheim
Hoffenheim - Leverkusen
Freiburg - Bochum
Augsburg - Hamburg
Wolfsburg - Frankfurt
Mainz - Hannover
Gladbach - Stuttgart
Hertha - München
4. Spieltag
Leverkusen - Wolfsburg
Stuttgart - Dortmund
Frankfurt - Gladbach
Heidenheim - Freiburg
Hannover - München
Augsburg - Mainz
Union - Hoffenheim
Bochum - Hertha
Hamburg - Leipzig
5. Spieltag
München - Leverkusen
Leipzig - Augsburg
Dortmund - Bochum
Hoffenheim - Hannover
Freiburg - Hamburg
Wolfsburg - Stuttgart
Mainz - Heidenheim
Gladbach - Union
Hertha - Frankfurt
6. Spieltag
Leverkusen - Hertha
Stuttgart - Hoffenheim
Frankfurt - München
Heidenheim - Leipzig
Hannover - Freiburg
Augsburg - Gladbach
Union - Dortmund
Bochum - Wolfsburg
Hamburg - Mainz
7. Spieltag
Leverkusen - Frankfurt
München - Stuttgart
Dortmund - Hamburg
Hoffenheim - Bochum
Freiburg - Augsburg
Wolfsburg - Hannover
Mainz - Leipzig
Gladbach - Heidenheim
Hertha - Union
8. Spieltag
Stuttgart - Hertha
Leipzig - Freiburg
Heidenheim - Hoffenheim
Hannover - Leverkusen
Augsburg - Dortmund
Mainz - Gladbach
Union - Frankfurt
Bochum - München
Hamburg - Wolfsburg
9. Spieltag
Leverkusen - Stuttgart
München - Union
Dortmund - Leipzig
Frankfurt - Bochum
Hoffenheim - Hamburg
Freiburg - Mainz
Wolfsburg - Augsburg
Gladbach - Hannover
Hertha - Heidenheim
10. Spieltag
Stuttgart - Frankfurt
Leipzig - Gladbach
Heidenheim - Wolfsburg
Hannover - Hertha
Augsburg - Hoffenheim
Mainz - Dortmund
Union - Freiburg
Bochum - Leverkusen
Hamburg - München
11. Spieltag
Leverkusen - Heidenheim
Stuttgart - Bochum
München - Augsburg
Dortmund - Freiburg
Frankfurt - Hannover
Hoffenheim - Leipzig
Wolfsburg - Union
Gladbach - Hamburg
Hertha - Mainz
12. Spieltag
Leipzig - Wolfsburg
Dortmund - München
Heidenheim - Frankfurt
Hannover - Stuttgart
Freiburg - Gladbach
Augsburg - Bochum
Mainz - Hoffenheim
Union - Leverkusen
Hamburg - Hertha
13. Spieltag
Leverkusen - Hamburg
Stuttgart - Union
München - Heidenheim
Frankfurt - Augsburg
Hoffenheim - Freiburg
Wolfsburg - Mainz
Gladbach - Dortmund
Bochum - Hannover
Hertha - Leipzig
14. Spieltag
Leipzig - Frankfurt
Dortmund - Hoffenheim
Heidenheim - Stuttgart
Freiburg - Wolfsburg
Augsburg - Leverkusen
Mainz - München
Gladbach - Hertha
Union - Bochum
Hamburg - Hannover
15. Spieltag
Leverkusen - Freiburg
Stuttgart - Hamburg
München - Leipzig
Frankfurt - Mainz
Hoffenheim - Gladbach
Hannover - Union
Wolfsburg - Dortmund
Bochum - Heidenheim
Hertha - Augsburg
16. Spieltag
Leipzig - Hannover
Dortmund - Leverkusen
Hoffenheim - Wolfsburg
Heidenheim - Union
Freiburg - Hertha
Augsburg - Stuttgart
Mainz - Bochum
Gladbach - München
Hamburg - Frankfurt
17. Spieltag
Leverkusen - Mainz
Stuttgart - Leipzig
München - Hoffenheim
Frankfurt - Freiburg
Hannover - Heidenheim
Wolfsburg - Gladbach
Union - Augsburg
Bochum - Hamburg
Hertha - Dortmund
er beinhaltet 18 mannschaften, allerdings sollst du den spielplan so abändern, dass zwei weiter man schaften noch dazu kommen sollen, sie sollen wie jede andere mannschaft auch einmal gegen jede andere mannschaft spielen. nicht mehr nicht weniger. dementsprechen kommen statt 17 spieltage aich 19 spieltage zusammen. die zwei mannschaften heißen köln und schalke. WICHTIG: ändere den gegebenen spielplane so wenig wie möglich ab
WICHTIG: ändere den gegebenen spielplane so wenig wie möglich ab
was soll das GENAU bedeuten ?
dass die paarungen an den jeweiligen spieltagen nicht stark abweichen sollen, also Gladbach - Leverkusen sollte wenn möglich auch am 1. Spieltag stattfinden, aber nur wen möglich
2 Antworten
Es ist ratsam zunächst eine Dreiecksmatrix über die 17 Spielpläne anzulegen.
Dann erweitert man diese Dreiecksmatrix um zwei Spalten und zwei Zeilen und verschiebt jeweils ein einziges Spiel in eine der beiden neuen Spalten. Als nächstes nimmt man den jeweils anderen neuen Partner, Köln bzw. Schalke, und generiert das zusätzliche 10. Spiel im Spielplan. Wenn man das 17 mal durchdekliniert hat, werden die 20 frei gewordenen Plätze in der Dreiecksmatrix mit den Einträgen für die Spielpläne des 18. und 19. Tages besetzt.
Auf diese Weise wurden folgende Spielpläne gewonnen.
Habe meinen Fehler gesehen und arbeite gerade an der Korrektur
was denkst du ungefähr, wann deine korrektur fertig sein wird? (ohne dich jetzt stressen zu wollen)
Kein Witz. Ich arbeite immer noch daran. Es ist wirklich ein komplexes Problem. Und es muss ein wenig Software programmiert werden. Ohne dem ist dieses Problem nicht zu knacken. Leider kann ich nicht durchgehend daran arbeiten. Immer nur, wenn meine Frau mich lässt. Und über das Wochenende bekomme ich Besuch. Vielleicht bis Samstag, den 20.07. sonst Dienstag, der 23.07.
Die Sache ist komplexer als ich dachte; aber hoch interessant. Ich habe bisher so eine Art Kombinations-Explorer geschrieben. Der erzeugt mir alle möglichen Spieltagskombinationen, von denen man mit bestimmten Regeln eine Untermenge bilden muss. Bei 20 Mannschaften müssen dabei rund 650 Mio Kombinationen durchsucht werden. Bei 18 Mannschaften aber nur 34 Mio. Leider gestaltet sich der Suchalgorithmus nicht so ganz trivial. Ich mache Versuche mit 8 bzw. 10 Mannschaften und habe leider festgestellt, dass die Gewinnung eines Erweiterungsspielplans von 8 Mannschaften auf 10 Mannschaften bereits mehr Klimmzüge erfordert als anfangs gedacht. Sobald aber die kleine Nummer läuft, läuft auch die große Nummer, abgesehen von möglichen Laufzeitproblemen. Zwischendurch muss ich aber auch meine Frau bei Laune halten. Und heute Nachmittag sind wir zu einer Grillparty eingeladen. Ich bleibe dran.
Wow, klingt auch sehr interessant. Ich kann aber auch gar nicht oft genug dir für die Mühe danken und die Zeit die du dafür aufopferst. Vielen Dank.
Ich melde, dass ich ein gutes Stück voran gekommen bin. Jetzt kommt eine mindestens 2wöchige Urlaubszeit. In dieser Zeit komme ich noch seltener zu dieser komplexen Frage. Aber soviel ist schon mal sicher, dass der Zugang zur Lösung in dieser Dreieckmatrix liegt. Habe aber leider noch keinen effizienten Besetzungsalgorithmus gefunden. Die Software, alles in Octave geschrieben, stellt zwar einen brute force Angriff auf das Problem dar. Damit sie aber auch 20 Vereine wuppen kann, muss ich noch besondere Klimmzüge unternehmen. Ich bleibe dran.
Alles klar! Nochmals vielen Dank für deine Mühe und weiter so!
Heute habe ich zum ersten Mal eine sichere Methode gefunden um kollisionsfreie Lösungen zu erzeugen. Einfach ist es nicht. Aber es funktioniert. Nun muss ich das ganze noch auf die Größe von 20 Vereinen hochskalieren. Bist Du nur an einer Lösung interessiert oder auch an der Methode?
Hi, danke erstmal für deine Rückmeldung.
Tatsächlich bin ich an beiden interessiert, da mich das Thema jetzt auch sehr gepackt hat
Gestern bin ich einen entscheidenden Schritt voran gekommen. Es führt kein Weg daran vorbei rund 650 Mio Kombinationen durchzuscannen. Das Programm dafür steht. Der Scan dauert 5 Tage. Ich werde das Programm jetzt noch in der Weise optimieren, dass es jederzeit unterbrochen werden kann und wieder neu gestartet werden kann um dann an der unterbrochenen Stelle weiter zu machen. Nicht ganz trivial wenn Schleifen enthalten sind, die durch rekursive Programmaufrufe realisiert wurden. Nur auf diese Weise kann ich mich vor unerwarteten Programmabstürzen schützen. Andernfalls müsste ich ja immer erst fünf Tage warten um zu schauen, ob es funktioniert hat oder nicht.
Jetzt endlich läuft der Scan über 650 Mio Tageskombinationen. Es hat etwas Mühe gekostet das Programm einigermassen stabil zu bekommen. Jetzt heisst es fünf Tage auf die Ernte zu warten.
Ich glaube es wird Zeit für einen Zwischenbericht. Der Scan über 650 Mio Tageskombinationen ist längst gelaufen. Der Laptop meiner Frau, den sie eh selten braucht ist 5 Tage und 5 Nächte durchgelaufen. Die Ausbeute beträgt genau 401 Tageskombinationen. Der grobe Filter hat anscheinend funktioniert. Nun muss ich aus dieser Edelmenge die 19 gesuchten Tageskombinationen noch herausfiltern. Anfangs dachte ich, dass ich das "von Hand" erledigen kann. Das hat sich aber als zu mühsam und fehlerträchtig erwiesen. Was mich dazu nötigt einen zweiten Filter zu programmieren. Wobei sich herausgestellt hat, dass das auch dieses Programm nicht so en passent gemacht werden kann. Auch hier müssen alle Register der Softwareentwicklung gezogen werden.
Unglaublich, dass du so hartnäckig bist und immer noch dran bleibst. Nochmals vielen Dank für deine Mühe und sag bescheid wenn du weitere Ergebnisse hast.
Hallo, ich bins mal wieder, gibt es mittlweile ein Update?
verdammt, bei den letzten beiden spieltage ist dir ein fehler unterlaufen. union spielt am 18. spieltag zweimal und mainz spielt am 19. spieltag zweimal
- Gladbach - Leverkusen
- Dortmund - Frankfurt
- Leipzig - Bochum
- Hoffenheim - Hertha
- Freiburg - Stuttgart
- Augsburg - Hannover
- Wolfsburg - München
- Mainz - Union
- Hamburg - Heidenheim
- Köln - Schalke
- Leverkusen - Leipzig
- Stuttgart - Mainz
- München - Freiburg
- Frankfurt - Hoffenheim
- Heidenheim - Augsburg
- Hannover - Dortmund
- Union - Hamburg
- Bochum - Gladbach
- Hertha - Wolfsburg
- Schalke - Köln
- Leipzig - Union
- Dortmund - Heidenheim
- Hoffenheim - Leverkusen
- Freiburg - Bochum
- Augsburg - Hamburg
- Wolfsburg - Frankfurt
- Mainz - Hannover
- Gladbach - Stuttgart
- Hertha - München
- Köln - Schalke
- Leverkusen - Wolfsburg
- Stuttgart - Dortmund
- Frankfurt - Gladbach
- Heidenheim - Freiburg
- Hannover - München
- Augsburg - Mainz
- Union - Hoffenheim
- Bochum - Hertha
- Hamburg - Leipzig
- Schalke - Köln
- München - Leverkusen
- Leipzig - Augsburg
- Dortmund - Bochum
- Hoffenheim - Hannover
- Freiburg - Hamburg
- Wolfsburg - Stuttgart
- Mainz - Heidenheim
- Gladbach - Union
- Hertha - Frankfurt
- Köln - Schalke
- Leverkusen - Hertha
- Stuttgart - Hoffenheim
- Frankfurt - München
- Heidenheim - Leipzig
- Hannover - Freiburg
- Augsburg - Gladbach
- Union - Dortmund
- Bochum - Wolfsburg
- Hamburg - Mainz
- Schalke - Köln
- Leverkusen - Frankfurt
- München - Stuttgart
- Dortmund - Hamburg
- Hoffenheim - Bochum
- Freiburg - Augsburg
- Wolfsburg - Hannover
- Mainz - Leipzig
- Gladbach - Heidenheim
- Hertha - Union
- Köln - Schalke
- Stuttgart - Hertha
- Leipzig - Freiburg
- Heidenheim - Hoffenheim
- Hannover - Leverkusen
- Augsburg - Dortmund
- Mainz - Gladbach
- Union - Frankfurt
- Bochum - München
- Hamburg - Wolfsburg
- Schalke - Köln
- Leverkusen - Stuttgart
- München - Union
- Dortmund - Leipzig
- Frankfurt - Bochum
- Hoffenheim - Hamburg
- Freiburg - Mainz
- Wolfsburg - Augsburg
- Gladbach - Hannover
- Hertha - Heidenheim
- Köln - Schalke
- Stuttgart - Frankfurt
- Leipzig - Gladbach
- Heidenheim - Wolfsburg
- Hannover - Hertha
- Augsburg - Hoffenheim
- Mainz - Dortmund
- Union - Freiburg
- Bochum - Leverkusen
- Hamburg - München
- Schalke - Köln
- Leverkusen - Heidenheim
- Stuttgart - Bochum
- München - Augsburg
- Dortmund - Freiburg
- Frankfurt - Hannover
- Hoffenheim - Leipzig
- Wolfsburg - Union
- Gladbach - Hamburg
- Hertha - Mainz
- Köln - Schalke
- Leipzig - Wolfsburg
- Dortmund - München
- Heidenheim - Frankfurt
- Hannover - Stuttgart
- Freiburg - Gladbach
- Augsburg - Bochum
- Mainz - Hoffenheim
- Union - Leverkusen
- Hamburg - Hertha
- Schalke - Köln
- Leverkusen - Hamburg
- Stuttgart - Union
- München - Heidenheim
- Frankfurt - Augsburg
- Hoffenheim - Freiburg
- Wolfsburg - Mainz
- Gladbach - Dortmund
- Bochum - Hannover
- Hertha - Leipzig
- Köln - Schalke
- Leipzig - Frankfurt
- Dortmund - Hoffenheim
- Heidenheim - Stuttgart
- Freiburg - Wolfsburg
- Augsburg - Leverkusen
- Mainz - München
- Gladbach - Hertha
- Union - Bochum
- Hamburg - Hannover
- Schalke - Köln
- Leverkusen - Freiburg
- Stuttgart - Hamburg
- München - Leipzig
- Frankfurt - Mainz
- Hoffenheim - Gladbach
- Hannover - Union
- Wolfsburg - Dortmund
- Bochum - Heidenheim
- Hertha - Augsburg
- Köln - Schalke
- Leipzig - Hannover
- Dortmund - Leverkusen
- Hoffenheim - Wolfsburg
- Heidenheim - Union
- Freiburg - Hertha
- Augsburg - Stuttgart
- Mainz - Bochum
- Gladbach - München
- Hamburg - Frankfurt
- Schalke - Köln
- Leverkusen - Mainz
- Stuttgart - Leipzig
- München - Hoffenheim
- Frankfurt - Freiburg
- Hannover - Heidenheim
- Wolfsburg - Gladbach
- Union - Augsburg
- Bochum - Hamburg
- Hertha - Dortmund
- Köln - Schalke
- Köln - Gladbach
- Schalke - Dortmund
- Hamburg - Leipzig
- Heidenheim - Augsburg
- Hoffenheim - Hertha
- Wolfsburg - München
- Mainz - Union
- Hannover - Freiburg
- Stuttgart - Bochum
- Frankfurt - Leverkusen
- Köln - Wolfsburg
- Schalke - München
- Leipzig - Union
- Hamburg - Dortmund
- Heidenheim - Stuttgart
- Hoffenheim - Bochum
- Augsburg - Mainz
- Hannover - Frankfurt
- Freiburg - Gladbach
- Hertha - Leverkusen
- Gladbach - Leverkusen
- Dortmund - Frankfurt
- Leipzig - Bochum
- Hoffenheim - Hertha
- Freiburg - Stuttgart
- Augsburg - Hannover
- Wolfsburg - München
- Mainz - Union
- Hamburg - Heidenheim
- Köln - Schalke
- Gladbach - Dortmund
- Leverkusen - Köln
- Frankfurt - Leipzig
- Bochum - Hoffenheim
- Hertha - Freiburg
- Stuttgart - Augsburg
- Hannover - Wolfsburg
- München - Mainz
- Union - Hamburg
- Heidenheim - Schalke
- Gladbach - Frankfurt
- Dortmund - Bochum
- Leverkusen - Hoffenheim
- Leipzig - Hertha
- Freiburg - Hannover
- Augsburg - Mainz
- Wolfsburg - Union
- Köln - Hamburg
- Stuttgart - Schalke
- München - Heidenheim
- Gladbach - Bochum
- Dortmund - Leverkusen
- Frankfurt - Hertha
- Hoffenheim - Freiburg
- Leipzig - Augsburg
- Hannover - Union
- Mainz - Stuttgart
- Hamburg - Wolfsburg
- Heidenheim - Köln
- Schalke - München
- Gladbach - Hoffenheim
- Dortmund - Leipzig
- Frankfurt - Augsburg
- Bochum - Hannover
- Freiburg - Mainz
- Leverkusen - Union
- Hertha - Hamburg
- Wolfsburg - Schalke
- Köln - Stuttgart
- München - Heidenheim
- Gladbach - Hertha
- Dortmund - Freiburg
- Leverkusen - Augsburg
- Leipzig - Hannover
- Hoffenheim - Mainz
- Frankfurt - Wolfsburg
- Union - Köln
- Stuttgart - Hamburg
- Schalke - Bochum
- Heidenheim - München
- Gladbach - Freiburg
- Dortmund - Augsburg
- Leverkusen - Hannover
- Leipzig - Mainz
- Hoffenheim - Union
- Hertha - Wolfsburg
- Köln - Stuttgart
- Hamburg - Schalke
- Bochum - Frankfurt
- München - Heidenheim
- Gladbach - Augsburg
- Dortmund - Hannover
- Frankfurt - Hoffenheim
- Freiburg - Wolfsburg
- Leipzig - Union
- Mainz - Schalke
- Köln - Hamburg
- Stuttgart - Bochum
- Hertha - Leverkusen
- Heidenheim - München
- Gladbach - Hannover
- Dortmund - Mainz
- Leverkusen - Wolfsburg
- Leipzig - Freiburg
- Hoffenheim - Köln
- Frankfurt - Stuttgart
- Augsburg - Union
- Hamburg - Schalke
- Bochum - Hertha
- München - Heidenheim
- Gladbach - Wolfsburg
- Dortmund - Köln
- Frankfurt - Hoffenheim
- Leipzig - Augsburg
- Freiburg - Mainz
- Hannover - Schalke
- Bochum - Hamburg
- Union - Stuttgart
- Hertha - Leverkusen
- Heidenheim - München
- Gladbach - Union
- Dortmund - Stuttgart
- Leverkusen - Heidenheim
- Leipzig - Wolfsburg
- Hoffenheim - Freiburg
- Frankfurt - Augsburg
- Köln - Schalke
- Mainz - Bochum
- Hertha - Hamburg
- München - Hannover
- Gladbach - Mainz
- Dortmund - Köln
- Leverkusen - Schalke
- Leipzig - Bochum
- Freiburg - Hoffenheim
- Hannover - Wolfsburg
- Frankfurt - Stuttgart
- Augsburg - Hamburg
- Union - Hertha
- Heidenheim - München
- Gladbach - Leipzig
- Dortmund - Hoffenheim
- Leverkusen - Augsburg
- Freiburg - Hertha
- Bochum - Wolfsburg
- Stuttgart - Schalke
- Köln - Hamburg
- Mainz - Union
- Hannover - Frankfurt
- München - Heidenheim
- Gladbach - Heidenheim
- Dortmund - Schalke
- Leverkusen - Köln
- Leipzig - Hamburg
- Hoffenheim - Augsburg
- Frankfurt - Union
- Freiburg - Mainz
- Hannover - Bochum
- Stuttgart - Hertha
- Wolfsburg - München
- Gladbach - Schalke
- Dortmund - Heidenheim
- Leverkusen - Hamburg
- Leipzig - Mainz
- Hoffenheim - Union
- Freiburg - Augsburg
- Frankfurt - Köln
- Hannover - Stuttgart
- Bochum - Wolfsburg
- Hertha - München
- Gladbach - Köln
- Dortmund - Hamburg
- Leverkusen - Schalke
- Leipzig - Stuttgart
- Hoffenheim - Mainz
- Freiburg - Frankfurt
- Augsburg - Hertha
- Union - Bochum
- Hannover - Wolfsburg
- Heidenheim - München
- Gladbach - Stuttgart
- Dortmund - Mainz
- Leverkusen - Hertha
- Leipzig - Köln
- Hoffenheim - Augsburg
- Frankfurt - Wolfsburg
- Freiburg - Schalke
- Union - Hannover
- Bochum - Heidenheim
- Hamburg - München
- Gladbach - Augsburg
- Dortmund - Schalke
- Leverkusen - Freiburg
- Leipzig - Hertha
- Hoffenheim - Wolfsburg
- Frankfurt - Mainz
- Köln - Bochum
- Union - Stuttgart
- Hannover - Hamburg
- Heidenheim - München
- Gladbach - Heidenheim
- Dortmund - Köln
- Leverkusen - Hoffenheim
- Leipzig - Schalke
- Freiburg - Augsburg
- Hannover - Union
- Bochum - Stuttgart
- Mainz - Wolfsburg
- Hertha - Hamburg
- München - Frankfurt
ich liebe dich, du weißt gar nicht wie sehr du mir damit hilfst. Und vielen Dank, dass du dir die Zeit dafür genommen hast