TeamBuilding Algorithmus

[Godmode]

Hab wieder mal ein kleines/großes Algorithmen Problem und zwar geht es um folgendes:

1. Exhaustion mit Optimierung: Team Building einmal anders (12 Punkte)

Derwisch Mayar ist zu Semesterbeginn wieder einmal total im Stress: Derwisch ist verantwortlich für die Zusammenstellung der Teams für die diesjährigen Reiterfestspiele an der FH-Konstantinopel. Er muß heuer aus 45 Studierenden des dritten Semesters fünf Teams à neun Personen bil-den – und zwar so, dass die Siegeschancen für alle Teams in etwa gleich hoch sind. Um das zu gewährleisten, kommt er auf die Idee, sich für jeden Studierenden die Durchschnittsnote aus den relevanten Lehrveranstaltungen (Galoppieren, Bogenschießen und Säbelfechten) zu berechnen und diese als Basis des Team-Building-Prozesses, wie das heute genannt wird, heranzuziehen. Sein Bestreben ist es, die Teams so zusammenzusetzen, dass die Standardabweichung der Durchschnittsnoten der Teams (= arithmetisches Mittel aller Durchschnittsnoten der Teammitglieder) möglichst klein wird. Helfen Sie Derwisch, indem Sie einen Exhaustionsalgorithmus mit Optimierung entwerfen, der für eine gegebene Anzahl students >= 1 von Studierenden, ein Feld marks der Länge students mit deren Durchschnittsnoten (1.0 <= marksi <= 5.0) und einer Teamgröße teamSize >= 1 (mit students modulo teamSize = 0) eine Anzahl teams = students / teamSize Teams mit möglichst gleichen Siegeschancen bildet und die Teamnummern (0 .. teams-1) für alle Studierenden ausgibt. Implementieren Sie Ihren Algorithmus in C in Form einer Funktion

void Teams(int students, int marks[], int teamSize)

Kann mir irgendwer einen guten Ansatz(keine Lösung) liefern wie ich das Problem lösen könnte? Eine Möglichkeit wäre, einfach alle Permutation auszurechnen und dann das Minimum darüber bilden, ist aber dann viel zu langsam.

Eine Andere Möglichkeite wäre, die Teams in einzelnen Schritten aufzubauen, also ich gebe in jedes Team immer eine neue Person dazu und berechne dann die Standardabweichung, wenn das Ergebnis schlecht ist, einen Schritt zurück, sonst weiter. Gefällt mir persönlich nicht sehr gut.

Also wenn wer gute Vorschläge hat, bitte her damit. ;)

[Monger]

Ich dachte, dieses Problem wäre überhaupt nicht eindeutig lösbar ?!?

Ich hab im Unterricht auf jeden Fall noch dieses Problem mit den Verpackungen kennengelernt (Eine Reihe von Gegenständen beliebiger Größe sollen so auf verschiedene Kisten verteilt werden, dass der Platz optimal genutzt wird). Und mir hat man noch erzählt, dass das zu den unlösbaren Problemen gehört, genauso wie das Traveling Salesman Problem...


Aber zu deinem Problem: ich würde erstmal den Durchschnitt berechnen. Dieser Wert ist ja derjenige, dem sich alle optimal annähern sollen. Die stärksten Abweichler vom Durchschnitt stellen ja das größte Problem dar, deshalb würde ich versuchen, abwechselnd gute und schlechte Studenten nacheinander die Teams zu verteilen, beginnend bei den besten bzw. schlechtesten. Dabei würde ich den jeweiligen Studenten dem Team zuordnen, dessen aktueller Durchschnitt die größte Abweichung zum eigenen Schnitt darstellt.


Das müsste relativ flott gehen, weil du für jeden Studenten einen linearen Berechnungsaufwand hast. Natürlich funktioniert die Methode nur dann einigermaßen gut, wenn die Unterschiede zwischen den Studenten nicht extrem sind und es eine ordentliche Menge an Studenten gibt.

Wahrscheinlich ist das weit von einer optimalen Lösung entfernt, aber vielleicht hast du so schonmal einen Ansatz...

[ScottManDeath]

Ich dachte, dieses Problem wäre überhaupt nicht eindeutig lösbar ?!?

Ich hab im Unterricht auf jeden Fall noch dieses Problem mit den Verpackungen kennengelernt (Eine Reihe von Gegenständen beliebiger Größe sollen so auf verschiedene Kisten verteilt werden, dass der Platz optimal genutzt wird). Und mir hat man noch erzählt, dass das zu den unlösbaren Problemen gehört, genauso wie das Traveling Salesman Problem...


Aber zu deinem Problem: ich würde erstmal den Durchschnitt berechnen. Dieser Wert ist ja derjenige, dem sich alle optimal annähern sollen. Die stärksten Abweichler vom Durchschnitt stellen ja das größte Problem dar, deshalb würde ich versuchen, abwechselnd gute und schlechte Studenten nacheinander die Teams zu verteilen, beginnend bei den besten bzw. schlechtesten. Dabei würde ich den jeweiligen Studenten dem Team zuordnen, dessen aktueller Durchschnitt die größte Abweichung zum eigenen Schnitt darstellt.


