Die Mathe-Redaktion - 17.10.2019 13:00 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 776 Gäste und 18 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Numerik & Optimierung » Algorithmus für optimalen Spielplan
Druckversion
Druckversion
Antworten
Antworten
Autor
Kein bestimmter Bereich Algorithmus für optimalen Spielplan
flaming
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 29.11.2008
Mitteilungen: 13
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2008-11-29


Hallo miteinander,

dies ist mein erster Beitrag und sofort auch eine Frage - macht man eigentlich nicht, weiß ich und ich entschuldige mich dafür. Mir brennt aber etwas unter den Nägeln..

Mein Problem ist das Finden eines Algorithmus, der für eine frei wählbare Anzahl von Mannschaften n einen optimalen Spielplan ausgibt.

Nun gibt es hier im Äther diverse Algorithmen, die sich mit diesem Thema beschäftigen, jedoch sind alle, die ich ausprobiert habe, für ein einfaches Beispiel nicht so perfekt wie ein von Hand gestalteter - und das kann ja eigentlich nicht sein, oder?

Es geht in meinem Fall darum, dass ich
- nur ein Spielfeld zur Verfügung habe,
- alle Spiele an einem Tag stattfinden sollen und
- jedes Team möglichst lange Regenerationspausen zwischen den Spielen haben soll. Es soll auf jeden Fall vermieden werden, dass ein Team zweimal hintereinander spielt.

Für einen Spielplan mit n = 5 Teams wäre ein optimaler Spielplan im Sinne der Aufgabenstellung:
1-2
3-4
5-1
3-2
4-5
1-3
2-5
4-1
5-3
2-4

Ich habe trotz intensiver Suche keinen Algorithmus finden können, der mir diesen Spielplan ausgibt. Ab einer gewissen Anzahl von Mannschaften z. B. muss ich doch auch garantieren können, dass jedes Team mindestens zwei Spiele Pause hat. Ab welcher? Gibt es eine allgemeingültige Regel hierfür?

Wie kann ein Computer eine solche Aufgabe optimieren für n = 6.. 12?

In obigem Spielplan habe ich zwei Partien "verdreht", sprich die größere Zahl vor die kleinere geschrieben. Somit hat jedes Team je zweimal "Heimrecht", das soll hier aber zunächst nicht Teil der Aufgabe sein.



  Profil  Quote  Link auf diesen Beitrag Link
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1348
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2008-11-29


Hallo Flaming!

Willkommen auf dem Matheplaneten!
Die Aufgabe gehört in den Bereich der diskreten Optimierung.
Lösen kann man dieses Problem beispielsweise mit Branch&Bound oder Lokaler Suche.
de.wikipedia.org/wiki/Branch_and_Bound
de.wikipedia.org/wiki/Lokale_Suche

Für 5 Teams sucht man eine Reihenfolge (Permutation) der 10 Begegnungen, bei der die Nebenbedingung "keine Mannschaft spielt 2x hintereinander" erfüllt ist.
Die Bedingung "jede Mannschaft spielt 1x gegen jede andere" ist automatisch erfüllt.

Viele Grüße
Ronald




  Profil  Quote  Link auf diesen Beitrag Link
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1348
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2008-11-30


Hallo flaming!

Ab einer Größe von 7 Mannschaften gibt es 2 Spiele Pause pro Mannschaft.
Ein möglicher Plan ist:
     1     4
     2     7
     3     5
     4     6
     1     7
     2     5
     3     6
     4     7
     1     5
     2     6
     3     4
     5     7
     1     6
     2     3
     4     5
     6     7
     1     3
     2     4
     5     6
     3     7
     1     2
Gefunden mit der Heuristik lokale Suche.

Viele Grüße
Ronald



[Verschoben aus Forum 'Knobelecke' in Forum 'Numerik & Optimierung' von Delastelle]



  Profil  Quote  Link auf diesen Beitrag Link
flaming
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 29.11.2008
Mitteilungen: 13
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2008-12-01


Hallo Delastelle,

vielen Dank für diese Info! Ich war mir fast sicher, dass es mit 7 Teams möglich sein muss, immer mindestens 2 Spiele Pause zu haben.

