2016-05-16 4 views
-1

Angenommen, ich habe eine Reihe von Twitter-Benutzern und ihren Followern und möchte 5 Benutzer mit der größten Anzahl an Follower identifizieren. Wenn ich sie auffordere, eine Werbung für mein Produkt zu retweeten, würde sie die höchste Anzahl erreichen von Benutzern.Wie kann ich 5 meiner Twitter-Freunde so auswählen, dass die Anzahl ihrer Follower maximiert wird?

Ich habe keine formelle Programmierung oder Informatik-Ausbildung. Ich verstehe jedoch Algorithmen und grundlegende CS-Konzepte. Es wäre großartig, wenn eine Lösung so bereitgestellt werden könnte, wie es ein Laie könnte.

+0

Sortieren Sie das Array nach der Anzahl der Follower, die die Benutzer haben, und nehmen Sie die ersten fünf. Sortieren ist sehr einfach, weil es in den meisten Sprachen bereits implementiert ist. Beantwortet das Ihre Frage? –

+0

Hmm. Aber wenn die Top-5-Benutzer mit den meisten Followern eine große Anzahl ähnlicher Freunde haben, gibt mir diese Methode möglicherweise nicht die optimale Antwort. Ich möchte Nutzer mit den einzigartigsten Followern identifizieren, damit meine Werbung die größtmögliche Reichweite hat. – Aiden

Antwort

2

Dies ist das "Maximum Coverage Problem", eine Klasse von Problemen, die als schwierig zu lösen angesehen wird (sogenannte NP-Hard-Probleme). Sie können über das Problem auf Wikipedia lesen: https://en.wikipedia.org/wiki/Maximum_coverage_problem

Ein einfacher Algorithmus, um es zu lösen, ist alle Teilmengen der Größe 5 Ihrer Freunde zu zählen, und messen Sie die Größe der Union ihrer Anhänger. Es ist keine effiziente Lösung, denn wenn Sie n Freunde haben, dann gibt es ungefähr n^5 Teilmengen der Größe 5 (vorausgesetzt, n ist groß).

Wenn Sie eine Lösung wünschen, die Code-fähig ist und in realen Fällen einigermaßen effizient ist, können Sie das Problem als "lineares Ganzzahl-Programm" (ILP) darstellen und einen Solver wie GLPK verwenden. Die Details zur Darstellung der maximalen Abdeckung als ILP sind auf der Wikipedia-Seite angegeben. Es funktioniert jedoch etwas mühsam und funktioniert möglicherweise immer noch nicht gut, wenn das Problem groß ist.

Verwandte Themen