Algorithmus, um bevorzugte Partner zu Dreiergruppen zusammenzufassen

Question

Was ist ein guter Algorithmus, um dieses Problem zu lösen?

Ich habe drei Gruppen von Menschen - Gruppe A, Gruppe B und Gruppe C. Es gibt die gleiche Anzahl von Menschen in jeder Gruppe. Sie haben jeweils eine Liste von Personen in den anderen Gruppen, mit denen sie arbeiten möchten. Ich möchte alle diese Personen in Gruppen von 3 (eine von A, eine von B und eine von C) zusammen fassen, so dass jeder in einer Gruppe mit den anderen Menschen in ihrer Gruppe arbeiten möchte.

Wie kann ich diese Gruppen schnell finden? Wenn es keinen Weg gibt, alle glücklich zu machen, dann sollte der Algorithmus zuerst so viele Gruppen dazu bringen, drei Personen zu haben, die miteinander arbeiten wollen, und dann so viele Leute in den anderen Gruppen glücklich machen.

Ein letzter Punkt: Die Leute sind sich einig, mit wem sie arbeiten wollen (wenn Person x mit Person y arbeiten will, will y auch mit x arbeiten). Wenn Sie auch einen großen O der Laufzeit Ihres Algorithmus geben könnten, wäre das großartig!

Answer 1

Dies ist wie das stabile Ehe-Problem, aber mit 3 Parteien statt zwei.

Werfen Sie einen Blick auf effiziente Lösungen für frühere Probleme (Bi-Partit Graph Matching) und passen Sie diese an Ihre Bedürfnisse an.

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

Eine Anpassung an den ersten Build Arbeitspaare aus den Gruppen A und B nur sein könnte. Dann müssen diese Paare jeweils mit einem Arbeiter der Gruppe C gepaart werden. Lasst die Paare nur Arbeiter bevorzugen, mit denen sich beide Mitglieder des Paares einig sind (angesichts ihrer Listen). Beachten Sie, dass dies nur ein lokales Optimum ergibt.

Eine optimale Lösung für k-partite passende NP-schwer zu finden:

http://www.math.tau.ac.il/~safra/PapersAndTalks/k-DM.ps

diese Papiersorte für eine nicht optimale Lösung für das k-partite Matching-Problem:

http://books.google.com/books?id=wqs31L1MF4IC&pg=PA309&lpg=PA309&dq=k-partite+matching&source=bl&ots=kgBuvi7ym_&sig=j3Y-nyo51y8qp0-HwToyUlkao4A&hl=de&sa=X&oi=book_result&resnum=1&ct=result

Ich bin mir sicher, dass Sie selbst andere auf Google finden können, da Sie die Suchbegriffe kennen. Ich weiß nicht, ob es einen effizienten Algorithmus gibt, der die optimale Lösung für k = 3 liefert.

Answer 2

Das ist anders als eine Erweiterung des stabilen Eheproblems, da, wie ich die Frage des OP verstehe, die Leute in jeder Gruppe keine geordnete Liste haben, mit wem sie am meisten arbeiten wollen; es ist eine binäre Beziehung (willig/nicht willig).

Dies kann als ein ganzzahliges Programmierproblem formuliert werden, das relativ schnell gelöst werden kann. Ich gebe die mathematische Formulierung des Problems unten; Sie können ein Paket wie glpk oder AMPL/CPLEX verwenden, um die Daten zu verarbeiten.

definieren die folgenden Matrizen:

M1 = |A| x |B| Matrix, wobei

M1(a,b) = 1 wenn ein (gegebenes Mitglied A) ist bereit, mit b zu arbeiten (gegebenen Mitglied B), und 0 sonst

M2 = |A| x |C| Matrix, wobei, wenn ein M2(a,c) = 1 (gegebenes Mitglied A) ist bereit, mit C zu arbeiten (Mitglied der C angegeben), und 0 sonst

M2 = |B| x |C| matrix, wh ere

M3(b,c) = 1 wenn b (gegebenes Mitglied B) ist bereit, mit C (angegeben Mitglied C) zu arbeiten, und 0 sonst

nun eine neue Matrix definieren wir für unsere Maximierung verwenden:

X = |A| x |B| x |C| Matrix, wo

X(a,b,c) = 1 wenn wir a, b und c zusammen arbeiten.

Nun definieren unsere Zielfunktion:

// die Anzahl der Gruppen maximieren

Sum[(all a, all b, all c) X(a,b,c)]

unterliegt den folgenden Einschränkungen maximieren:

// damit niemand wird gelegt in zwei Gruppen

Für alle Werte von a: Sum[(all j, k) X(a, j, k)] <= 1

Für alle Werte von b: Sum[(all i, k) X(i, b, k)] <= 1

Für alle Werte von c: Sum[(all i, j) X(i, j, c)] <= 1

// Um ​​sicherzustellen, dass alle Gruppen kompatibler Personen

für alle a, b, c zusammengesetzt sind: X(a,b,c) <= M1(a,b)/3 + M2(a,c)/3 + M3(b,c)/3

Answer 3

Zunächst können Sie alle Fakten eliminieren, bei denen die beiden Parteien disjunkte Listen haben, mit wem sie in der dritten Gruppe arbeiten werden. Dann starten Sie eine Brute-Force-, Tiefen-Suche zuerst, immer von der am wenigsten populärsten zu den beliebtesten.

Alternativ zu der obigen Eliminierung eine Liste aller möglichen Trios erstellen und davon arbeiten.

Answer 4

Nur eine kurze Notiz zu diesem Problem. Erstens ist es kein Beispiel für das Problem der stabilen Ehe, noch in der Tat eine Erweiterung davon (d. H. Das 3D-Problem der stabilen Übereinstimmung). Unabhängig davon ist es ein 3D-Matching-Problem, das als NP-schwer bekannt ist (siehe Garey und Johnson). Um ein solches Problem in vernünftiger Weise zu lösen, ist es wahrscheinlich, dass Sie eine Art von Constraint-, Integer- oder linearer Programmierung verwenden müssen (andere Methoden existieren). Etwas, das von Nutzen sein könnte, ist die neue Microsoft Solver Foundation, also schaut es euch an.

Answer 5

Ich stieß auf ein ähnliches Problem und schrieb nur ein Skript, das Brute-Kräfte es ...http://grouper.owoga.com/

Meine ersten Gedanken waren: für eine größere Gruppe, die zu brutal Kraft war, irgendeine Art von genetischen Algorithmus? Machen Sie N zufällige Swaps M-mal. Bewerten Sie jede neue Anordnung durch eine "Glück" -Funktion. Nimm die besten, züchte, wiederhole.

Für kleine Gruppen erzielte ich bessere Ergebnisse, indem ich einige Gruppen überschlug und den "besten" Swap fand (den, der den höchsten "Glück" -Gewinn generierte).