Teilen die Menschen in Teams für die meisten Zufriedenheit

Question

Nur Neugier Frage. Denken Sie daran, wenn in der Klasse GruppeArbeitswarteschlangenBenutzerArbeitswarteschlangenGruppenBenutzerin würde der Professor Menschen teilen in Gruppen einer bestimmten Anzahl (n)?

Einige meiner Professoren würde eine Liste von n Menschen nehmen ein arbeiten will mit und n Menschen, die man will nicht die Arbeit mit von jedem Schüler, und drehen Sie dann auf magische Weise Gruppen von n, wo Studenten abgestimmt werden mit den Menschen würde sie bevorzugen und vermeiden sie arbeiten mit Menschen, die sie nicht bevorzugen.

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

Bearbeiten : Gefunden ein ACM Artikel etwas genau wie meine Frage beschreibt. Lesen Sie den zweiten Absatz für Déjà-vu.

Answer 1

Für mich klingt es eher wie eine Art Clique Problem.

So wie ich das Problem sehen, würde ich die folgenden Graph einrichten:

• Vertices würden die Studenten
• Zwei Schüler würden durch eine Kante verbunden werden, wenn beiden folgenden Dinge zu halten:
  1. Mindestens einer der beiden Studenten will mit dem anderen zu arbeiten.
  2. Keine der beiden Studenten wollen nicht mit dem anderen zu arbeiten.

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

Wenn dies nicht möglich war, würde ich wahrscheinlich die erste Einschränkung lassen auf die Kanten gleiten, und haben Kanten zwischen zwei Menschen, solange keiner von ihnen sagt ausdrücklich, dass sie zur Arbeit wollen nicht mit dem anderen.

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

Answer 2

Sie konnten dieses Modell ziemlich leicht als Clustering-Problem, und Sie würden nicht einmal wirklich einen Raum definieren müssen, könnten Sie eigentlich definieren nur die Entfernungen:

Machen Sie zwei Menschen sehr nahe, wenn sie beide wollen arbeiten zusammen. Schließen, wenn man von ihnen will mit dem anderen zu arbeiten. Mittlere Entfernung, wenn es nur Apathie ist. Weit davon entfernt, wenn einer nicht mit dem anderen zu arbeiten möchte.

Dann könnte man nur Cluster finden, yay. aufgeteilt dann alle Cluster von übermäßig groß, mit Zuversicht, dass die Menschen in den Clustern alle gut zusammen arbeiten würden.

Answer 3

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

Answer 4

Es gibt ein paar Algorithmen Sie nutzen könnten. Ein gutes Beispiel ist das so genannte „stabile Ehe Problem“, die eine perfekte Lösung. Sie können mehr darüber lesen Sie hier:

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 Paar bilden möchten, können Sie eine Variante verwenden, um die stabile Mitbewohner Problem. In diesem Fall erstellen Sie Paare, aber jeder kommt aus einem einzigen Pool.

Aber Sie gebeten, für ein Team (die ich in> 2 Personen pro Team übersetzen). In diesem Fall könnten Sie alle fill in ihrem besten zum schlechtesten Spiel lassen und dann die

laufen