Algorithmus zum Abgleich von Paaren

Question

Ich arbeite an einer Rails-App, bei der ständig Benutzer zusammengeführt werden müssen. Grundsätzlich brauche ich einen Algorithmus, der als seine Eingabe eine Liste von Benutzern nimmt und eine Liste von Paaren, die am besten übereinstimmen zurückgibt. Benutzer werden als gute Übereinstimmungen durch Kriterien wie hat mehr Interessen gemeinsam oder Abstand zwischen ihnen. Im Allgemeinen muss ich in der Lage sein, zu optimieren, was als "gute Übereinstimmung" gilt, aber ich brauche einfach eine Richtung für den Algorithmus, der eine Reihe von Benutzern nimmt und eine Reihe von Paaren zurückgibt.

Wenn es hilft, habe ich eine Methode im Benutzermodell, die als Parameter einen anderen Benutzer nimmt und eine Bewertung zurückgibt, wie gut die Übereinstimmung ist. Ich brauche Hilfe, um das beim Massenabgleich zu verwenden.

Ich habe vor, die Benutzer in eine Tabelle eintragen zu lassen und dann einen Cron-Job zu starten, der die Liste so oft durchläuft, um die besten Paarübereinstimmungen zwischen allen zu finden. Hat jemand irgendwelche Ideen?

Vielen Dank!

Answer 1

Jack Edmonds' Algorithmus findet eine Übereinstimmung mit maximalem Gewicht in einem allgemeinen (nicht zweistufigen) Graphen.

Wladimir Kolmogorow hat eine Papier und eine Implementierung in C++.

---

Nachtrag: Wenn es Ihnen nichts ausmacht, dass Sie nicht die beste Übereinstimmung erhalten, und Sie etwas wollen, das einfach zu berechnen ist, warum verwenden Sie dann nicht den einfachen Gieralgorithmus? In jeder Phase werden die beiden Benutzer mit der höchsten Punktzahl zusammengeführt. Dann werden die beiden Benutzer mit der höchsten Punktzahl unter den verbleibenden Benutzern gepaart, und so weiter.