Algorithmus für eine annähernd gerechte Sitzung gesucht
Neue Frage »

27.03.2010, 21:10 FragenÜberFragen Auf diesen Beitrag antworten »
Algorithmus für eine annähernd gerechte Sitzung gesucht
Hallo geschätzte Mathematiker,

Das Problem das ich (als in der Mathematik äußerst untalentierter) stellen möchte lautet:
wie ermittelt man die "gerechteste" Sitzordung für eine Personenmenge, bei der bekannt sind:

1) Anzahl Personen: 26

2) Anzahl Tische: 5
1 x 4er-Tisch
2 x 6er-Tisch
2 x 8er-Tisch

3) Liste, in der zu jeder Person deren Lieblings-Sitznachbar u n d Ersatz-Lieblingsnachbarn genannt

ist.
PERSON > Lieblingsnachbar(Ersatz-Lieblingsnachbar)
a > hat nicht abgestimmt
b > i(h)
c > o(q)
d > j(e)
e > d(v)
f > p(z)
g > r(s)
h > e(k)
i > h(d)
j > y(k)
k > j(m)
l > v(s)
m > x(i)
n > y(w)
o > c(q)
p > f(z)
q > o(r)
r > s(t)
s > a(r)
t > r(s)
u > x(v)
v > u(x)
w > h(i)
x > y(m)
y > x(m)
z > s(f)



Hintergrund:
Meine Frau betreut Erst-Klässler einer offenen Ganztagsschule.
Die sechsjährigen Kinder rebellierten gegen die Mensa-Sitzordnung in der Mittagspause - bis die Betreuerinnen nachgaben und eine neue Sitzordnung versprachen.
Um eine möglichst entgegenkommende Sitzordnung zu ermöglichen, erbaten sie von jedem Kind die Nennung genau eines Lieblings-Sitznachbarn und genau eines E r s a t z-Lieblings-Sitznachbarn.
Erwartungsgemäß stellte sich schnell danach heraus, wie schwierig die Umsetzung einer auch nur annähernd "gerechten" Sitzordnung für den Nicht-Mathematiker ist..

Meine Frau mußte zwar unter Zuhilfenahme vieler Papierschnitzel (und unter Berücksichtigung weiterer Parameter wie Geschlecht und Charakter usw.) längst zu einer pragmatischen Lösung kommen, aber vielleicht erscheint euch ja diese Art von Problemstellung in irgeneiner Weise diskussionswürdig.

Welcher Mathematikbereich beschäftigt sich eigentlich mit der Gerechtigkeit von Algorithmen? Und wenn es so eine Mathematik gibt, wo und wie würde sie beispielsweise hier die Grenze zwischen Berechenbarkeit und Gerechtigkeit ansetzen?

ich freue mich über jede Antwort!
27.03.2010, 21:46 Airblader Auf diesen Beitrag antworten »

Also spontan würde ich dieses Problem dem Teilgebiet der Optimierung zusprechen.

Ein paar Fragen, die mir schon beim Lesen durch den Kopf geschossen sind:

Wie definierst du "Nachbar"? Jemand, der links oder rechts sitzt? Oder auch gegenüber? Was sind es überhaupt für Tische .. runde oder eckige Tische? Wenn es eckige sind und ich am Ende einer Seite sitze, habe ich dann nur einen Nachbarn?

Das Problem würde ich schlicht und ergreifend "numerisch" angehen .. oder mit einem besseren Wort: Per Programm.
Ich kenne allerdings keines, was dafür ohne enormen Aufwand einsetzbar wäre. Daher stellt sich die Frage, ob ihr jemanden zur Verfügung habt, der programmieren kann. Und selbst dann müsste man sich damit auseinandersetzen, wie man es vernünftig implementiert und nach welchen Regeln die Sitzordnung bestimmt wird.
Dass man eine Ausweichmöglichkeit auf eine "2. Wahl" hat ist ganz nett, aber nicht 100%-ig. Im Extremfall kann es sein, dass manche Schüler keinen der beiden Nebensitzer haben können und man müsste entscheiden, wie man dann vorgeht.