Das müsste relativ flott gehen, weil du für jeden Studenten einen linearen Berechnungsaufwand hast. Natürlich funktioniert die Methode nur dann einigermaßen gut, wenn die Unterschiede zwischen den Studenten nicht extrem sind und es eine ordentliche Menge an Studenten gibt.

Wahrscheinlich ist das weit von einer optimalen Lösung entfernt, aber vielleicht hast du so schonmal einen Ansatz...

Jo, würde so auch anfangen um eine initiale Lösung zu bekommen. Und dann einfach hinreichend oft paarweise zufällige 2 Studenten austauschen, und sehen, ob es besser geworden ist ;) Oder gleich einen "richtigen" genetischen Algorithmus implementieren

Nennet sich afaik auch Rucksackproblem.

[Trap]

Hint: Nachgucken was "Exhaustion" bedeutet bzw "Exhaustionsalgorithmus"

Das Problem dürfte NP-hart sein, damit ist das die einzige Möglichkeit eine optimale Lösung zu finden.

Suchwort zum Thema Optimierung von exhaustiver Suche: dynamische Programmierung

[DocEW]

Ist auf jeden Fall NP-hart, d.h. du kannst also höchstens versuchen, dir einen möglichst guten Approximations-Algorithmus zu überlegen.
Ich würde wie schon beschrieben vorgehen: Möglichst gute Anfangslösung finden und dann evtl. noch versuchen, Verbesserungen zu erreichen (etwa durch das beschriebene Tauschen).
Als Startlösung versuch doch mal einfach folgendes:
- Mache zwei Listen: Überdurchschnittliche Studenten (sortiert mit Besten zuerst) und unterdurchschnittliche (sortiert mit schlechtesten zuerst)
- Füge zuerst die Überdurchschnittlichen ein, immer den nächsten Studenten zu dem Team, das noch am schlechtesten ist (und noch Platz hat)
- Dann die Unterdurchschnittlichen, den nächsten zum momentan besten Team (das noch Platz hat)

Ist wohl im Grunde so ähnlich wie Mongers Ansatz, aber vielleicht hilft dir eine etwas andere Formulierung. :)

Vielleicht versuchst du auch was ganz anderes... erstmal Paare bilden, die zusammen möglichst nah am Durchschnitt sind... keine Ahnung, da gibt es ja viele Möglichkeiten.

Wenn du das Problem gelöst hast, kannst du auch gleich ein Programm schreiben, was 5 CDs mit jeweils 9 Songs füllt und die CDs möglichst gleich lang macht. :D

[Godmode]

danke für eure tollen Vorschläge, ich werde mich gleich mal an die Arbeit machen. ;)

[Trap]

Oh jeh. Implementier nicht irgendwelchen Müll nur weil das jemand in einem Forum vorschlägt. So wie die Aufgabe gestellt ist, ist sie optimal lösbar.

[Godmode]

Oh jeh. Implementier nicht irgendwelchen Müll nur weil das jemand in einem Forum vorschlägt. So wie die Aufgabe gestellt ist, ist sie optimal lösbar.

Naja is halt blöd wenn man zu einem neuem Thema überhaupt keine Ansatz hat, deshalb hab ich einfach mal gefragt. Mit dynamischer Programmierung bin ich auch noch nicht wirklich vertraut, deshalb ja diese Aufgabe.

Exhaustion = alle Lösungen berechnen

wenn ich diese Lösungen dann habe, brauche ich nur mehr das Minimum bilden.

[DocEW]

Oh jeh. Implementier nicht irgendwelchen Müll nur weil das jemand in einem Forum vorschlägt. So wie die Aufgabe gestellt ist, ist sie optimal lösbar.
Natürlich ist sie optimal lösbar. Fragt sich nur in welcher Zeit.

[Monger]

Natürlich ist sie optimal lösbar. Fragt sich nur in welcher Zeit.

... und mit welchem Entwicklungsaufwand. Sich mal eben so in C eine performante und perfekte Lösung aus den Fingern zu saugen wenn man von dynamischer Programmierung keine Ahnung hat (was übrigens auch für mich gilt. Was zur Hölle ist das ?!?), könnte etwas länger dauern. Und bans3i hat sich nicht gerade so angehört, als hätte er jetzt ein halbes Jahr Zeit dafür.

[Senior Sanchez]

Ich dachte, dieses Problem wäre überhaupt nicht eindeutig lösbar ?!?

Ich hab im Unterricht auf jeden Fall noch dieses Problem mit den Verpackungen kennengelernt (Eine Reihe von Gegenständen beliebiger Größe sollen so auf verschiedene Kisten verteilt werden, dass der Platz optimal genutzt wird). Und mir hat man noch erzählt, dass das zu den unlösbaren Problemen gehört, genauso wie das Traveling Salesman Problem...


