Verteilungsproblem

phyll

Hallo!

An meiner Schule gibt es einen Projekttag, vor dem jeder Schüler 4 Projekte in einer Reihenfolge auswählen muss, in die er gerne ginge. Bisher war es nun bei uns so, dass sich ein Arbeitskreis zusammensetzte und alle 1300 Schüler in ihre Projekte verteilte. Ein Haufen Arbeit, und natürlich fühlen sich danach viele ungerecht behandelt. Daher wollte ich ein Programm schreiben, das die Schüler möglichst optimal verteilt. Dazu habe ich drei Fragen:

1. Ich bin der Meinung, das Problem müsste NP-vollständig sein, weil es äqiuvalent zum Rucksackproblem ist. http://de.wikipedia.org/wiki/Rucksackproblem. Ich hätte dabei soviele Rucksäcke wie Projekte, jeder Schüler hat das "Gewicht" 1 und einen "Nutzwert", der von seiner Priorität für dieses Projekt abhängt. Frage: Stimmt diese Argumentation?

2. Falls ich das Problem durch Brute-Force lösen wollte, wie kann ich berechnen, wieviele Möglichkeiten es denn überhaupt gibt, die Schüler zu verteilen? (Zur Vereinfachung könnte man annehmen, alle Projekte hätten Platz für gleich viele Schüler)

3. Vermutlich werde ich aber ein Verfahren anwenden, das schnell berechenbar ist und dabei gute Näherungslösungen produziert. Meine Idee dafür war:

1. Alle Schüler in ihr 1. Wunschprojekt stecken
2. Alle Projekte durchgehen, wenn in einem Projekt zu viele Leute sind, 
nach Schülern suchen, in deren 2. Wunschprojekt noch Platz ist und diese dort hinstecken
3. Danach das Ganze mit den 3. und 4. Projekten wiederholen
4. Falls immer noch irhendwo zu viele drin sind, die Probleme melden und manuell korrigieren lassen.

Was meint ihr? Hat das irgendwelche gravierenden Nachteile oder kann man es so machen? Hat jemand eine andere Idee?

phyll

Kerstin81

Hallo!
Ich glaube, du hast ein Problem, wenn du das so machen möchtest. Stell dir vor:
Anton hat diese Reihenfolge gewählt:
Projekt A - 1
Projekt B - 2
Projekt C - 3
Projekt D - 4

Berta so:
Projekt B - 1
Projekt C - 2
Projekt A - 3
Projekt D - 4

Nun sind in Projekt A zu viele Schüler, in Projekt B zu wenige. Damit rutscht Anton in Projekt B. Sind jetzt auch noch aus anderen Projekten Schüler in B gerutscht, ist B überfüllt. Im nächsten Durchlauf überprüfst du die 3.liebste Wahl, dh, Berta kommt in Projekt A (wo doch Anton sein will, der aber nach C geht). usw

Mein Vorschlag wäre: Zufall einbauen
Also:
Alle Schüler auf ihr Lieblingsprojekt setzen.
Ganz wichtig: Schüler, die ein unbeliebtes Projekt gewählt haben, dürfen in jedem Fall dort bleiben.
In überbesetzten Projekten schaust du dir die 2. Wahl an. Kandidaten, die hier ein unbeliebtes Projekt gewählt haben, wechseln. Sind jetzt zu viele in dem unbeliebten Projekt, entscheidet ein Zufallsgenerator, wer dort bleibt und wer doch in sein Lieblingsprojekt darf. Sind immer noch zu wenige in dem unbeliebten Projekt, wiederholst du das Ganze mit der 3. Wahl.

Kerstin

Jester

phyll schrieb:

1. Ich bin der Meinung, das Problem müsste NP-vollständig sein, weil es äqiuvalent zum Rucksackproblem ist. http://de.wikipedia.org/wiki/Rucksackproblem. Ich hätte dabei soviele Rucksäcke wie Projekte, jeder Schüler hat das "Gewicht" 1 und einen "Nutzwert", der von seiner Priorität für dieses Projekt abhängt. Frage: Stimmt diese Argumentation?

Deine Argumentation zeigt zumindest, dass das Rucksackproblem Deine Problemstellung beinhaltet. Das heißt aber nicht automatisch, dass Deine Problemstellung NP-vollständig ist. -- Das Rucksackproblem beinhaltet ja auch den Spezialfall wo alle Teile gleich groß und gleich schwer sind. Sicher auch ein Rucksackproblem, aber halt ein sehr einfaches.