Was bedeutet "Heuristik lokale Suche"? Wie implementiere ich einen Algorithmus, der mir diesen Spielplan ausspuckt? Wenn es eine lineare Optimierungsaufgabe ist, dann kann es u. U. ja mehrere Lösungen geben.



  Profil  Quote  Link auf diesen Beitrag Link
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1348
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2008-12-01


Hallo flaming!

fed-Code einblenden


Viele Grüße
Ronald





  Profil  Quote  Link auf diesen Beitrag Link
flaming
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 29.11.2008
Mitteilungen: 13
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2009-12-17


Hallo Delastelle bzw. Ronald,

sorry, dass ich so lange nicht mehr hier gewesen bin, die Thematik hatte sich in meiner Priorisierung ordentlich nach hinten katapultiert in letzter Zeit. Nichts destotrotz ist das Thema nach wie vor "aktuell" für mich.

Mit diskreter Optimierung hatte ich noch nichts zu tun, allenfalls mit linearer. Ich denke aber, dass ich Deine Schilderungen verstanden habe. Leider sind z. B. 10! Möglichkeiten ein unglaublich großer Wert.

Die Heuristik lokale Suche scheint somit das Mittel der Wahl zu sein. Meine Hoffnung war, dass es einen Algorithmus gibt, der für jede n-beliebige Anzahl von Mannschaften immer nach dem gleichen Schema optimale Spielpläne im Sinne der Aufgabenstellung ausrechnet, und zwar ohne "ausprobieren" bzw. Optimierung. Diesen gibt es aber offenbar nicht (sonst wäre er vermutlich auch im Äther bekannt). Das beste, was ich finden konnte, ist der unter folgendem Link vorgestellte Algorithmus:
www-i1.informatik.rwth-aachen.de/~algorithmus/algo36.php
Dieser liefert aber schon bei n=7 ein nicht optimales Ergebnis i.S.d.A.

Die Programmiersprache ist Java (jaja, ich weiß..). Sollte es eine Klasse für die Heuristik lokale Suche geben, wäre ich natürlich sehr daran interessiert (und sei es, damit ich nach und nach Spielplan-Templates für bis zu n=20 oder so Mannschaften erstelle).

Gibt es einen Beweis, dass für n+2 Mannschaften die Mindestpause immer um ein Spiel steigt?
--> Bei 3 Teams ist es klar, dass es mindestens 0 Spiele sind, bei 5 ist es 1, bei 7 sind es 2. Sind es bei 9 mindestens 3 und bei 11 mindestens 4? Falls ein Beweis existiert, würde dies einen Großteil der Rechenarbeit einsparen.

An dieser Stelle mein ausdrücklicher Dank für Deine Ausführungen! Ich weiss noch nicht, was ich mit den Informationen bis hier anfange, mal sehen.

Grüße,
Dirk



  Profil  Quote  Link auf diesen Beitrag Link
clausthaler
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 04.06.2008
Mitteilungen: 295
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2009-12-17


2009-12-17 15:34 - flaming in Beitrag No. 5 schreibt:
Gibt es einen Beweis, dass für n+2 Mannschaften die Mindestpause immer um ein Spiel steigt?
--> Bei 3 Teams ist es klar, dass es mindestens 0 Spiele sind, bei 5 ist es 1, bei 7 sind es 2. Sind es bei 9 mindestens 3 und bei 11 mindestens 4? Falls ein Beweis existiert, würde dies einen Großteil der Rechenarbeit einsparen.

Ich denke, die Konstruktion steht hier, leider wird das Buch nur teilweise angezeigt.

Gruß   cth



  Profil  Quote  Link auf diesen Beitrag Link
flaming
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 29.11.2008
Mitteilungen: 13
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, vom Themenstarter, eingetragen 2009-12-17


Clausthaler: danke vielmals für diesen Link!

Er bestätigt nicht nur die eine These, er untermauert eine andere: dass es möglich sein muss, einen Spielplan ohne Optimierungsläufe zu berechnen.