Aber zu deinem Problem: ich würde erstmal den Durchschnitt berechnen. Dieser Wert ist ja derjenige, dem sich alle optimal annähern sollen. Die stärksten Abweichler vom Durchschnitt stellen ja das größte Problem dar, deshalb würde ich versuchen, abwechselnd gute und schlechte Studenten nacheinander die Teams zu verteilen, beginnend bei den besten bzw. schlechtesten. Dabei würde ich den jeweiligen Studenten dem Team zuordnen, dessen aktueller Durchschnitt die größte Abweichung zum eigenen Schnitt darstellt.


Das müsste relativ flott gehen, weil du für jeden Studenten einen linearen Berechnungsaufwand hast. Natürlich funktioniert die Methode nur dann einigermaßen gut, wenn die Unterschiede zwischen den Studenten nicht extrem sind und es eine ordentliche Menge an Studenten gibt.

Wahrscheinlich ist das weit von einer optimalen Lösung entfernt, aber vielleicht hast du so schonmal einen Ansatz...

Das ist lösbar, fragt sich nur mit welchem Zeitaufwand.

Bei TopCoder gabs mal sone ähnliche Aufgabe. Da musste man unterschiedlich schwere Kinder so auf einer Wippe positionieren, dass das gesamte Drehmoment möglichst gegen 0 tendiert.

Mein Ansatz hatte für viele Lösungen richtig funktioniert, nur nicht für Spezialfälle. Ich hatte die Kinder sortiert eingefügt, mein Algorithmus erlaubte allerdings keine vollständige Rekombination auf der Wippe. Ich hatte mich aber danach nicht genauer damit beschäftigt, aber mit genügend Zeit (bei TopCoder hatte ich für 3 Aufgaben 60 min ;) ), sollte das machbar sein.

Dein Ansatz, monger, weißt da noch die Schwächen wie meiner auf. Das funktioniert allgemein recht gut, allerdings für perfekt ausbalancierbare Teams wird das schwer, wenn die inner bestimmten Reihenfolge sind. Da ist die Erweiterung von ScottMan gut, da er quasi evolutionär noch weiter ausbalancieren kann.

[Monger]

Wie gesagt, mein Ansatz setzt voraus, dass die Noten bei allen Studenten einer Gleichverteilung ähneln, und die Teamgrößen relativ groß sein können.

Für die Realität ist das ok, vom theoretischen Ansatz her ist das fatal. Bei festen, kleinen Teamgrößen (z.B. drei Leute) kann das Ergebnis extrem mies sein. Selbst wenn man nur Pi mal Daumen die Leute zusammenwürfelt, ist das Ergebnis wahrscheinlich immer noch besser als diese automatische Lösung.

Ich finde die Idee gut, immer zwei Personen zu tauschen. Das sollte relativ einfach umzusetzen sein: "suche das stärkste und das schwächste Team, und tausche den stärksten und den schwächsten Spieler aus!"

Wenn man das ein paar Mal durchrattern lässt, hat man zwar immer noch kein optimales Ergebnis, aber es sollte nach ein paar Durchläufen einigermaßen "glatt" sein. Und ich finde, über Algorithmen die drei Tage zum rechnen brauchen, sollte man erst gar nicht nachdenken.

[DocEW]

Ich habe mal nachgeguckt: Für das Rucksack-Problem (http://de.wikipedia.org/wiki/Rucksackproblem)gibt es einen Algorithmus, der mittels dynamischer Programmierung eine lineare Laufzeit für beschränkte Eingabegrößen (hier gegeben) hat.
Aber ich weiß noch nicht, wie man das "TeamBuilding" Problem auf das Rucksack-Problem transformiert. Für mich ist es erstmal ein Partitionsproblem (http://de.wikipedia.org/wiki/Partition), wie da genau die Verbindung aussieht...?

[Trap]

Das Problem ist recht ähnlich zu http://de.wikipedia.org/wiki/Beh%C3%A4lterproblem.

Zur Aufgabenstellung: Müssen alle Teams gleich viele Mitspieler haben?

[Godmode]

Das Problem ist recht ähnlich zu http://de.wikipedia.org/wiki/Beh%C3%A4lterproblem.

Zur Aufgabenstellung: Müssen alle Teams gleich viele Mitspieler haben?

ja die Teams müssen gleich groß sein.

edit: mein neuer Vorschlag:

Ich bilde alle Kombinationen die es gibt und bilde von diesen dann das Minimum. Somit habe ich schon mal alle Lösungen, da es ja eine Exhaustion ist. Mit dynamischer Programmierung sorge ich jetzt dafür, dass Teilergebnisse zwischengespeichert werden, somit kann ich den Algorithmus beträchtlich beschleunigen. Jetzt muss ich nur mehr einen Algorithmus finden der mir alle Kombinationen bildet.