Aus einem Pool von 1000 Bewerbern soll ein Team von 100 Mitgliedern zusammengestellt werden. Jeder Bewerber bekommt die 99 anderen Bewerber, die er als Teamkollegen haben möchte.
Jedes mögliche Team erhält eine Punktzahl, die misst, wie gut es die Teamkameradenpräferenzen seiner Mitglieder erfüllt. Wenn Lisa in einem Team ist und 11 der Leute auf Lisas Wunschliste sind auch im Team, das Team bekommt 11 Punkte für Lisa. Die Punkte für alle Mitglieder werden addiert. Das theoretische Maximum, das ein mögliches Team bekommen kann, ist 99 * 100. Das Minimum ist 0.
Jetzt wollen wir das Team mit der höchsten Punktzahl finden. Der Versuch, dieses Problem durch Berechnung des Ergebnisses für jede mögliche Kombination (≈ 10 ^ 140) zu erzwingen, ist keine Option.
Gibt es einen cleveren Algorithmus, der eine Abkürzung zur besten Antwort braucht oder muss man sich mit einem Algorithmus begnügen, der eine gute Antwort findet?
Ich denke, wenn Sie das effizient lösen könnten, könnten Sie das Ссылка effizient lösen - wo es eine Verbindung zwischen zweien gibt Knoten setzen jeden Knoten auf die Liste der Knoten, mit denen der andere arbeiten möchte. Wenn man sich den Artikel anschaut, wird es meiner Meinung nach schwierig sein, eine garantiert gute Annäherung zu finden, es sei denn, Ihr Problem hat eine spezielle Struktur.
Sie könnten versuchen, einen Hill Climbing -Algorithmus zu verwenden. Beginnen Sie mit einem Mitglied, das "beliebt" ist (am häufigsten von anderen Mitgliedern ausgewählt), und fügen Sie schrittweise neue Mitglieder hinzu, die den Team-Punktestand am meisten erhöhen. Dies ist leider nicht garantiert, um die beste Lösung zu finden, aber es wird wahrscheinlich gute finden. Um Ihre Lösung zu verbessern, können Sie Simulated Annealing ausprobieren.
Tags und Links algorithm combinations genetic-algorithm mathematical-optimization