Wenn man ein wenig nach oben scrollt, sieht man unter 7.24 einen Spielplan für 9 Mannschaften auf zwei Spielfeldern. Diesen kann man recht leicht man auf ein Spielfeld übernehmen (immer zwei Spalten bzw. vier Spiele zusammenfassen) und es lässt sich relativ leicht nachvollziehen, dass jede Mannschaft (wie vermutet) mindestens drei Spiele Pause hat.

Der Spielplan gefällt mir aber auch aus einem anderen Grund: Bei einer ungeraden Anzahl von Spielen "wandern" die Teams "nach unten".
Was ich damit meine: bei einem Spielplan mit 9 Mannschaften gibt es 8 Spieltage zu je vier Spielen, ein Team hat spielfrei. Es ist stets so, dass eines der beiden Teams, das das letzte Spiel an einem Spieltag hat, am nächsten Spieltag spielfrei hat und am übernächsten stets die erste Partie bestreitet. Besonders schön sieht man dies am Team 1: dieses erscheint am jeweils nächsten Spieltag immer eine Position weiter hinten. Bei Team 2 gibt es ein "Break" (mir fällt kein besseres Wort dafür ein) am 3. Spieltag, sonst passt es auch hier. Aus meiner Erfahrung weiß ich, dass das für n = 3 ... 7 genau gleich ist.

Grmpf, das muss doch zu knacken sein! Es müsste doch möglich sein, dass man für n Mannschaften eine Regel findet wie: Team 1 "wandert" nach unten, Team 2 hat folgende Eigenart, ..., Team n füllt den Rest auf.
Jeder "perfekte" Spielplan scheint einen solchen Algorithmus zu besitzen (wenn ich mir einen Spielplan händisch überlege, mache ich es genauso, nur dass ich hintenraus ausprobieren muss), ich sehe ihn aber nicht!



  Profil  Quote  Link auf diesen Beitrag Link
Toaster
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 03.01.2003
Mitteilungen: 268
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2009-12-18


Hallo flaming,

alles, was du wissen musst, steht doch unter 7.26-7.28 in dem angegebenen Link.

Viele Grüsse,
Torsten



  Profil  Quote  Link auf diesen Beitrag Link
flaming
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 29.11.2008
Mitteilungen: 13
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, vom Themenstarter, eingetragen 2009-12-18


Oh Sh*t. Toaster, da hast Du recht! Manchmal sieht man den Wald vor lauter Bäumen nicht. *Nochmalgenauhinkuck* Da stehts.
Das werde ich mal studieren und hoffentlich nachvollziehen. Wenns hakt, melde ich mich nochmals..

Dank Euch allen und frohes Fest!



  Profil  Quote  Link auf diesen Beitrag Link
flaming
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 29.11.2008
Mitteilungen: 13
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, vom Themenstarter, eingetragen 2009-12-25


OK.

Hab mir die Informatik-Studentin meines Vertrauens gekrallt - die hats mir erklärt. Permutationen, schicke Sache. Der Link beschreibt den Algorithmus, abgefahren.

Danke dennoch für alles!!



  Profil  Quote  Link auf diesen Beitrag Link
strugelimutz
Neu Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 08.06.2010
Mitteilungen: 2
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2010-06-08


Ich habe noch eine andere Ausgangslage:

12 Teams spielen jedes Team gegen jedes. 11 Spieltage. An einem Spieltag spielen jeweils 3 Teams an einem Spielort, das gibt 4 Spielorte pro Spieltag. Die Teams spielen jeweils zweimal gegen einander.

Wie sieht der Spielplan aus?



  Profil  Quote  Link auf diesen Beitrag Link
magiczambo
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 09.10.2019
Mitteilungen: 6
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2019-10-09 13:25


2009-12-25 21:43 - flaming in Beitrag No. 10 schreibt:
OK.

Hab mir die Informatik-Studentin meines Vertrauens gekrallt - die hats mir erklärt. Permutationen, schicke Sache. Der Link beschreibt den Algorithmus, abgefahren.

Danke dennoch für alles!!

Hallo ich stehe gerade vor dem gleichen Problem, habe mir die verlinkte Seite aus dem Buch jetzt intensivst angeschaut. Steige aber nicht wirklich durch, wie ich diesen Algorithmus nun in PHP z.B. einbauen könnte.
Die Programmiersprache ist hier erstmal zweitrangig.



  Profil  Quote  Link auf diesen Beitrag Link
