Das Problem der maximalen Diversität erfordert die Auswahl von Elementen aus einer Liste von Elementen, sodass die Diversität, die als metrischer Abstand zwischen Elementen definiert ist, maximiert wird.
Ich habe ein einfacheres Problem, von dem ich gehofft hatte, es auf einfachere Weise lösen zu können. In meinem Fall habe ich eine Liste von Elementen mit jeweils einem bestimmten nicht eindeutigen Schlüssel. Ich möchte Elemente aus meiner Liste auswählen, damit die maximale Anzahl von Elementen pro Schlüssel minimiert wird .
zB wenn meine Liste ist:
('a', 5), ('b', 4), ('c', 2), ('a', 6), ('b', 5)
und wir müssen Elemente wählen , eine optimale Lösung wäre eine Liste, die ein Element für jeden Schlüssel enthält.
Gibt es dafür einen Algorithmus, der einfacher ist als der für das Problem der maximalen Vielfalt?
quelle
Antworten:
Der folgende Algorithmus sollte funktionieren.
Der Algorithmus läuft in mehreren Runden ab. In jeder Runde sei die Anzahl der verbleibenden Gegenstände. Nehmen Sie einen Gegenstand pro Schlüssel, bis zu Gegenstände, und entfernen Sie diese Gegenstände. Wenn wir Elemente genommen haben, wird der Algorithmus beendet. Andernfalls fahren Sie mit der nächsten Runde fort.m' m' m'
Wir überlassen den Korrektheitsnachweis (oder ein Gegenbeispiel) dem Leser.
quelle
Wenn ich ein bisschen mehr darüber nachdenke, denke ich, dass ich einen "One-Pass" -Algorithmus habe, um dies zu lösen.
Lass es seinn Artikel mit k Schlüssel, mit nich Elemente für jeden Schlüssel. Wir wollen wählenmich≤nich , so dass ∑mich= m , und das maxmich wird minimiert.
Klar, wenn für allenich wir haben nich> m / k wählen wir einfach mich= m / k . Andernfalls verwenden wir den folgenden Algorithmus:
Dieser Algorithmus sollte seinO ( n ) In der Länge der Liste ist die Annahme, dass die Anzahl der verschiedenen Schlüssel im Vergleich vernachlässigbar ist, vernachlässigbar.
quelle