Aufgabe 2.4a

Moderator: Algorithmische Modellierung

mister_tt
Kernelcompilierer
Kernelcompilierer
Beiträge: 502
Registriert: 29. Sep 2008 15:54

Aufgabe 2.4a

Beitrag von mister_tt » 12. Aug 2013 09:55

Hallo zusammen,

meiner Meinung nach ist der Lösungsansatz von Aufgabe 2.4a falsch beschrieben. Wenn man es so umsetzt wie beschrieben, wird nicht unbedingt ein Plan gefunden, bei dem die Lehrveranstaltungen möglichst gleichmäßig verteilt sind. Man bekommt einen Plan, bei dem an einem Wochentag möglichst wenige Lehrveranstaltungen sind. Betrachten wir einen einfachen Fall, in dem alle Studierenden die selben Veranstaltungen besuchen, von Mo-Fr jeweils zwei überschneidungsfreie Zeitslots verfügbar sind, jede Veranstaltung nur einen Slot braucht und es 8 Veranstaltungen gibt. Dann wäre ein gleichmäßig verteilter Plan doch so etwas hier (zu lesen als Anzahl der Veranstaltungen pro Tag Mo-Fr): [2, 2, 2, 1, 1]. Mit dem Lösungsansatz aus der Aufgabe würde aber ein solcher Plan gefunden werden: [2, 2, 2, 2, 0]. Das ist aber keineswegs gleichmäßig verteilt.
Meiner Meinung nach könnte man als "Metrik" folgendes nehmen: (Summe der Slots von Veranstaltungen von Student i) / (Anzahl der Tage, an denen Veranstaltungen von Student i stattfinden). Das summiert man über alle Studenten auf und lässt ein minimize drauf los. Das sollte doch einen gleichmäßig verteilten Plan finden, oder?

Viele Grüße und danke
Simon

mister_tt
Kernelcompilierer
Kernelcompilierer
Beiträge: 502
Registriert: 29. Sep 2008 15:54

Re: Aufgabe 2.4a

Beitrag von mister_tt » 5. Sep 2013 17:47

Die oben beschriebene Zielfunktion stellt lediglich sicher, dass an möglichst vielen Tagen Veranstaltungen stattfinden. Nicht aber, dass die Veranstaltungen über diese Tage gleichmäßig verteilt sind. Es wäre also (bei mehr Veranstaltungen) ein Plan wie [8, 1, 1, 1, 1] möglich, was eher nicht gewünscht ist. Herr Weihe formulierte die Dominanz einer Lösung gegenüber einer anderen sinngemäß so: Eine Lösung A, aufgeschrieben wie oben sowie absteigend sortiert, ist besser als eine andere Lösung B, wenn A lexikographisch kleiner als B ist (wobei B natürlich ebenfalls sortiert sein muss). Beispiel:
[3, 3, 2, 2, 2] <- optimale Lösung
lexikographisch kleiner als
[3, 3, 3, 3, 0]
lexikographisch kleiner als
[4, 2, 2, 2, 2]
lexikographisch kleiner als
[8, 1, 1, 1, 1]
Dann bleibt immer noch die Frage, wie man das als Zielfunktion umsetzt. Mir ist aber noch eine, wie ich finde, einfachere Möglichkeit eingefallen, die hoffentlich auch funktioniert :-)

Man könnte den Bruch von oben nehmen und den Zähler so verändern, dass er die maximale Anzahl Slots von Veranstaltungen von Student i an einem Tag repräsentiert. Man nimmt also (maximale Anzahl Slots von Veranstaltungen an einem Tag von Student i) / (Anzahl der Tage, an denen Veranstaltungen von Student i stattfinden). Das summiert man über alle Studenten auf und minimiert es. So wird die Zielfunktion größer, wenn mehr Slots von Veranstaltungen von Student i an einem Tag stattfinden oder wenn an weniger Tagen Veranstaltungen von Student i stattfinden. Beispiel analog zu oben:
[3, 3, 2, 2, 2] -> 3/5 = 0,6
[3, 3, 3, 3, 0] -> 3/4 = 0,75
[4, 2, 2, 2, 2] -> 4/5 = 0,8
[8, 1, 1, 1, 1] -> 8/5 = 1,6

Herr Weihe machte mich noch auf das Problem aufmerksam, dass auch das Aufsummieren über alle Studenten alles andere als optimal ist. Durch die Summe kann es durchaus passieren, dass der Plan für manche Studenten super wird, für andere Studenten aber sehr schlecht. Eher gewünscht wäre eine Variante, die für alle Studenten ungefähr gleich gut ist. Denn letztlich will man ja die Anzahl der Beschwerden minimieren. Hierzu könnte man eine Art "Straffunktion" einführen, die bei Plänen, die für Student i sehr schlecht sind, die Zielfunktion größer macht. Wenn also x der Strafwert für einen schlechten Plan für Student i ausdrückt, wird dieser zum Bruch oben addiert. Dies macht Pläne, die für einzelne Studenten sehr schlecht sind, unwahrscheinlicher.

Antworten

Zurück zu „Algorithmische Modellierung“