Teilen Sie Leute in Teams für die meisten Zufriedenheit

Question

Nur eine Frage der Neugier. Erinnern Sie sich daran, dass der Professor bei Gruppenarbeit die Personen in Gruppen mit einer bestimmten Nummer aufteilt (n)?

Einige meiner Professoren eine Liste von n Menschen würde man mit und n Menschen arbeiten, will man mit von jedem Schüler nicht arbeiten wollen, und dann mit würde magisch entpuppen Gruppen von n wo die Schüler abgestimmt Menschen, die sie bevorzugen und vermeiden, mit Menschen zu arbeiten, die sie nicht bevorzugen.

Für mich diesen Algorithmus klingt viel wie ein Knapsack Problem, aber ich dachte, ich würde fragen, um zu wissen, was Ihr Ansatz für diese Art von Problem sein würde.

EDIT: Gefunden an ACM article beschreiben etwas genau wie meine Frage. Lesen Sie den zweiten Absatz für deja vu.

Answer 1

Für mich klingt es eher wie eine Art clique Problem. wenn diese beiden folgenden Dinge die Schüler

Zwei Studenten durch eine Kante würde verbunden wäre

• Vertices halten:

  So wie ich das Problem zu sehen, hatte ich folgendes graph eingerichtet:

  1. mindestens einer der beiden Studenten will mit dem anderen arbeiten.
  2. Keiner der beiden Studenten wollen nicht mit dem anderen arbeiten.

Es ist dann eine Frage der Unterteilung des Graphen in Cliquen der Größe n. (Angenommen, die Anzahl der Schüler ist durch n teilbar)

Wenn dies nicht möglich wäre, würde ich wahrscheinlich die erste Beschränkung auf die Kanten gleiten lassen, und Kanten zwischen zwei Personen haben, solange keiner von ihnen ausdrücklich darauf hinweist will nicht mit dem anderen arbeiten.

Wie für einen Ansatz, um dies effizient zu lösen, habe ich keine Ahnung, aber das sollte man hoffentlich näher kommen zu einem gewissen Einblick in das Problem.

Answer 2

Dieses Problem kann Brute-gezwungen sein, daher wäre mein Ansatz zuerst, es Brute-Force, dann beheben, wenn ich eine bessere Idee.

Answer 3

Man könnte dies ziemlich leicht als Clustering-Problem modellieren, und Sie würden nicht einmal wirklich brauchen, um einen Raum zu definieren, könnten Sie eigentlich definieren nur die Entfernungen:

Machen Sie zwei Personen sehr nahe, wenn sie beide arbeiten wollen zusammen. Schließen, wenn einer von ihnen mit dem anderen arbeiten möchte. Mittlere Distanz, wenn es nur Apathie gibt. Weit weg, wenn keiner mit dem anderen arbeiten will.

Dann könnten Sie nur Cluster finden, yay. Dann teilen Sie alle Cluster von zu großer Größe auf, mit der Gewissheit, dass die Leute in den Clustern gut zusammenarbeiten würden.

Answer 4

Es gibt ein paar Algorithmen Sie nutzen könnten. Ein gutes Beispiel ist das "stabile Eheproblem", das eine perfekte Lösung bietet.Hier können Sie mehr darüber lesen:

http://en.wikipedia.org/wiki/Stable_marriage_problem

Das stabile Ehe Problem funktioniert nur mit zwei Gruppen von Menschen (Männer/Frauen in der Ehe Fall). Wenn Sie ein Paar bilden möchten, können Sie eine Variante verwenden, das stabile Mitbewohnerproblem. In diesem Fall erstellen Sie Paare, aber jeder kommt aus einem einzigen Pool.

Aber Sie haben nach einem Team gefragt (das ich in> 2 Leute pro Team übersetze). In diesem Fall könnten Sie alle ihre besten bis schlechtesten Übereinstimmungen eingeben lassen und dann die