flaming
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 29.11.2008
Mitteilungen: 13
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, vom Themenstarter, eingetragen 2019-10-09 14:49


Eine Permutation P für Spielpläne sieht wie folgt aus:
P = {1}{3 5 7 ... 6 4 2} für ungerade Anzahl Elemente (Teams),
P = {1}{3 5 ... 6 4 2} für gerade Anzahl, siehe 7.27 im CRC Handbook of Combinatorial Designs (bitte nochmal verifizieren!)

Die Startfolge ist bei einem Spielplan (z. B. n=7) meist 1 2 3 4 5 6 7 oder auch A B C D E F G. Die ersten Paarungen ergeben sich 1-2, 3-4, 5-6 und 7 bleibt stehen bzw. A-B, C-D, E-F und G bleibt stehen.

Die Permutationsregel besagt, wie du die Elemente der Folge vertauschen musst. Im vorliegenden Fall (n=7, siehe P oben)
Element 1 mit Element 3 (3 2 1 4 5 6 7 oder C B A D E F G), dann
Element 3 mit Element 5 (3 2 5 4 1 6 7 oder C B E D A F G), dann
Element 5 mit Element 7 (3 2 5 4 7 6 1 oder C B E D G F A), dann
Element 7 mit Element 6 (3 2 5 4 7 1 6 oder C B E D G A F), dann
Element 6 mit Element 4 (3 2 5 1 7 4 6 oder C B E A G D F), dann
Element 4 mit Element 2 (3 1 5 2 7 4 6 oder C A E B G D F).

Ich hoffe, dass das so korrekt ist. Am Ende des kompletten Durchlaufes hast Du eine neue Folge, von denen immer zwei Elemente einer Paarung entsprechen. Im Fall n=7 also 7 (war übrig) gegen 3, 1-5, 2-7, 4-6.

Die Folge 3 1 5 2 7 4 6 als Ergebnis des ersten Durchlaufes ist dann der Ausgangspunkt für die nächste Permutation, wo wieder wie oben zuerst Element 1 (3) mit Element 3 (1), dann 3 mit 5, 5 mit 7 usw. getauscht wird.

Nach insgesamt 5 Durchläufen solltest Du bei n=7 für jedes Team 6 Paarungen haben, von der keine doppelt vorkommt und bei dem die Pausen optimiert sind. Ist n gerade, wird ähnlich verfahren, nur dass jeder Durchlauf jeweils komplette Paarungen bildet.

Ich bin weder Mathematiker noch Informatiker, hoffe es war verständlich. Probier es einmal mit n=5 oder n=7 durch und verifiziere. Ich hab in Java eine (ziemlich umständliche) Klasse hinbekommen, die tut, was ich will.



  Profil  Quote  Link auf diesen Beitrag Link
magiczambo
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 09.10.2019
Mitteilungen: 6
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, eingetragen 2019-10-09 20:57


2019-10-09 14:49 - flaming in Beitrag No. 13 schreibt:
Eine Permutation P für Spielpläne sieht wie folgt aus:
P = {1}{3 5 7 ... 6 4 2} für ungerade Anzahl Elemente (Teams),
P = {1}{3 5 ... 6 4 2} für gerade Anzahl, siehe 7.27 im CRC Handbook of Combinatorial Designs (bitte nochmal verifizieren!)

Die Startfolge ist bei einem Spielplan (z. B. n=7) meist 1 2 3 4 5 6 7 oder auch A B C D E F G. Die ersten Paarungen ergeben sich 1-2, 3-4, 5-6 und 7 bleibt stehen bzw. A-B, C-D, E-F und G bleibt stehen.

Die Permutationsregel besagt, wie du die Elemente der Folge vertauschen musst. Im vorliegenden Fall (n=7, siehe P oben)
Element 1 mit Element 3 (3 2 1 4 5 6 7 oder C B A D E F G), dann
Element 3 mit Element 5 (3 2 5 4 1 6 7 oder C B E D A F G), dann
Element 5 mit Element 7 (3 2 5 4 7 6 1 oder C B E D G F A), dann
Element 7 mit Element 6 (3 2 5 4 7 1 6 oder C B E D G A F), dann
Element 6 mit Element 4 (3 2 5 1 7 4 6 oder C B E A G D F), dann
Element 4 mit Element 2 (3 1 5 2 7 4 6 oder C A E B G D F).