Alles in allem ist für mich aber die Kernfrage: Ist es wirklich sinnvoll, diesen Arbeitsaufwand da reinzustecken?

Meine persönliche erste Idee:
Macht doch ein Spiel daraus und lasst die Kinder sich selbst organisieren. Sie sollen sich erstmal "Reise-nach-Jerusalem"-mäßig durch den Raum bewegen und beim Ende der Musik hinsetzen. Dabei dürfen sie natürlich schon zielstrebig laufen, aber sie dürfen nicht stehenbleiben.
Dann kann man ja jeden fragen, ob er seinen Platz mag. Wer ihn nicht mag, steht auf und man macht das Ganze nochmal etc.

Ist nur eine Idee, die man sicher in vielen (besseren) Variationen durchführen kann. Aber ich wollte sie nur mal als skizzierte Alternative in den Raum legen.

air
27.03.2010, 21:51 tigerbine Auf diesen Beitrag antworten »

ich sehe es auch als Optimierungsproblem. Mir stellt sich dabei zuerst de Frage, wie man einer beliebigen Sitzordnung einen Wert zuordnung würde (Wie sieht also die zu optimierende Funktion aus?).

Zitat:
Original von Airblader
Alles in allem ist für mich aber die Kernfrage: Ist es wirklich sinnvoll, diesen Arbeitsaufwand da reinzustecken?


Für den KiGa vielleicht nicht. Aber Hochzeitsplaner würden uns eine solche Software doch aus der Hand reißen, oder? Big Laugh
27.03.2010, 22:00 Airblader Auf diesen Beitrag antworten »

Zitat:
Original von tigerbine
Mir stellt sich dabei zuerst de Frage, wie man einer beliebigen Sitzordnung einen Wert zuordnung würde (Wie sieht also die zu optimierende Funktion aus?).


Also ganz klar enthalten sein muss ja:

- A: Anzahl der Kinder, die neben ihrem Wunschpartner sitzen
- B: Anzahl der Kinder, die neben ihrer 2. Wahl sitzen

Dann wäre vielleicht, wenn man die genaue Form der Tische geklärt hat, sinnvoll:

- C: Anzahl der Kinder, die zumindest so nahe beim Wunschpartner sitzen, dass Gespräche möglich sind
- D: Anzahl der Kinder, die zumindest so nahe bei der 2. Wahl sitzen, dass Gespräche möglich sind

Das sind zumindest mal vier m.M.n. wichtige Faktoren. Bleibt aber auch dann noch die Frage, wie man diese kombiniert.

Zitat:
Für den KiGa vielleicht nicht. Aber Hochzeitsplaner würden uns eine solche Software doch aus der Hand reißen, oder? Big Laugh


Stimmt eigentlich - gute Idee. Und das meine ich ernst.
Im Hinblick auf Hochzeitsplaner - gibts da sowas nicht vllt. sogar schon (muss ja nicht "kompatibel" zu diesem Problem sein)?

Du bringst mich hier auf Ideen, dabei habe ich doch schon genug zu tun. unglücklich Big Laugh

air
27.03.2010, 22:05 tigerbine Auf diesen Beitrag antworten »

Scheint es zu geben, ich kann das aber nicht öffnen.

http://users.informatik.haw-hamburg.de/~...ege/Ameisen.odp

code: 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:

Hochzeitsproblem

n Gäste, mit i=1,...,n

T Tische, mit t=1,...,T

Jeweils Kt Sitzplätze

Sympathiewert Sij zwischen Person i & j
mit 1<=Sij<=3,

1 nicht sympathisch,

2 neutral,

3 sehr sympathisch

Hochzeitsproblem

Nicht mehr Personen pro Tisch
als Sitzplätze

genau 1 Platz pro Person

Binärvariable:
1, Person i sitzt an Tisch t
0, sonst

Hochzeitsproblem

Aufgabe:

Maximiere Sympathiewerte
je Tisch im ganzen Saal

Hochzeitsproblem

4 Gäste

2 Tische

Sympathiematrix

[Bild3]


