Hallo
Wir spielen bald zu 20 Leuten ein Badmintonmatch. Es werden nur Doppel auf 5 Plätzen gespielt. Jetzt möchte ich es gerne so arrangieren, dass bei rund 9 Viertelstunden Spielen keiner mit einem erneut alsauch keiner gegen den gleichen nochmalig spielen muss. Gib es hierzu eine vernünftige Regel , Formel , Hilfestellung. Bislang habe ich es mit Ausprobieren und versuchter Logik relativ weit geschafft, bin aber an einem frustigen Ende trotzdem angelangt. Kann mir einer helfen ?
Vorab herzlichen Dank
Christian
hi,
Wir spielen bald zu 20 Leuten ein Badmintonmatch. Es werden
nur Doppel auf 5 Plätzen gespielt. Jetzt möchte ich es gerne
so arrangieren, dass bei rund 9 Viertelstunden Spielen keiner
mit einem erneut alsauch keiner gegen den gleichen nochmalig
spielen muss. Gib es hierzu eine vernünftige Regel , Formel ,
Hilfestellung. Bislang habe ich es mit Ausprobieren und
versuchter Logik relativ weit geschafft, bin aber an einem
frustigen Ende trotzdem angelangt. Kann mir einer helfen ?
ich weiß nicht, ob ich das problem richtig verstanden hab:
ihr seid 20. wenn jeder MIT jedem exakt einmal spielt, muss jeder exakt 19 partien (bzw. n-1 partien bei n spielern) absolvieren.
in diesen 19 partien würde er auf insgesamt 38 (2*(n-1)) gegner treffen. da ihr n=20 seid, MUSS dann jeder öfter gegen bestimmte gegner antreten; im schnitt fast 2 mal.
???
m.
Hi Michael
Danke dass du so schnell geantwortet hast. Mir geht es darum möglichst viele Spiele spielen zu können, ohne dass man erneut aufeinander trifft. Wenn man die Anzahl der Spiele nimmt werden ungefähr 9 herauskommen, da man immer im Doppel gegeneinander spielt, sodass sich hierüber die Anzahl erheblich reduziert. Wichtig ist mir beim erneuten Auflaufen auf den Platz, dass die vier Leute, die auf dem einen Platz stehen, noch nie vorher in dieser Paarung zusammen bzw. gegenüber gestanden habe.Dabei ist es ebnso unerheblich, wenn ich in der ganzen Partie mit/gegen einen nicht gespielt habe, Hauptsache : nie ein zweites Mal mit /gegen den gleichen
Vielen Dank vorab
Christian
hi,
Danke dass du so schnell geantwortet hast. Mir geht es darum
möglichst viele Spiele spielen zu können, ohne dass man erneut
aufeinander trifft. Wenn man die Anzahl der Spiele nimmt
werden ungefähr 9 herauskommen, da man immer im Doppel
gegeneinander spielt, sodass sich hierüber die Anzahl
erheblich reduziert. Wichtig ist mir beim erneuten Auflaufen
auf den Platz, dass die vier Leute, die auf dem einen Platz
stehen, noch nie vorher in dieser Paarung zusammen bzw.
gegenüber gestanden habe.Dabei ist es ebnso unerheblich, wenn
ich in der ganzen Partie mit/gegen einen nicht gespielt habe,
Hauptsache : nie ein zweites Mal mit /gegen den gleichen
ich nenne die erste partie A & B gegen C & D.
darf A später noch einmal gegen B antreten, z.b. mit E gegen B & F ?
darf A später noch einmal gegen B antreten, z.b. mit C gegen B & E ?
mit anderen worten: ist nur dieselbe 4er-kombination als wiederholung verboten? (aber 2 oder 3 dieser 4 sind erlaubt …)
oder - s. dein letzter satz - ist jedes erneute aufeinandertreffen zweier spieler als partner bzw. gegner verboten?
im letzteren fall sind es bei 20 spielern nur 6 partien, die pro person gespielt werden, denn ab der 7. wiederholt sich mindestens eine „begegnung“.
m.
Hi
ich nenne die erste partie A & B gegen C & D.
darf A später noch einmal gegen B antreten, z.b. mit E gegen B
& F ?
darf A später noch einmal gegen B antreten, z.b. mit C gegen B
& E ?
A plus B und A gegen B ist problemlos möglich, aber das ist dann auch schon das Ende der Fahnenstange zwischen den beiden. Bei 20 Leuten spielt also A maximal 9 Spiele gegen die 9x2 Mitspieler.
Gruss
Christian
hi,
A plus B und A gegen B ist problemlos möglich, aber das ist
dann auch schon das Ende der Fahnenstange zwischen den beiden.
Bei 20 Leuten spielt also A maximal 9 Spiele gegen die 9x2
Mitspieler.
ich fürchte ich kann dir hier nicht helfen. ich vermute, das ist eine art stundenplanproblen, eine NP-vollständige angelegenheit.
stundenplanprobleme sind zeitlich ziemlich aufwändig; man löst sie, indem man ein programm einen rohstundenplan entwerfen lässt und dann händisch noch ein bisschen verfeinert.
falls ich wider erwarten noch eine kluge idee habe, werde ich sie hier beitragen.
"Das Stundenplanproblem gilt als NP-vollständig.
Das Stundenplanproblem gehört also zu der Problemklasse NP, das heisst, es gibt einen nichtdeterministischen Algorithmus, der das Problem in polynomieller Zeit löst.
Im Gegensatz dazu stehen die Problemklassen P(es gibt einen deterministischen Algorithmus, der das Problem in polynomieller Zeit löst) und EXP (es gibt einen Algorithmus, der das Problem in exponentieller Zeit löst). Dabei gilt, dass die Problemklasse P eine Teilmenge von NP und diese wiederum eine Teilmenge von EXP ist. Die Eigenschaft ‚vollständig‘ sagt aus, dass das Problem einen so hohen Schwierigkeitsgrad hat, dass man, wenn man einen deterministischen Algorithmus für das Problem finden sollte, damit nachweisen könnte, dass die Problemklasse P und NP gleich sind. Die NP-vollständig Eigenschaft des Stundenplanproblem lässt sich nachweisen, indem man die einfachste Form des Problems auf das Graph-Coloring Problem (aus dem OR) zurückführt, welches NP-vollständig ist.
(http://www.fh-wedel.de/~si/seminare/ss01/Ausarbeitun…)
m.
Hallo,
eine passende Lösung hab ich im Moment nicht parat,
aber in der Fussball Bundesliga gibt es ein ähnliches Problem.
Dort wird die 1-Faktorisierung des vollständigen Graphen verwendet:
http://www-i1.informatik.rwth-aachen.de/~algorithmus…
evt. läßt sich daraus eine Lösung für Dein Problem ableiten.
Grüße
Thorsten
hi,
eine passende Lösung hab ich im Moment nicht parat,
aber in der Fussball Bundesliga gibt es ein ähnliches Problem.
Dort wird die 1-Faktorisierung des vollständigen Graphen
verwendet:
das ist an sich eine gute idee; ich hatte auch schon an so was gedacht und find die literaturangabe interessant.
allerdings hat das hier gestellte problem noch eine schraubendrehung mehr, denn wir haben ja keine fixen teams, denn die spielpartner sollen in jeder partie wechseln.
m.