Ich hoffe, dass das so korrekt ist. Am Ende des kompletten Durchlaufes hast Du eine neue Folge, von denen immer zwei Elemente einer Paarung entsprechen. Im Fall n=7 also 7 (war übrig) gegen 3, 1-5, 2-7, 4-6.

Die Folge 3 1 5 2 7 4 6 als Ergebnis des ersten Durchlaufes ist dann der Ausgangspunkt für die nächste Permutation, wo wieder wie oben zuerst Element 1 (3) mit Element 3 (1), dann 3 mit 5, 5 mit 7 usw. getauscht wird.

Nach insgesamt 5 Durchläufen solltest Du bei n=7 für jedes Team 6 Paarungen haben, von der keine doppelt vorkommt und bei dem die Pausen optimiert sind. Ist n gerade, wird ähnlich verfahren, nur dass jeder Durchlauf jeweils komplette Paarungen bildet.

Hallo, vielen Dank schon mal für deine Antwort. Leider scheitert dieser "Algorithmus" so wie beschrieben nach dem 3. Durchlauf. Irgendwo habe ich wohl nen Denkfehler drin.

Ich bekomme folgende Ergebnisse:

(1,2,3,4,5,6,7) --> Ausgangsmenge
(3,1,5,2,7,4,6) --> Nach 1. Durchlauf
(5,3,7,1,6,2,4) --> 2. Durchlauf
(7,5,6,3,4,1,2) --> 3. Durchlauf

Somit würden folgende Paarunge bisher feststehen:
1 : 2
3 : 4
5 : 6
7 : 3
1 : 5
2 : 7
4 : 6
5 : 3
7 : 1
6 : 2
4 : 7
5 : 6
3 : 4
1 : 2

die Paarung 5 : 6 kommt nun schon 2x vor ebenfalls 1 : 2 und 3 : 4.

Bei 5 Spielern das selbe.

Auch bei geraden Anzahlen an Spielern









  Profil  Quote  Link auf diesen Beitrag Link
flaming
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 29.11.2008
Mitteilungen: 13
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, vom Themenstarter, eingetragen 2019-10-09 21:46


Puh, das ist schon so lang her.. nochmal nachgeschaut:

Bei n=7 wären die ersten zwei Runden 1-2, 3-4, 5-6, 7-1, 2-3, 4-5, 6-7, sprich es wird erst die dritte Folge permutiert. Passt es dann?



  Profil  Quote  Link auf diesen Beitrag Link
magiczambo
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 09.10.2019
Mitteilungen: 6
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, eingetragen 2019-10-09 22:24


2019-10-09 21:46 - flaming in Beitrag No. 15 schreibt:
Puh, das ist schon so lang her.. nochmal nachgeschaut:

Bei n=7 wären die ersten zwei Runden 1-2, 3-4, 5-6, 7-1, 2-3, 4-5, 6-7, sprich es wird erst die dritte Folge permutiert. Passt es dann?

mh.... leider nein.