edit: ein PDF - Hochezeitsproblem aka Ameisenproblem
27.03.2010, 22:51 Mazze Auf diesen Beitrag antworten »

Es wurde ja schon zur genüge erwähnt, aber ja, dass ist ein klassisches Optimierungsproblem. Es gibt dazu dutzende Möglichkeiten, aber so ziemlich alles erfordert die Lösung per Rechner. Was die Funktion angeht, ich würde es so machen :

Zunächst wird die Zielfunktion für einen Sitzplatz definiert (lokale Kosten). Wir Minimieren einfach mal, sprich überall positive Kosten.

Kosten 0 für Lieblingspartner unter den Nebensitzplätzen
Kosten a für Ersatzlieblingspartner unter den Nebensitzplätzen
Kosten b keiner der beiden unter den Nebensitzplätzen

mit 0 < a < b

a und b sind "sinnvoll" zu wählen. Die globalen Kosten g sind dann die Summe über die lokalen Kosten. Die Funktion g ist dann genau minimal (=0) wenn jeder neben seinem Lieblingspartner sitzt. (so es existiert)

Optimieren kann man das dann wie man möchte. Da gibt es ja unzählige Möglichkeiten. Was sich hier als Schwierig herausstellen dürfte ist, dass es keine optimale Substruktur gibt, sprich wenn Tisch 1 Kosten 0 hat, heisst es nicht, dass die Minimallösung diesem Tisch auch Kosten 0 zuordnen wird.

Man kann das Ganze natürlich auch wesentlich komplizierter machen, aber eine brauchbare Lösung dürfte diese Methode liefern.
 Anzeige 
 
27.03.2010, 22:55 Airblader Auf diesen Beitrag antworten »

Bei der Implementierung sollte man sich auf jeden Fall Gedanken machen, wie man möglichst viele Sitzordnungen von vornherein verwerfen kann.
Denn bei 26 Schülern hat man - sofern meine miserablen Kombinatorik-Kenntnisse nun nicht völlig versagen Big Laugh - immerhin

(in Worten: Über 400 Quadrilliarde)

Möglichkeiten.
Und das ist noch das 21.862.474-fache dessen, was ein Int64 mit seinen 64 Bits packt.

air
27.03.2010, 23:01 Mazze Auf diesen Beitrag antworten »

Naja, ungültige Sitzordnungen wird es wohl nicht geben, mit anderen Worten, ungültige Zustände. Wenn sich alle nicht leiden könnten, wäre sogar jede Sitzordnung optimal. Aber davon abgesehen würde man einen Zustand wohl auch nicht als eine Int64-Variable modellieren. Man kann durchaus alle Zustände erreichen, dauert nur eine Weile! Big Laugh
27.03.2010, 23:04 Airblader Auf diesen Beitrag antworten »

Zahlen sind keine Grenzen, es gibt ja auch Datentypen speziell für solche großen Zahlen. Ich wollte lediglich ein bisschen darauf aufmerksam machen, mit welcher Größenordnung man es bei 'schlappen' 26 Kindern zu tun hat und dass eine vernünftige Herangehensweise von vornherein als wichtig erachtet werden sollte.

Hat man aber z.B. runde Tische, so sind ja schon einige der Möglichkeiten gleichwertig. Ähnliches für andere Muster. Aber man muss eben vorher wissen, wie genau das alles nun aussieht.

air
27.03.2010, 23:09 Mazze Auf diesen Beitrag antworten »

Eine Idee wären wohl "Zusammenhangskomponenten". Wenn man es schafft das alle Lieblingspartner/Ersatzlieblingspartner an einem Tisch A sitzen, und alle übrigen Kinder keinen Liebling/Ersatzliebling an Tisch A haben, so muss dieser Tisch nicht weiter betrachtet werden. Damit wird der Zustandsraum dann durchaus eingeschränkt. Wenn man bedenkt das sich Kinder wohl häufiger in "festen" Gruppen bewegen, klingt das vielleicht sogar realistisch.
27.03.2010, 23:12 Airblader Auf diesen Beitrag antworten »

