Eishockey-Pool-Algorithmus
Dies ist ein kleines lustiges Projekt, das ich begonnen habe zu versuchen und meine Chancen zu maximieren, unseren Bürohockey-Pool zu gewinnen. Ich versuche, den besten Weg zu finden, um 20 Spieler auszuwählen, die mir innerhalb einer maximalen Gehaltsobergrenze die meisten Punkte geben.
Stellen Sie sich zum Beispiel vor, dass die Rohdaten aus
bestehen- Der Spielername
- Position (Stürmer, Verteidiger, Torwart)
- Voraussichtliche Punktezahl für diese Saison
- Gehalt.
Jetzt möchte ich die 20 Spieler, die mir den meisten Punkt innerhalb der X Gehaltsobergrenze geben. Später, als Phase 2, möchte ich das gleiche tun, aber in diesem Fall möchte ich nur 12 Stürmer, 6 Verteidiger und 2 Torhüter.
Nun ist der offensichtliche Weg, einfach jede mögliche Kombination zu gehen, obwohl dies funktionieren wird, ist es keine gültige Option, da es bei 500 Spielern zu viele Kombinationsmöglichkeiten gibt. Ich könnte einige intelligente Filter hinzufügen, um die 500 Spieler auf die Top 50 Stürmer, Top 30 Verteidiger und die Top 15 Torhüter zu reduzieren, aber das wäre ein sehr langsamer Prozess.
Ich frage mich, ob es andere Algorithmen gibt, um das zu implementieren. Dies ist nur zum Spaß und keine wichtige Geschäftsanforderung. Aber wenn du ein paar Gedanken darüber hast, wie es weitergeht, lass es mich wissen.
Mein erster Versuch war die Verwendung des Rucksack-Algorithmus mit Hilfe von anderen Quellen. Es scheint nur mit dem Gehalt als Parameter zu funktionieren. Ich habe Mühe herauszufinden, wie man den 20-Spieler-Team-Parameter hinzufügt. Sein in .Net sollte aber einfach in Java zu konvertieren sein.
Ich dachte daran, eine separate Schleife zu machen, um die besten Teams mit 20 Spielern ohne Gehalt zu ermitteln und dann die beiden Listen zu vergleichen, bis ich das Team gefunden habe, das auf der Liste am höchsten ist. Nicht sicher.
%Vor%Danke für Ihre Hilfe!
5 Antworten
Leider sollten Sie nicht erwarten, eine gute Lösung für dieses Problem zu finden, da es NP-schwer ist . Außer P = NP gibt es keine polynomialen Zeitalgorithmen, und erschöpfende Suche ist wahrscheinlich eine von die besten Algorithmen (obwohl Sie einige Heuristiken verwenden könnten, um es zu beschleunigen).
Um zu sehen, dass dieses Problem NP-schwer ist, zeigen wir Ihnen, wie Sie das Rucksackproblem reduzieren können es in polynomieller Zeit. Gegeben sei ein Fall des Teilmengen-Summenproblems, bestehend aus einer Menge S = {(Gewicht <1>, Wert <1>), (Gewicht 2, Wert < sub> 2 ), ..., (Gewicht n <, Wert n <}} und Gewichtsgrenze k, wir können eine Instanz Ihres Hockey-Problems konstruieren Erstellen einer Reihe von Spielern, deren Gehalt das Gewicht ist und deren erwartete Punkte der Wert ist. Wir versuchen dann, die maximale Gewichtskombination von Spielern zu finden, deren Gehalt k nicht übersteigt, was dann identisch mit der maximalen Summe ist, die Sie im ursprünglichen Rucksackproblem machen können, das das Zielgewicht nicht überschreitet.
Wie der von Ihnen gepostete Code jedoch zeigt, gibt es einen pseudopolynomialen Zeitalgorithmus zur Lösung des Rucksackproblems. Unter der Annahme, dass die Gehälter niedrig sind (oder dass Sie sie auf kleine Zahlen normalisieren können), können Sie dies möglicherweise mit gutem Erfolg nutzen.
Obwohl es zweifelhaft ist, dass es einen polynomiellen Algorithmus gibt, um die exakte Antwort zu erhalten, gibt es einen polynomiellen Algorithmus, um Lösungen für das Rucksackproblem zu finden, wenn Sie mit einer ungefähr optimalen Lösung einverstanden sind. Weitere Informationen finden Sie diese Hinweise , die zwei Algorithmen enthalten . Interessanterweise stützen sie sich auf den Pseudopolynomialzeitalgorithmus, den Sie zu verwenden scheinen, also sind sie vielleicht einfach zu implementieren?
Entschuldigen Sie die Hoffnung auf eine schöne Lösung mit Mathe ... NP-harte Probleme tendieren dazu. : - (
Zeichnen Sie die Spieler auf einer Grafik, X-Achse ist Punkte, Y-Achse ist Gehalt, Nullen im Ursprung. Untere rechte Spieler werden begehrenswerte billige Highscorer sein, obere linke Spieler werden unerwünschte teure niedrige Torschützen sein, Spieler auf der Diagonale werden gleichwertig sein (gleiche Kosten pro Punkt). Fegen Sie einen ursprungsverankerten Radius von der X-Horizontalen gegen den Uhrzeigersinn bis zur Y-Vertikalen, um eine immer größer werdende Kuchenscheibe zu bilden, bis entweder 20 Spieler innerhalb der Scheibe sind oder die Gesamtgehälter innerhalb der Scheibe die Kappe erreichen. Wenn Sie die $ cap, aber nicht 20 Spieler erreichen, löschen Sie den Spieler "oben links" innerhalb des Slices und fahren Sie fort. Wenn Sie 20 Spieler erreichen, aber nicht die Obergrenze, können Sie einen Niedrigscorer aus dem Slice löschen, um Platz für einen Spieler mit höherem Scoring zu schaffen, der gerade das Segment betritt, wodurch Ihre Gesamtkosten pro Punkt unnötig steigen, aber da es lustiges Geld ist und du bist kein richtiger Besitzer, pass auf.
Eine unterhaltsame Art, dieses Problem anzugehen, ist die Verwendung eines genetischen Algorithmus . Und eigentlich habe ich genau das für meinen eigenen Hockeypool gemacht!
Sie können den ganzen Scala-Code hier sehen, wenn Sie neugierig sind, aber das Herzstück ist:
%Vor%Es beginnt mit dem Erzeugen einer zufälligen Sammlung von gültigen Aufstellungen (unter Berücksichtigung von Gehaltsobergrenzen und Positionsbeschränkungen). Für jede Iteration wird dann eine neue Population generiert, indem eine Kombination aus Turnierauswahl und Bergsteigen . "Fitness" ist einfach definiert als die erwartete Anzahl von Punkten für eine Aufstellung mit dem niedrigsten Gehalt als Tiebreaker.
Es ist natürlich nur eine Heuristik, aber wenn Ihre Liste der Spieler nicht zu groß ist und Sie es sich leisten können, den Algorithmus eine Weile laufen zu lassen, besteht eine gute Chance, dass Sie eine ziemlich optimale Lösung finden.
Das Problem mag schwierig sein, aber Sie können die Tatsache nutzen, dass Ihr Torwart nicht in der Offensive spielt (formeller: die von Ihnen ausgewählten Entitäten haben unterschiedliche Kategorien), um Ihre Laufzeit zu verbessern.
Vielleicht möchten Sie auch eine ungefähre Lösung für Ihr Problem finden. Verwenden Sie diesen Wert, um die optimale Lösung zu verknüpfen und danach zu suchen.
Sie können es einfach als ILP formulieren. Sie zu lösen, ist auch NP-Hard, aber die Probleminstanz scheint nicht so groß zu sein, so dass sie vielleicht perfekt lösbar ist (ein Solver ist beispielsweise lpsolve). Auch wenn es wegen der Problemgröße nicht perfekt lösbar ist, gibt es gute Heuristiken für ILP.
Tags und Links knapsack-problem