wenn ich 2x 1234567 an einander reiher und dann erst permuttiere gehts sogar noch schneller ;-(

1:2
3:4
5:6
7:1
2:3
4:5
6:7
3:1
5:2
7:4
6:5 -->> identische Paarung mit der 3.



  Profil  Quote  Link auf diesen Beitrag Link
magiczambo
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 09.10.2019
Mitteilungen: 6
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.17, eingetragen 2019-10-10 08:25


2019-10-09 14:49 - flaming in Beitrag No. 13 schreibt:
Eine Permutation P für Spielpläne sieht wie folgt aus:
P = {1}{3 5 7 ... 6 4 2} für ungerade Anzahl Elemente (Teams),

Die Permutationsregel besagt, wie du die Elemente der Folge vertauschen musst. Im vorliegenden Fall (n=7, siehe P oben)
Element 1 mit Element 3 (3 2 1 4 5 6 7 oder C B A D E F G), dann
Element 3 mit Element 5 (3 2 5 4 1 6 7 oder C B E D A F G), dann
Element 5 mit Element 7 (3 2 5 4 7 6 1 oder C B E D G F A), dann
Element 7 mit Element 6 (3 2 5 4 7 1 6 oder C B E D G A F), dann
Element 6 mit Element 4 (3 2 5 1 7 4 6 oder C B E A G D F), dann
Element 4 mit Element 2 (3 1 5 2 7 4 6 oder C A E B G D F).

Bist du dir sicher, dass die Permutationsregel so angewandt wird wie du hier beschrieben hast?



  Profil  Quote  Link auf diesen Beitrag Link
flaming
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 29.11.2008
Mitteilungen: 13
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.18, vom Themenstarter, eingetragen 2019-10-10 09:43


Sagen wir, ich war es. Jetzt weiß ich gar nichts mehr.

Bei mir hatte sich irgendwann die Anforderung verschoben, aber die Klasse war fertig, da bin ich mir sicher. Ich hab die auch noch irgendwo, werde heute Abend nachsehen und dann nochmals berichten.

Entschuldige vielmals die Unannehmlichkeiten.



  Profil  Quote  Link auf diesen Beitrag Link
magiczambo
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 09.10.2019
Mitteilungen: 6
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.19, eingetragen 2019-10-10 10:46


2019-10-10 09:43 - flaming in Beitrag No. 18 schreibt:
Sagen wir, ich war es. Jetzt weiß ich gar nichts mehr.

Bei mir hatte sich irgendwann die Anforderung verschoben, aber die Klasse war fertig, da bin ich mir sicher. Ich hab die auch noch irgendwo, werde heute Abend nachsehen und dann nochmals berichten.

Entschuldige vielmals die Unannehmlichkeiten.
Ich bin mir mittlerweile relativ sicher, dass die Permutationsregel anders gedeutet werden muss, dennoch komme ich noch nicht auf die genaue Lösung, wäre toll wenn du mal nachschaust. Danke im voraus


EDIT:

Ich glaube ich habe die Lösung....muss diese aber noch verifizieren und dann versuchen diese auch in Worte zu fassen ;-)



  Profil  Quote  Link auf diesen Beitrag Link
flaming
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 29.11.2008
Mitteilungen: 13
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.20, vom Themenstarter, eingetragen 2019-10-10 11:07


So ein Cloudspeicher ist schon toll, wenn man sich erinnert, dass man da vor Jahren mal was abgelegt hat. Frühstückspause etwas überzogen und geschaut:

Bei n ungerade muss die jeweilige Folge *doppelt* behandelt werden. Als Ausgabe der Permutationen erhalte ich bei n=7 die Folgen

1 2 3 4 5 6 7 (Startfolge)
1 3 5 2 7 4 6
1 5 7 3 6 2 4

Diese sind jeweils doppelt zu reihen, also
1 2 3 4 5 6 7 1 2 3 4 5 6 7
1 3 5 2 7 4 6 1 3 5 2 7 4 6
1 5 7 3 6 2 4 1 5 7 3 6 2 4

Damit ergibt sich
1-2 3-4 5-6 7-1 2-3 4-5 6-7
1-3 5-2 7-4 6-1 3-5 2-7 4-6
1-5 7-3 6-2 4-1 5-7 3-6 2-4

Info: die nächste Reihe wäre 1 7 6 5 4 3 2, also alles außer der 1 (die ja als Kopf immer stehen bleibt) absteigend. Diese wird aber nicht mehr benötigt.

Bei n=9 komme ich auf
1 2 3 4 5 6 7 8 9
1 3 5 2 7 4 9 6 8
1 5 7 3 9 2 8 4 6
1 7 9 5 8 3 6 2 4

n=11
 1  2  3  4  5  6  7  8  9 10 11
 1  3  5  2  7  4  9  6 11  8 10
 1  5  7  3  9  2 11  4 10  6  8
 1  7  9  5 11  3 10  2  8  4  6
 1  9 11  7 10  5  8  3  6  2  4