Das stimmt natürlich, aber das ist natürlich etwas, das wohl nur in Ausnahmen möglich ist. Es sei denn, man könnte sogar die Tische etwas variieren - das wäre zwar erstmal eine Steigerung der Komplexität, macht aber diese Betrachtung erstmal einfacher, denke ich.

Für mich ist das Problem noch etwas, das mathematisch nicht zu fassen ist: Wie entscheidet man 'gerecht'? Wenn es mit allen Kindern hinhaut und einem nicht, wird es das eine Kind wohl kaum interessieren, dass es neben anderen Kindern sitzt, die sich nicht besonders mögen.
Rein intuitiv wäre da eine Lösung vorzuziehen, so dass vllt. zwei Kinder nicht perfekt sitzen, aber wenigstens neben ihrer 2. Wahl oder so.

Das ganze natürlich nur als vereinfachte Version der Problematik.

Edit: Vielleicht denken wir auch zu allgemein. Dem Fragesteller dürfte in erster Linie eine Lösung seiner konkreten Situation am Herzen liegen. Die Daten liegen vor. Vielleicht könnte man also die Daten anschauen und etwas spezifischer und weniger allgemein denken - um in vernünftiger Zeit an eine Lösung zu kommen.

Edit #2:
Gehe ich genau nach diesem Prinzip vor, so finde ich z.B. in kurzer Zeit, dass b, i, h, d, e, j, k und m gut zusammenpassen.
Gehen wir von einem 8er-Tisch aus mit auf jeder Seite 4 Stühlen, so wäre diese Anordnung sinnvoll:

code: 
1:
2:
3:
4:

 b i h e
|-------|
|-------|
 m k j d


Damit hätte man nur noch 18 Personen über.

air
27.03.2010, 23:31 papahuhn Auf diesen Beitrag antworten »

Ich habe die Daten mal visualisiert und dabei Erst und Zweitwahl als gleichberechtigt genommen. Im Grunde ist man recht gut bedient, wenn man eine lange Kette sucht und einem Tisch zuordnet. Wenn man die Kette dabei so wählt, dass die Knoten an den Enden in symmetrischer Relation stehen, sollten alle glücklich sein. Ein Beispiel wäre k,j,y,m,i,d,e für einen Siebenertisch, wenn es einen gäbe. Die Kette lässt sich sogar auf k,j,y,m,i,d,e,h aufstocken, da d und e sich gegenseitig sympathisch sind. So könnte man eventuell manuell herumprobieren, bevor man das den Rechner machen lässt.
27.03.2010, 23:35 Airblader Auf diesen Beitrag antworten »

Nach papahuhns Post kommt mir ein weiteres Problem in den Sinn:

Zwar kann man erstmal zusammenhängende Gruppen finden, die sinnvoll ergeben, aber dadurch, dass sie von der Liste verschwinden, könnte ein anderer Tisch schwer zusammenstellbar sein.
Hätte man anders kombiniert - da es sicher immer mehrere Möglichkeiten geben wird - wäre der andere Tisch vielleicht einfacher und besser.

Das hebelt das Zusammenhangsprinzip natürlich wieder deutlich aus. Man könnte aber eben schauen, ob man überhaupt in Probleme an anderen Tischen kommt. Letztlich suchen wir ja vllt. nicht die beste, sondern einfach eine gute Möglichkeit.

Edit:
Und die nächste Idee .. wie wäre es denn, wenn wir die logische und oben von mir erwähnte spielerische Idee kombinieren? Vielleicht genügt es, eine ansatzweise vernünftige Lösung zu finden. Diese nimmt man als Ausgang und lässt die Kinder sich dann in dieser konkreten Sitzordnung umschauen und selbst organisieren, ob sie vielleicht jemanden finden, den sie fragen können, ob man tauschen kann etc. - die Kinder wissen i.d.R. ja, wer sich nicht ausstehen kann und wer mit wem gut befreundet ist ... und das Gehirn eines Kindes bringt sicherlich besser und schneller Ergebnisse als ein mühevoll entwickeltes Programm auf dem Rechner. Augenzwinkern

