Denksportaufgabe

[oliverv]

Hallo,

ich programmiere ein Lehrveranstaltungs-Anmeldesystem für eine Universität. Der Student hat die Möglichkeit 3 LV aus einem Bereich auszuwählen, von denen er dann zu einer zugeteilt wird.

Dabei speichere ich in einer Datenbank ua. folgende Felder:

Praeferenz1 = Die erste Wahl des Studenten
Praeferenz2 = Die zweite Wahl
Praeferenz3 = Die dritte Wahl
Zugewiesen = Die LV, die gleich nach der Anmeldung aufgrund verschiedener Kriterien zugeteilt wird. (entweder 1, 2 oder 3)

Wegen des Designs des übrigen Anmeldemechanismus kann es vorkommen, ... Das Problem ist schwer in Worte zu fassen. Ein Beispiel:

Student Praeferenz1      Praeferenz2       Praeferenz3       Zugewiesen  
Max          15               20               22               20    
Moritz       20               15               19               15 

Beiden Studenten wurde also die zweite Wahl zugeteilt. Würde man nur die Zuweisung von ihnen tauschen wären sie aber beide glücklicher, weil sie nun beide ihre 1. Wahl besuchen könnten, ohne dass Platzprobleme bei einer LV entstehen würden.

Ich möchte nun, nachdem die Anmeldungsfrist abgeschlossen ist, mit einem PHP-Skript über alle Anmeldedaten drüberfahren, alle solche Konstellationen herausfiltern und die Zuweisungen solange tauschen bis ein Optimum erreicht ist, also es nicht mehr möglich ist durch das Tauschen von Zuweisungen einem Studenten in eine höhere Präferenz zuzuweisen.

Dabei muss natürlich 1. mit 2., 2. mit 3. und 1. mit 3. Präferenz geprüft werden.

Ja, mein Problem: Ich habe keinen Schimmer für einen (schnellen) Lösungsansatz.

Bin für jede Idee dankbar!

[tontechniker]

Wie werden denn die Zuweisungen im Moment verteilt? Du könntest erstmal allen ihren Erstwunsch zuteilen und dann die Kurse mit Zweitwunsch so auffüllen das sie passen.

[ghostgambler]

Ich fürchte, dass du dafür keine "perfekte" Lösung finden wirst ... so oder so wird per Zufall der ein oder andere Schüler bevorzugt werden.


Als einfacher Lösungsansatz: While-Schleife über die komplette Datenbank und dann in der Schleife Datensätze suchen die zum Tauschen geeignet sind.
Ist natürlich nicht gerade schnell

$result = SELECT * FROM tabelle WHERE Praef1 != Zuweisung;
while ($row = result) {
  $in = "";
  if row.zuweisung = praef2 then $in = "Praef1";
  elseif row.zuweisung = praef3 then $in = "praef2, praef1";
  $result2 = SELECT * FROM tabelle WHERE row.zuweisung IN ($in) AND zuweisung IN (row.praefs)
}

oder sowas in der Richtung... (das letzte IN ist falsch, da müsste noch so ein If-In-Konstrukt hin, aber ich muss jetzt weg, deshalb abgekürzt XD~)

[oliverv]

@tontechniker: Das versteh' ich nicht. Aber bei der Zuweisung soll sich nichts ändern, nur im Nachhinein sollen Zuweisungen getauscht werden.

@ghostgambler: Danke, das ist zumindest schon besser als mein bisheriger Ansatz (alles in ein Array packen und dann mit 2 Schleifen alles mit allem abgleichen).

Wenn noch jemand Ideen hat, bitte mitteilen.

Oliver

[onemorenerd]

Das allgemeine Problem ist NP-vollständig, also nicht in polynomieller Zeit lösbar. Siehe dazu z.B. http://de.wikipedia.org/wiki/Partitionsproblem

Aber wenn du nur wenige Veranstaltungen und Studenten hast, ist deine Eingabe hinreichend klein. Du kannst alle möglichen Lösungen berechnen, bewerten, vergleichen und so die beste bestimmen.