Algorithmus für Tennisturnier < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:49 Do 06.09.2007 | | Autor: | howlett |
| Aufgabe | Bei einem Freizeit-Tennisturnier auf einer Tennisanlage mit 4 Spielfeldern sollen ausschließlich Doppel gespielt werden. Es sind insgesamt 6 Runden geplant. Es kommt also zu insgesamt 24 Spielen.
Erstelle einen Spielplan, bei dem möglichst alle Spieler gleich viele Spiele absolvieren und jeder Spieler minimal häufig auf gleiche Spieler trifft.
Die Teilnehmerzahl ist
(a) 24
(b) 25
(c) 26 |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Meine Mutter soll für den kommenden Sonntag einen Tennisspielplan erstellen und ich sagte großkotzig, dass ich das schon schaffen kann. Es ist allerdings ein kompliziertes Problem, zu dem ich noch, aufgrund wenig Vorkenntnisse in diesem Bereich, keine Lösung gefunden habe...
Gibt es einen allgemeinen Algorithmus mit dem man dieses Problem lösen kann?
Ich bin mir auch nicht sicher, in welches Forum dieser Artikel gehört. Verschiebt diesen Artikel, falls er zu einem anderen Forum-Thema besser passt
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:18 Do 06.09.2007 | | Autor: | dormant |
Hi!
Das ist leider kein wohlgestelltes Problem.
Was ist besser - 24 haben alle gleich viel gespielt und der 25. hat gar nicht gespielt, oder jeder hat im Schnitt 20 Spiele gemacht und 20 Leute weichen mit 1-2 Spielen davon ab? Für das zweite Ziel kann man ähnliche Aussagen machen - wie soll man zwei Spielpläne beurteilen?
Außerdem sind beide Ziele nicht unabhängig, man muss also wissen was wichtiger ist - gleiche Spiele, oder auf verschiedene Spieler (was meinst du eigentlich - Gegner, oder Partner) treffen.
Deswegen gibt es dafür keinen Algorithmus. Wenn man die Forderungen klarer formulieren könnte, dann würde wahrscheinlich lineare Programmierung helfen.
Gruß,
dormant
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:41 Do 06.09.2007 | | Autor: | howlett |
Danke für die rasche Antwort.
Vorweg: Das Problem ist noch nicht gelöst.
> Was ist besser - 24 haben alle gleich viel gespielt und der 25. hat gar
> nicht gespielt, oder jeder hat im Schnitt 20 Spiele gemacht und 20 Leute
> weichen mit 1-2 Spielen davon ab?
Für den Einzelnen sind maximal 6 Spiele möglich. Es handelt sich um 6 Durchgänge in denen jeweils 4 Doppel gespielt werden. Jeder Spieler soll ungefähr gleich häufig spielen.
Bsp.: Feld 1, 1. Runde:
1 2
3 4
Feld 2, 1. Runde
5 6
7 8
> Außerdem sind beide Ziele nicht unabhängig, man muss also wissen was
> wichtiger ist - gleiche Spiele, oder auf verschiedene Spieler (was meinst
> du eigentlich - Gegner, oder Partner) treffen.
Das wichtigste ist, das jeder ungefähr gleich häufig spielt. Also wahrscheinlich 4 oder 5 mal. Der Partner bleibt nicht fix. Man sollte kein mal mit dem gleichen Partner zusammen spielen und möglichst kein mal gegen einen gleichen Gegner spielen.
Grüße!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:42 Do 06.09.2007 | | Autor: | dormant |
Hi!
> Danke für die rasche Antwort.
> Vorweg: Das Problem ist noch nicht gelöst.
>
> > Was ist besser - 24 haben alle gleich viel gespielt und der
> 25. hat gar
> > nicht gespielt, oder jeder hat im Schnitt 20 Spiele
> gemacht und 20 Leute
> > weichen mit 1-2 Spielen davon ab?
>
> Für den Einzelnen sind maximal 6 Spiele möglich. Es handelt
> sich um 6 Durchgänge in denen jeweils 4 Doppel gespielt
> werden. Jeder Spieler soll ungefähr gleich häufig spielen.
>
> Bsp.: Feld 1, 1. Runde:
>
> 1 2
> 3 4
>
> Feld 2, 1. Runde
>
> 5 6
> 7 8
Schon klar, die genau Zahl ist nicht so wichtig. Das ist aber keine klare Forderung. Klar wäre z.B. zu verlangen: beim paarweisen Vergleich soll der Unterschied zwischen den Spielen höchstens 1 sein. Wenn das nicht möglich ist (kann passieren), dann kann man den Unterschied auf höchstens 2 setzen, u.s.w.
> Das wichtigste ist, das jeder ungefähr gleich häufig
> spielt. Also wahrscheinlich 4 oder 5 mal. Der Partner
> bleibt nicht fix. Man sollte kein mal mit dem gleichen
> Partner zusammen spielen und möglichst kein mal gegen einen
> gleichen Gegner spielen.
Kein mal mit dem selben Partner ist machbar, aber möglichst kein mal gegen einen von beiden Gegner ist auch nicht klar. Da kann man auch eine Toleranzgrenze setzen, z.B. man darf bei höchstens einem Spiel gegen den einen von den beiden Gegnern gespielt haben, oder was Ähnliches.
Es gibt viele Möglichkeiten das Problem anzugreifen, ich würde es in Schritten lösen.
1. Schritt: Wer spielt und wer guckt zu in der jeweiligen Runde? Offensichtilich spielt in Runde 1 die Spieler 1-16 und 17-24 gucken zu. In Runde 2 spielen 24-9 und 8-1 gucken zu. In Runde 3 spielen 1-8 und 17-24; und 9-16 gucken zu. Runde 4 wie Runde 1, Runde 5 wie Runde 2, und Runde 6 wie Runde 3. Du kannst dir vorstellen wie der Algorithmus (greedy algorithm) für 25 Spieler ausschaut. Damit hat man auch "das Wichtigste" erreicht.
2. Schritt: In der jeweiligen Runde gucken, dass man die Toleranzbedingungen erfüllt.
u.s.w. - du darfst dir genaueres dazu überlegen.
Gruß,
dormant
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:08 Do 06.09.2007 | | Autor: | howlett |
Ich habe eine Lösung gefunden. Über wikipedia war ein Algorithmus zu finden, der für Bundesliga-Spieltage erfunden wurde. Dabei wird, grob beschrieben, mit Kongruenzen gearbeitet:
Dies habe ich auf mein Problem zurückgeführt und habe eine Lösung gefunden:
1. Runde:
01 25 | 03 23 | 05 21 | 07 19
02 24 | 04 22 | 06 20 | 08 18
2. Runde:
09 17 | 11 15 | 13 00 | 02 03
10 16 | 12 14 | 01 04 | 25 05
u.s.w.
Naja, ich werde einfach noch ein bißchen herum-experimentieren und die Alternativen für weniger Teilnehmer austüfteln.
Danke.
|
|
|
|