In diesem Modell, wie gesagt, brauchen wir nichtmal eine Lösung, die so gut ist, dass sie als endgültig betrachtet werden kann, sondern sozusagen nur einen vernünftigen "Startwert" bzw. eine vernünftige Start-Sitzordnung.

air
27.03.2010, 23:42 ObiWanKenobi Auf diesen Beitrag antworten »

Ohne dem mathematischen Problem ausweichen zu wollen, wäre es vieleicht überlegenswert von vorne herein die "Meinungsfindung" anders zu gestalten, um so zu einem besseren Konsens zu kommen.

Ich würde die Methode des "Systemischen Konsensierens" wählen:

http://www.sk-prinzip.net/

P.S. Vor 20 Jahren habe ich eine weitere Methode kennengelernt das Problem zu lösen:

Müller! Da hinsetzen! Meier! Dort hinsetzen! Huber! Da hinsetzen....
Mundhalten! Essen!

Ich gebe allerdings zu, dass diese Methode wenig zeitgemäß ist!
27.03.2010, 23:47 Airblader Auf diesen Beitrag antworten »

Aber zumindest ist sie effektiv ... Big Laugh

Wie man sieht hat diese Problematik sehr viele Herangehensweisen. Und jede in sich kann beliebig komplex gestaltet werden. Wir sollten aufpassen, nicht unnötig viel Aufwand zu betreiben, wenn man eine etwa gleich gute Lösung für den Bruchteil des Aufwandes haben kann.

Letztlich können wir nur vorschlagen. Entscheiden muss der Fragesteller selbst.

air
P.S.: Inwiefern, wenn ich fragen darf, hast du die denn mit 22 Jahren beigebracht bekommen?
28.03.2010, 04:04 FragenÜberFragen Auf diesen Beitrag antworten »

Hallo Leute, ihr seid der Wahnsinn,

ich war nur ein paar Stunden weg und ihr habt schon eine Klein-Lawine von durchdachten Antworten erzeugt, von denen ich aufgrund meiner mageren Mathematik-Kenntnisse jetzt schon nur noch einen kleinen Teil verstehe :-)

Vielleicht noch mal ein Wort dazu, was der Grund war, warum ich diesen Thread hier angestoßen habe:

1) Das Gefühl, daß die Aufgabenstellung nicht ganz so trivial ist, wie sie im ersten Moment erscheint. Und den Nachweis dafür von einer Gruppe von Leuten, die am ehesten dazu prädestiniert ist, dies zu beurteilen. Diesen Nachweis habt ihr mir mit euren Antworten schon wunderbar geliefert.

2) Die Begeisterung darüber, wie eine Meute von Sechsjährigen es geschafft hat, ihre Betreuerinnen in ein solches Problem zu katapultieren.

3) Die Frage, welches mathematische Gebiet hier "zuständig" ist (ein Teilgebiet der Optimierung, wie ich jetzt von euch gelernt habe.)


Leider schaffe ich es heute nur noch, euch jetzt schon mal für eure Engagement die Ernsthaftigkeit eure Ansätze zu danken, morgen vormittag werde ich mit meiner Frau eure Antworten mal genauer ansehen und versuchen, alle Rückfragen, die ihr an mich hattet zu beantworten.
Ein paar eurer Rückfragen kann ich allerdings jetzt schon beantworten:

a) Der (einzige) 4er-Tisch ist quadratisch (je eine Person pro Seite)

b) Die (beiden) 8er-Tische sind quadratisch (je zwei Personen pro Seite)

c) Die (beiden) 6er-Tische sind rechteckig (an den kurzen Seiten nur eine Person)

d) Die Tische sind im Quadrat angeordnet, wobei
- der 4er-Tisch in der Mitte steht
- die großen Tische die Ecken des Quadrats bilden

e) Der Begriff Nachbar wurde in der Erhebung der Kinderwünsche nicht definiert. Ich versuche mal eine Wohlfühlranking (1=höchster Wert) ...
- e.1) (nah) gegenüber (z.B. am 4er-Tisch oder an den Längsseiten des 6er-Tisches)
- e.2) (nah) nebeneinander (links oder rechts an allen Längsseiten oder bei Nachbarn "Über-Eck")
- e.3) (weit) gegenüber (z.B. am 8er-Tisch oder an den kurzen Seiten des 6er-Tisches)