n=13
 1  2  3  4  5  6  7  8  9 10 11 12 13
 1  3  5  2  7  4  9  6 11  8 13 10 12
 1  5  7  3  9  2 11  4 13  6 12  8 10
 1  7  9  5 11  3 13  2 12  4 10  6  8
 1  9 11  7 13  5 12  3 10  2  8  4  6
 1 11 13  9 12  7 10  5  8  3  6  2  4

Bei n=8 hast Du insgesamt 7 Folgen (und ich bete, es passt, n gerade habe ich nicht überprüft):
1 2 3 4 5 6 7 8
1 3 5 2 7 4 8 6
1 5 7 3 8 2 6 4
1 7 8 5 6 3 4 2
1 8 6 7 4 5 2 3
1 6 4 8 2 7 3 5
1 4 2 6 3 8 5 7

Mittlerweile kann ich bestätigen, dass ich mir recht sicher bin.

[Die Antwort wurde vor Beitrag No.1 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
Er/sie war noch nicht wieder auf dem Matheplaneten
magiczambo
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 09.10.2019
Mitteilungen: 6
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.21, eingetragen 2019-10-11 07:14


Danke flaming, deine Antwort stützt meinen gewonnenen Ansatz. Nur für die Nachwelt --> dein Post hier: LinkAlgorithmus für optimalen Spielplan

ist zu verwerfen.

Vielen Dank nochmals.




  Profil  Quote  Link auf diesen Beitrag Link
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1348
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.22, eingetragen 2019-10-11 23:40


Hallo,

hier ein Programm mit Lokaler Suche (mein Beitrag 4).
Da ich das Programm von damals nicht mehr gefunden habe hier ein neues:
Fortran
      program ls
c lokale Suche
      implicit none
      integer feld(100,2)
      integer mperm(100)
      integer mini,maxiter,maxsidesteps,i,az,azmannschaften
      real t0,t1
      common /dela1/ t0
      common /dela2/ t1
      common /dela3/ azmannschaften
      common /dela4/ az
      call cpu_time(t0)
      call random_seed()
      mini = 9999
c      maxiter = 10000000
      maxiter = 10000
      maxsidesteps = 10000
      azmannschaften = 7
      do 100 i = 1,100
        mperm(i) = 0
100   continue
      call lokaleSuche(mperm,mini,feld,maxiter,maxsidesteps)
      print *,'mini ',mini
      print *,'mperm ',mperm(1:az)
      do 200 i = 1,az
        print *,feld(mperm(i),1),feld(mperm(i),2)
200   continue
      call cpu_time(t1)
      print *,'Zeit = ',t1
      end
c ***********************************
c lokale Suche, Anzahl laeufe maxiter         
c ***********************************
      subroutine lokaleSuche(operm,opt,feld,maxiter,maxsidesteps)
      implicit none
      integer feld(100,2),feld2(100,2)
      integer perm(100),mperm(100),operm(100),perm2(100)
      integer azmannschaften,mini,opt,az,spiele,az1,az2,zf
      integer ozf,maxiter,maxsidesteps
      integer i,j,kkk,mmm,ende,side,merk,zwi,zwi2
      real t0,t1
      common /dela1/ t0
      common /dela2/ t1
      common /dela3/ azmannschaften
      common /dela4/ az
 
      az = 0
      do 100 i = 1,azmannschaften
        do 200 j = i,azmannschaften
          if (i.ne.j) then 
            az = az + 1
            feld(az,1) = i
            feld(az,2) = j
          endif
200     continue
100   continue
      spiele = az
 
      opt = 999
      do 500 mmm = 1,maxiter
        mini = 999
        call permutation(perm,az)
c perm = [3 11 13 17 6 9 14 18 4 10 12 20 5 7 16 21 2 8 19 15 1];
        do 1000 i = 1,az
          feld2(i,1) = feld(perm(i),1)
          feld2(i,2) = feld(perm(i),2)
1000    continue
        call berechneZF(feld2,spiele,azmannschaften,zf,az1,az2)
        mini = zf
        call permutation(perm2,az-1)
 
        ende = 0
        side = 0
        while(ende == 0) do
          ende = 1
          do 2000 kkk = 1,spiele-1
            operm = perm
            ozf = zf
            zwi = perm2(kkk)
            zwi2 = zwi+1
            merk = perm(zwi)
            perm(zwi) = perm(zwi2)
            perm(zwi2) = merk
            do 2100 i = 1,az
              feld2(i,1) = feld(perm(i),1)
              feld2(i,2) = feld(perm(i),2)
2100        continue
            call berechneZF(feld2,spiele,azmannschaften,zf,az1,az2)
            if (zf > ozf) then
c zurueck
              do 3000 i = 1,az
                perm(i) = operm(i)
3000          continue              
              zf = ozf
            else 
              if (zf <= ozf) then
                side = side + 1
              endif
              if (zf < mini) then
                ende = 0
                side = 0
                mini = zf
                mperm = perm
              endif
              if (zf == 0) then
                print *,'Loesung gefunden'
                print *,perm(1:az)
                do 3100 i = 1,az
                  print *,feld(perm(i),1),feld(perm(i),2)
3100            continue
                call cpu_time(t1)
                print *,'Zeit = ',t1
                stop
              endif
              if (side > maxsidesteps) then
                ende = 1
              endif
            endif
2000      continue  
        end do
        if (mini < opt) then
          opt = mini
          do 4000 i = 1,az
            operm(i) = mperm(i)
4000      continue 
        endif        
500   continue
      end
 
c *************************************************
c berechne zielfunktion
c *************************************************
      subroutine berechneZF(feld,spiele,azmannschaften,erg,az1,az2)
      implicit none
      integer feld(100,2)
      integer spiele,azmannschaften,az1,az2,erg,ms,nr
      integer merk1,merk2,merk3
      az1 = 0
      az2 = 0 
      do 100 ms = 1,azmannschaften
        do 200 nr = 1,spiele-1
          merk1 = nr 
          merk2 = nr+1 
          if ( ((feld(merk1,1) == ms).or.(feld(merk1,2) == ms)).and.
     c        ((feld(merk2,1) == ms).or.(feld(merk2,2) == ms)) ) then
            az1 = az1 + 1
          endif  
200     continue
100   continue          
 
      do 1000 ms = 1,azmannschaften
        do 1100 nr = 1,spiele-2
          merk1 = nr 
          merk2 = nr+1 
          merk3 = nr+2
          if ( ((feld(merk1,1) == ms).or.(feld(merk1,2) == ms)).and.
     c         ((feld(merk2,1).ne.ms).and.(feld(merk2,2).ne.ms)).and.
     c         ((feld(merk3,1) == ms).or.(feld(merk3,2) == ms)) ) then 
            az2 = az2 + 1
          endif
1100    continue
1000  continue
      erg = 2*az1+az2
      end
 
c *****************************************
c bilden einer Zufallspermutation
c Herrmann: Algorithmen-Arbeisbuch
c *****************************************
      subroutine permutation(perm,elemente) 
      implicit none
      integer elemente
      integer perm(elemente)
      integer i,merk,r
      double precision zwi
c bilde Permutationsvektor
      do 1000 i = 1,elemente
        perm(i) = i
1000  continue
      do 1100 i = elemente,2,-1        
        call random_number(zwi)
        r = floor(zwi*i)+1
        merk = perm(i)
        perm(i) = perm(r) 
        perm(r) = merk 
1100  continue
      end

Es ist nicht so schnell - aber es funktioniert.
Hier noch eine gefundene Lösung für 7 Mannschaften
Eingabeaufforderung
perm:
           11          12          19           1          15          16           5           7          20
            3          10          13           6          17           9           2          21           8
            4          14          18
Spiele:            
            2           7
            3           4
            5           6
            1           2
            3           7
            4           5
            1           6
            2           3
            5           7
            1           4
            2           6
            3           5
            1           7
            4           6
            2           5
            1           3
            6           7
            2           4
            1           5
            3           6
            4           7
           
Eventuell hatte ich früher mal eine etwas schnellere Version geschrieben. Es braucht eine hohe Zahl von Läufen Lokaler Suche (Variable maxiter).

Viele Grüße
Ronald



  Profil  Quote  Link auf diesen Beitrag Link
flaming wird per Mail über neue Antworten informiert.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]