Algorithmus zum Zuordnen bevorzugter Partner in Dreiergruppen
https://stackoverflow.com/questions/294660
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Was ist ein guter Algorithmus, um dieses Problem zu lösen?
Ich habe drei Gruppen von Menschen – Gruppe A, Gruppe B und Gruppe C.In jeder Gruppe sind gleich viele Personen.Jeder von ihnen hat eine Liste mit Personen aus den anderen Gruppen, mit denen er zusammenarbeiten möchte.Ich möchte alle diese Personen in Dreiergruppen zusammenfassen (einer von A, einer von B und einer von C), sodass jeder in einer Gruppe mit den anderen Personen in seiner Gruppe zusammenarbeiten möchte.
Wie kann ich diese Gruppen schnell finden?Wenn es keine Möglichkeit gibt, alle glücklich zu machen, sollte der Algorithmus zunächst dafür sorgen, dass möglichst viele Gruppen aus drei Personen bestehen, die miteinander arbeiten möchten, und dann so viele Personen in den anderen Gruppen glücklich machen.
Ein letzter Punkt:Menschen einigen sich darauf, mit wem sie zusammenarbeiten möchten (wenn Person X mit Person Y zusammenarbeiten möchte, dann möchte auch Y mit X zusammenarbeiten).Wenn Sie auch eine große Angabe zur Laufzeit Ihres Algorithmus machen könnten, wäre das großartig!
Lösung
Das ist wie das stabile Ehe Problem, aber mit drei Parteien statt zwei.
Haben Sie einen Blick auf effiziente Lösungen für frühere Problem (zweiteilige Graph Matching) und passen sie an Ihren Bedürfnissen.
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 haben diese Paare mit einem Arbeiter aus der Gruppe C, die jeweils gekoppelt werden. Lassen Sie sich nur die Paare Arbeiter bevorzugen, die beide Mitglieder des Paares einigen sich auf (da ihre Listen). Beachten Sie, dass dies nur ein lokales Optimum geben.
Eine optimale Lösung für k-partite Matching ist NP-schwer zu finden:
http://www.math.tau.ac .il / ~ safra / PapersAndTalks / k-DM.ps
Sehen Sie dieses Papier für eine nicht optimale Lösung für das k-partite Matching-Problem:
Ich bin sicher, dass Sie andere auf Google finden sich jetzt, dass Sie die Bedingungen für die Suche kennen. Ich weiß nicht, ob es ein effizienter Algorithmus ist die optimale Lösung für k = 3 geben.
Andere Tipps
Dies unterscheidet sich von einer Ausweitung des Problems der stabilen Ehe, da, wie ich die Frage des OP verstehe, die Personen in jeder Gruppe keine geordnete Liste haben, mit wem sie von den meisten bis zu den wenigsten zusammenarbeiten möchten;Es ist eine binäre Beziehung (wollen/nicht wollen).
Dies lässt sich als ganzzahliges Programmierproblem formulieren, das recht schnell gelöst werden kann.Ich gebe unten die mathematische Formulierung des Problems an;Sie können ein Paket wie glpk oder AMPL/CPLEX verwenden, um die Daten zu verarbeiten.
Definieren Sie die folgenden Matrizen:
M1 = |A| x |B| Matrix, wo
M1(a,b) = 1 wenn a (angegebenes Mitglied von A) bereit ist, mit b (angegebenes Mitglied von B) zusammenzuarbeiten, andernfalls 0
M2 = |A| x |C| Matrix, wo M2(a,c) = 1 wenn a (angegebenes Mitglied von A) bereit ist, mit c (angegebenes Mitglied von C) zusammenzuarbeiten, andernfalls 0
M2 = |B| x |C| Matrix, wo
M3(b,c) = 1 wenn b (angegebenes Mitglied von B) bereit ist, mit c (angegebenes Mitglied von C) zusammenzuarbeiten, andernfalls 0
Definieren Sie nun eine neue Matrix, die wir für unsere Maximierung verwenden werden:
X = |A| x |B| x |C| Matrix, wo
X(a,b,c) = 1 wenn wir dafür sorgen, dass a, b und c zusammenarbeiten.
Definieren Sie nun unsere Zielfunktion:
//Maximieren Sie die Anzahl der Gruppen
maximieren Sum[(all a, all b, all c) X(a,b,c)]
unterliegen folgenden Einschränkungen:
//Um sicherzustellen, dass niemand in zwei Gruppen eingeteilt wird
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 aus kompatiblen Personen bestehen
Für alle a,b,c: X(a,b,c) <= M1(a,b)/3 + M2(a,c)/3 + M3(b,c)/3
Nur eine kurze Notiz für dieses Problem. Erstens ist es kein Beispiel für das stabile Ehe Problem, noch in der Tat eine Erweiterung davon (das heißt das 3D stabile Matching-Problem). Ganz gleich, aber ist es ein 3D-Matching-Problem, die NP-schwer sein bekannt (siehe Garey und Johnson). Um ein solches Problem in einer angemessenen Art und Weise zu lösen, ist es wahrscheinlich, dass Sie benötigen, um irgendeine Form von Zwang, integer zu verwenden, oder die lineare Programmierung (andere Methoden existieren). Etwas, das von Nutzen sein könnte, ist die neue Microsoft Solver-Stiftung, so check it out.
So starten Sie mit, Sie über alle Tatsachen beseitigen, wo die beiden Parteien haben disjunkte Listen, mit wem sie in der dritten Gruppe arbeiten. Starten Sie dann eine Brute-Force, Tiefensuche, immer aus den am wenigsten Kommissionierung beliebt beliebtesten.
Alternativ entspricht die obige Eliminierung, bildet eine Liste aller möglichen Trios und Arbeit aus, dass statt.
Ich lief in ein ähnliches Problem und schrieb nur ein Skript, dass Brute-Kräfte es ... http: // Grouper. owoga.com/
Meine erste Gedanken waren: für eine größere Gruppe, die zu groß, um Brute-Force war, irgendeine Art von genetischem Algorithmus? Machen N Zufall Swaps M-mal. Bewerten Sie jede neue Anordnung durch eine ‚Glück‘ Funktion. Nehmen Sie die besten wenig, Rasse, zu wiederholen.
Für kleine Gruppen I durch Schleifen über ein paar Gruppen bessere Ergebnisse am Ende, die Suche nach dem ‚besten‘ swap (derjenige, der die höchste Gesamt ‚Glück‘ Verstärkung erzeugt wird), so dass das, dann wiederholen.