morgen mehr davon...
28.03.2010, 04:09 Airblader Auf diesen Beitrag antworten »

Hi,

also wenn ich dich recht verstehe, ist "Gegenüber" besser als "Nebeneinander"?
Prinzipiell würde ich aber jetzt von meinem Verständnis her mal sagen: Ob nun gegenüber oder nebeneinander sollte keine große Rolle spielen. Man nimmt einfach die Kombination, die für die übrigen Plätze das beste Ergebnis liefert.

Jedenfalls kann ich mir kaum vorstellen, dass ein Kind weniger zufrieden ist, weil der Freund nebenan und nicht gegenüber sitzt. Big Laugh

Aber für den Moment lass ichs auch mal gut sein und wünsche eine gute Nacht (von der ich nicht mehr viel habe) Hammer

Wink

air
28.03.2010, 04:47 Airblader Auf diesen Beitrag antworten »

So, verzeiht den Doppelpost, aber es ist doch einiges Neues.
Ich habe nun doch noch ein paar Minuten nachgedacht und mich an eine ganze Kombination gewagt.

Kleine Anmerkung: Ihr habt 5 Tische, braucht aber nur 4. Was ist mit dem überzähligen Tisch?
Ich mache jetzt mal einen Vorschlag:

code: 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

   i  h                       w  n
  ------                     ------
b |    | e       f         x |    | y
  |    |        ---          |    |
m |    | d    p | | a      u |    | v
  ------        ---          ------
   k  j          z            t  l


	       q r     
               ----- 
             g |   | s  
               -----
                o c


Schauen wir uns das mal an. Ich bezeichne jetzt mal mit (1 / 2 / 3). Im ersten Eintrag steht, wie viele an dem Tisch perfekt sitzen. Im zweiten Eintrag, wie viele zumindest bei der 2. Wahl oder über Eck mit einer Wahl sitzen. Im dritten Eintrag stehen völlig unzugeordnete Kinder.

Der ganze Linke Tisch erreicht dann eine ordentlich (6 / 2 / 0). Das ist akzeptabel. Der mittlere Tisch erreicht (3 / 1 / 0) - auch das ist okay.
Am unteren Tisch haben wir eine (5 / 1 / 0) und auch das ist recht gut, denke ich.

Doch jetzt kommt der "Problemtisch". Am rechten Tisch haben wir eine (6 / 1 / 1). An sich ist das gut ... nur das eine, schwarze, unglückliche Schaf bzw. Kind ist Kind 'w'. Dieses sitzt bei keinem Wunschpartner.
Wenn ihr aber den linken Tisch einfach oben quer hinstellt, dann habt ihr statt der (6 / 1 / 1) immerhin eine (6 / 2 / 0).
Et voila - und schon habt ihr nicht ein unzufriedenes Kind! Eine "über-Eck"-Beziehung ist ja okay, wenn ich das richtig verstanden habe.

Das ist nun vielleicht nicht die optimalste Lösung, aber immerhin ist es schonmal eine, wie ich finde, alles andere als schlechte Lösung.

Jetzt brauche ich aber wirklich Schlaf. Big Laugh

air
Edit: Kann sein, dass ich mich bei den ersten beiden Tischen etwas vertan habe zwischen "perfekt sitzen" und "bei 2. Wahl sitzen". Aber ist ja nicht ganz so wild. Bin nun aber zu müde um nochmal nachzuzählen. *gähn*
28.03.2010, 15:56 FragenÜberFragen Auf diesen Beitrag antworten »

Hallo zusammen,

besonderen Dank Airblader, daß du dir so spät noch den Kopf zerbrochen hast :-)

ich bin gerade mal mit meiner Frau alle euren Rückfragen/Ansätze durchgegangen (so weit wir sie als Mathematik-Laien einordnen konnten), hier das Ergebnis:

1) zu euren Vorschlägen zur spielerischen Ermittlung der Sitzordnung ("Reise nach Jerusalem" von airblader) oder zumindest zur Ermittlung eines neuen Startwertes oder zur Neu-Erhebung ("neue Meinungsbildung" von tigerbine) der Lieblingsnachbarn:
Die Betreuerinnen haben schon einiges spielerisch ausprobiert, auch andere Umfrage-Versuche oder Formen der Selbsorganisation fanden statt, alles in allem ohne den gewünschten Erfolg aber mit viel Unruhe und Unzufriedenheit verbunden, so daß sie dieses Thema jetzt unbedingt mit diesem letzten Ansatz zum Abschluss bringen wollen.
(Eine Methode des "Systemischen Konsensierens": das klingt trotzdem sehr interessant!)

2) zur Frage, wo der gewünschte Lieblingsnachbar am liebsten sitzen sollte:
meine Frau hat mich für mein (eigenmächtiges) Ranking gescholten. Sie meint, nebeneinander zu sitzen ist für die Sechsjährigen in jedem Fall wichtiger als gegenüber. Es geht hier wohl eher um den symbolischen Wert und weniger um Augenkontakt und Kommunikation. So daß das Ranking wohl eher lauten muß (sorry):

- 1) nebeneinander (links oder rechts an allen Längsseiten oder bei Nachbarn "Über-Eck")
- 2) (nah) gegenüber (z.B. am 4er-Tisch oder an den Längsseiten des 6er-Tisches)
- 3) (weit) gegenüber (z.B. am 8er-Tisch oder an den kurzen Seiten des 6er-Tisches)



3) zur Frage von Airblader
Zitat:
Ihr habt 5 Tische, braucht aber nur 4. Was ist mit dem überzähligen Tisch?

Der fünfte ist eigentlich sogar gewünscht, da er gerne zur Entzerrung genutzt wird, und weil sich die Betreuerinnen dann wahlweise dazusetzen können. Obwohl richterweise auch vier genügen würden.


4) zum Vorschlag von Mazze (über die Ermittlung von Kosten).
Hier müssen wir Mathematik-Laien leider aussteigen ;-).
Trotzdem natürlich danke für deine Posts!

5) zur vorgeschlagenen Sitzordnung von Airblader im vorangegangenen Post:
uns ist folgendes aufgefallen: es gibt ein auffällige Bindung in den Daten zwischen der Dreiergruppe X,Y,M (in Papahuhns Visualisierung wird sie gut sichtbar):
m > x(i)
x > y(m)
y > x(m)
In deiner Lösung ist interessanterweise genau diese Gruppe komplett auseinandergefallen. Möglicherweise müßten in deinem Ansatz die Gruppen-Tendenzen berücksichtigt werden.

5) zum Vorschlag von papahuhn:
Zitat:
Ich habe die Daten mal visualisiert und dabei Erst und Zweitwahl als gleichberechtigt genommen. Im Grunde ist man recht gut bedient, wenn man eine lange Kette sucht und einem Tisch zuordnet. Wenn man die Kette dabei so wählt, dass die Knoten an den Enden in symmetrischer Relation stehen, sollten alle glücklich sein. Ein Beispiel wäre k,j,y,m,i,d,e für einen Siebenertisch, wenn es einen gäbe. Die Kette lässt sich sogar auf k,j,y,m,i,d,e,h aufstocken, da d und e sich gegenseitig sympathisch sind. So könnte man eventuell manuell herumprobieren, bevor man das den Rechner machen lässt.

Durch die Visualisierung wird vieles sehr schön klar. Auch ist damit ein flexibler Weg aufgezeigt, wie mit unterschiedlichen Ketten gespielt werden werden kann. Die Beobachtung, daß du in deiner Beispiel-Kette (nicht notwendigerweise aber halt zufällig durch deine Wahl) ebenfalls die o.g. Gruppe (x,y,m) auseinandergerissen hast, hat mich auf die Frage gebracht, ob man solche Ketten also um einen massiven Gruppen-Kern im Zentrum aufbauen sollte (anstatt von den End-Knoten her, wie du vorschlägst)?
(Möglicherweise hat Mazze dies allerdings unter dem Stichwort "Zusammenhangskomponenten" längst angesprochen, ich war mir hier nicht sicher, ob ich das richtig einordnen kann)

gruß
FragenÜberFragen
28.03.2010, 16:15 Airblader Auf diesen Beitrag antworten »

Das Problem mit einer eng gebundenen Dreier-Kette ist, dass es zu eng ist. Es ist praktisch eine geschlossene Kette und dadurch wird es schwerer, noch andere Kinder mit reinzubringen.

Ganz einfach sieht man es am Vierertisch. Hier müsste man noch ein Kind hinzufügen, doch die Dreiergruppe ist in sich schon gewissermaßen geschlossen.

Dass sowohl bei mir, als auch bei anderen Vorschlägen diese Trennung ganz unabsichtlich zustandekam, spricht für mich im ersten Augenblick dafür, dass wir hier das typische Phänomen haben, dass eine lokal ungünstigere Situation global einfach günstiger ist.

Der Effekt der Gruppentendenz ist zwar erstmal einleuchtend (und bleibt es auch), liefert aber u.U. wesentlich ungünstigere Sitzordnungen.

Mehr kann ich im Augenblick leider nicht sagen, da fehlt mir etwas die Zeit. Augenzwinkern

air
28.03.2010, 21:58 Mystic Auf diesen Beitrag antworten »

So, wenn ich mir mal Airblader's Code oben "ausborge", dann würde meine Sitzordnung wie folgt aussehen:

code: 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

   c  o                       n  w
  ------                     ------
j |    | q       g         a |    | h
  |    |        ---          |    |
k |    | z    r | | s      b |    | e
  ------        ---          ------
   p  f          t            i  d


	        m l     
               ----- 
             y |   | v  
               -----
                x u


Immerhin hat jeder so mindestens einen Nachbarn (vorzugsweise nebenan, auf dem Vierertisch bzw. der Längsseite des Sechsertisches ev. auch gegenüber), der seinem Erstwunsch oder Zweitwunsch entspricht, ausgenommen natürlich a, der keinen Wunsch bekanntgegeben hat.

Ich habe dabei auch versucht, gemäß dem Punkteschema

- Erstwunsch ist Nachbar nebenan (3)
- Zweitwunsch ist Nachbar nebenan oder Erstwunsch gegenüber (2)
- Zweitwunsch gegenüber (1)

die Punktezahl zu maximieren und komme dann auf folgende Punktezahlen

- Vierertisch (15)
- Sechsertisch (22)
- LinkerAchtertisch (26)
- RechterAchtertisch (18)

also in Summe auf 81 Punkte, wenn ich mich nicht verrechnet habe...
29.03.2010, 10:33 Mystic Auf diesen Beitrag antworten »

Ich habe mir jetzt noch eine etwas andere Bewertung überlegt, die mir um einiges gerechter erscheint und die hoffentlich diesen Doppelpost rechtfertigt, nämlich:

1. Erstwunsch nebenan (5)
2. Erstwunsch nah gegenüber oder Zweitwunsch nebanan (4)
3. Zweitwunsch nah gegenüber (3)
4. Erstwunsch am gleichen Tisch, aber nicht nebenan oder nah gegenüber (2)
5. Zweitwunsch am gleichen Tisch, aber nicht nebenan oder nah gegenüber (1)

"Nah gegenüber" kann dabei nur am Vierertisch und an den Längsseiten des Sechsertisches auftreten.

Damit ergibt sich dann folgende Bewertung (tatsächliche/maximale Punktezahl) der Tische bei der obigen Sitzordnung, wenn ich richtig gerechnet habe:

Linker Achtertisch: 48/72
Rechter Achtertisch: 38/72
Vierertisch: 29/36
Sechsertisch: 41/54

Wie man sieht, sind dann die beiden kleineren Tische relativ nahe am Optimum, aber auch die Achtertische sind jetzt nicht so schlecht, wobei der zweite vor allem durch a, welcher keinen Wunsch geäußert hat, etwas benachteiligt ist...
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »


MatheBoard » Hochschulmathematik » Sonstiges » Algorithmus für eine annähernd gerechte Sitzung gesucht