Algorithmus für konkretes Problem gesucht

[BlackJack]

@Hyperion: Denke ich nicht. Die Bedingungen schränken doch recht gut ein, so dass man viele Wege in dem Baum gar nicht weiterverfolgen muss.

[EyDu]

@BlackJack: Natürlich liefert mein Ansatz keinen optimalen Wert, aber je nach Anzahl der möglichen Spieler kann das finden einer optimalen Mannschaft, nach grobem Überschlag, relativ aufwändig sein. Da ich Bewertungen von Fußballspielen keine schlechten Eigenschaften ansehen kann (welche die gefundene Lösung unglaublich schlecht macht), scheint mir auf den ersten Blick eine Annäherung eine ausreichend gute Näherung zu liefern. Es hängt halt davon ab, was mit dem Resultat genau gemacht werden soll.

Ich würde vorher allerdings auch die perfekte Lösung ausprobieren, da sie einfach schnell zu implementieren ist. Mit geschickten Abschneiden von Ästen sieht die Sache, zumindest bei einer normalen Größe einer Fußballmannschaft, nicht mehr so dramatisch aus.

[BlackJack]

@EyDu: Ja, es kommt auf den Einsatzzweck an. Bei der Beschreibung würde ich aber tatsächlich erwarten, dass das Optimum gesucht ist, damit man zum Beispiel den Mitspielern sagen kann wie weit ihre Mannschaftsaufstellung vom Ideal entfernt war.

[EmaNymton]

Erstmal danke für die vielen Vorschläge und die Diskussion. Ich habe gestern nochmal meinen letzten Ansatz versucht und denke, dass er die optimale Aufstellung findet, ohne eine der Bedingungen zu verletzen. Ich hätte allerdings gerne nochmal eure Meinung dazu gehört:

• Finde alle Spieler die gespielt haben und schreibe sie in eine Liste.
• Wähle jeweils den Spieler der Liste mit der höchsten Punktzahl aus und schreibe ihn in eine Liste "besteElf". Wenn bei einer Position die Minimalanzahl der Besetzung erreicht ist oder schon 3 Spieler aus dem selben Verein in besteElf sind, schreibe den Spieler in eine Liste "bank".
• Wenn die beste Elf noch nicht aus 9 Spielern besteht (kann passieren, wenn für eine Position z.B. nicht genügend Spieler zur Verfügung standen), fülle die jeweilige Position mit Dummys auf (Punkte sind dann laut Regel -25), alternativ kann man auch einen Spieler nehmen, der nicht gespielt hat.
• Wähle jeweils den Spieler von der "bank" mit der höchsten Punktzahl aus und schreibe ihn in die "besteElf". Wenn bei einer Position die Maximalanzahl der Besetzung erreicht ist oder schon 3 Spieler aus dem selben Verein in besteElf sind, ignoriere den Spieler.

Damit sollte ich doch sowohl immer die drei besten Spieler aus einem Verein erhalten, als auch meine Besetzungsregeln (minimal/maximal) erfüllen, oder?

Ich hab mal zwei Beispiele vom letzten Spieltag angefügt, um das nochmal zu verdeutlichen:

Code: Alles auswählen

eingesetzte Spieler:
('Neuer', 'Torwart', 63, 'Bayern M\xc3\xbcnchen')
('Barth', 'Abwehr', -28, 'SC Freiburg')
('H\xc3\xb6wedes', 'Abwehr', 35, 'FC Schalke 04')
('Bender', 'Mittelfeld', -4, 'Borussia Dortmund')
('Ribery', 'Mittelfeld', 52, 'Bayern M\xc3\xbcnchen')
('Usami', 'Mittelfeld', 11, 'Bayern M\xc3\xbcnchen')
('Tiffert', 'Mittelfeld', -1, '1. FC Kaiserslautern')
('Traore', 'Mittelfeld', -12, 'VfB Stuttgart')
('Ochs', 'Mittelfeld', -40, 'VfL Wolfsburg')
('Kie\xc3\x9fling', 'Sturm', -5, 'Bayer Leverkusen')
('Eigler', 'Sturm', -20, '1. FC N\xc3\xbcrnberg')
('Dembel\xc3\xa9', 'Sturm', -40, 'SC Freiburg')
('Huntelaar', 'Sturm', 180, 'FC Schalke 04')
('Torun', 'Sturm', 77, 'Hertha BSC')
ersten 9 Spieler:
('Huntelaar', 'Sturm', 180, 'FC Schalke 04')
('Torun', 'Sturm', 77, 'Hertha BSC')
('Neuer', 'Torwart', 63, 'Bayern M\xc3\xbcnchen')
('Ribery', 'Mittelfeld', 52, 'Bayern M\xc3\xbcnchen')
('H\xc3\xb6wedes', 'Abwehr', 35, 'FC Schalke 04')
('Usami', 'Mittelfeld', 11, 'Bayern M\xc3\xbcnchen')
('Tiffert', 'Mittelfeld', -1, '1. FC Kaiserslautern')
('Barth', 'Abwehr', -28, 'SC Freiburg')
Bankspieler:
('Bender', 'Mittelfeld', -4, 'Borussia Dortmund')
('Kie\xc3\x9fling', 'Sturm', -5, 'Bayer Leverkusen')
('Traore', 'Mittelfeld', -12, 'VfB Stuttgart')
('Eigler', 'Sturm', -20, '1. FC N\xc3\xbcrnberg')
('Ochs', 'Mittelfeld', -40, 'VfL Wolfsburg')
('Dembel\xc3\xa9', 'Sturm', -40, 'SC Freiburg')

--------------------------
Beste Elf von X am 2. Spieltag:
Torwart:
  Neuer 		63 	Bayern München
Abwehr:
  Höwedes 	35 	FC Schalke 04
  Barth 		-28 	SC Freiburg
  Dummy 		-25 	Dummy
Mittelfeld:
  Ribery 		52 	Bayern München
  Usami 		11 	Bayern München
  Tiffert 		-1 	1. FC Kaiserslautern
  Bender 		-4 	Borussia Dortmund
Sturm:
  Huntelaar 	180 	FC Schalke 04
  Torun 		77 	Hertha BSC
  Kießling 		-5 	Bayer Leverkusen

Aufstellung im: 1 3 4 3

14 Spieler von 28 möglichen haben gespielt.

Bestmögliche Ausbeute am Spieltag: 355

Code: Alles auswählen

eingesetzte Spieler:
('Starke', 'Torwart', 94, '1899 Hoffenheim')
('Benaglio', 'Torwart', -26, 'VfL Wolfsburg')
('Reinartz', 'Abwehr', 48, 'Bayer Leverkusen')
('Boateng', 'Abwehr', 45, 'Bayern M\xc3\xbcnchen')
('Westermann', 'Abwehr', -2, 'Hamburger SV')
('Vorsah', 'Abwehr', 48, '1899 Hoffenheim')
('Tasci', 'Abwehr', 46, 'VfB Stuttgart')
('Lell', 'Abwehr', 24, 'Hertha BSC')
('Bellinghausen', 'Abwehr', 10, 'FC Augsburg')
('M\xc3\xbcller', 'Mittelfeld', -1, 'Bayern M\xc3\xbcnchen')
('Rudy', 'Mittelfeld', 71, '1899 Hoffenheim')
('Ekici', 'Mittelfeld', -29, 'Werder Bremen')
('Draxler', 'Mittelfeld', 37, 'FC Schalke 04')
('Dejagah', 'Mittelfeld', -48, 'VfL Wolfsburg')
('Salihamidzic', 'Mittelfeld', -50, 'VfL Wolfsburg')
('Ndjeng', 'Mittelfeld', 6, 'FC Augsburg')
('Gomez', 'Sturm', -2, 'Bayern M\xc3\xbcnchen')
('Podolski', 'Sturm', -1, '1. FC K\xc3\xb6ln')
('Obasi', 'Sturm', 20, '1899 Hoffenheim')
('Gogia', 'Mittelfeld', -15, 'FC Augsburg')
ersten 9 Spieler:
('Starke', 'Torwart', 94, '1899 Hoffenheim')
('Rudy', 'Mittelfeld', 71, '1899 Hoffenheim')
('Reinartz', 'Abwehr', 48, 'Bayer Leverkusen')
('Vorsah', 'Abwehr', 48, '1899 Hoffenheim')
('Tasci', 'Abwehr', 46, 'VfB Stuttgart')
('Draxler', 'Mittelfeld', 37, 'FC Schalke 04')
('Ndjeng', 'Mittelfeld', 6, 'FC Augsburg')
('Podolski', 'Sturm', -1, '1. FC K\xc3\xb6ln')
('Gomez', 'Sturm', -2, 'Bayern M\xc3\xbcnchen')
Bankspieler:
('Boateng', 'Abwehr', 45, 'Bayern M\xc3\xbcnchen')
('Lell', 'Abwehr', 24, 'Hertha BSC')
('Obasi', 'Sturm', 20, '1899 Hoffenheim')
('Bellinghausen', 'Abwehr', 10, 'FC Augsburg')
('M\xc3\xbcller', 'Mittelfeld', -1, 'Bayern M\xc3\xbcnchen')
('Westermann', 'Abwehr', -2, 'Hamburger SV')
('Gogia', 'Mittelfeld', -15, 'FC Augsburg')
('Benaglio', 'Torwart', -26, 'VfL Wolfsburg')
('Ekici', 'Mittelfeld', -29, 'Werder Bremen')
('Dejagah', 'Mittelfeld', -48, 'VfL Wolfsburg')
('Salihamidzic', 'Mittelfeld', -50, 'VfL Wolfsburg')
--------------------------
Beste Elf von XX am 2. Spieltag:
Torwart:
  Starke 		94 	1899 Hoffenheim
Abwehr:
  Reinartz 		48 	Bayer Leverkusen
  Vorsah 		48 	1899 Hoffenheim
  Tasci 		46 	VfB Stuttgart
  Boateng 		45 	Bayern München
  Lell 		24 	Hertha BSC
Mittelfeld:
  Rudy 		71 	1899 Hoffenheim
  Draxler 		37 	FC Schalke 04
  Ndjeng 		6 	FC Augsburg
Sturm:
  Podolski 		-1 	1. FC Köln
  Gomez 		-2 	Bayern München

Aufstellung im: 1 5 3 2

20 Spieler von 28 möglichen haben gespielt.

Bestmögliche Ausbeute am Spieltag: 416

Ich kann jetzt auch noch den Ansatz verfolgen, in dem ich alle Möglichkeiten durchprobiere, und beide laufen lassen aber ich bin der Meinung, dass ich damit schon meine optimale Aufstellung gefunden habe. Irgendwo ein Denkfehler/Sonderfall vergessen?

[BlackJack]

@EmaNymton: Du hast hier jetzt anscheinend wieder die Bedingung höchstens x Spieler von einem Verein nicht mehr erwähnt. Da könnte es wie schon gesagt zu Situationen kommen, bei denen man nicht ums durchprobieren der Kombinationen herum kommt, um die optimale Besetzung zu finden.

Edit: Okay, Du hast die Bedingung erwähnt. Sollte aber am Problem nichts ändern.

Edit2: Wieso Spieler die aus einem Verein kommen der schon x-mal vertreten ist, eigentlich noch auf die Bank setzen? Im letzten Schritt werden die dann ja wieder explizit ignoriert.

[EmaNymton]

Wie könnte so eine Situation aussehen? Wenn es mehrere Spieler aus einem Verein gibt, werden die 3 besten gewählt, d.h. ich möchte keinen Spieler tauschen.

Edit2: Wieso Spieler die aus einem Verein kommen der schon x-mal vertreten ist, eigentlich noch auf die Bank setzen? Im letzten Schritt werden die dann ja wieder explizit ignoriert.

Jupp, ist überflüssig!

[crs]

Bsp.:
Team A: 3 Offensivspieler mit je 100 Punkten, 1 Torwart mit 50 Punkten
Team B: 1 Offensivspieler mit 99 Punkten
Alle anderen Spieler mit 0 Punkten.

Dann kann der Algorithmus fuer eine optimale Loesung nicht die drei besten Spieler aus Team A waehlen.

[Hyperion]

@crs: Das stimmt. Aus Deinem Beispiel geht aber noch nicht explizit hervor, was daran schief gehen kann. Das Problem besteht nämlich jetzt darin, welche Spieler aus einem Verein ich wähle, bzw. welche ich rauswerfe. Auf den ersten Blick würde man die drei Mittelfeldspieler wählen und den Torwart rauskegeln.

Aber: Was wenn das mit Abstand beste Torwart aus der Gesamtauswahl war? Dann wäre es ja gerade sinnvoll den Torwart zu wählen, und lieber einen Punkt durch den Tausch mit dem 99er Mittelfeldspieler aus Team B in Kauf zu nehmen. Und genau diese Entscheidung ist imho nicht effizient zu treffen, sondern da hilft nur ein Bruteforce-Ansatz, der eben alle möglichen Kombinationen ausprobiert und dadurch die optimale findet.

Genau das sind die Situationen, die ich und BlackJack bereits angesprochen hatten - nur halt anhand eines Beispiels

[EmaNymton]

Ok, jetzt wird's klarer, danke. Dann weiß ich ja jetzt was ich noch zu tun habe

[crs]

@crs: Das stimmt. Aus Deinem Beispiel geht aber noch nicht explizit hervor, was daran schief gehen kann.

Imho geht das daraus schon hervor. Da nur max. 3 Offensivspieler erlaubt sind wuerde der vorher beschriebene Algorithmus genau die 3 Offensivspieler aus Team A auswaehlen und den Spieler aus Team B nicht einsetzen, also 300 Punkte. Optimal waere in dem Beispiel aber offensichtlich nur 2 Offensivspieler aus Team A und dafuer den Torwart, dazu den Offensivspieler aus Team B, also 349 Punkte.

Welche Spieler man tauschen muss ist natuerlich nicht immer so offensichtlich, aber es ist zumindest ein Gegenbeispiel fuer den Algorithmus

[EmaNymton]

Das Ergebnis (349) liefert der Algorithmus auch, denn es werden erstmal zwei Offensivspieler (mit Offensiv meinst du Sturm?) bis zur Minimalbesetzung (2) aufgefüllt. Der dritte von A kommt auf die Bank, dann kommt Spieler aus B mit 99 Punkten auch auf die Bank. Dann kommt der Torwart, wird in die beste Elf gesetzt.
Nun werden alle Spieler von der Bank durchprobiert, da aber schon drei Spieler von Team A in der besten Elf sind, kommt der Spieler mit 99 Punkten ins Team.

Ändert aber nix am Problem!

[EmaNymton]

So, wollte mich nur nochmal melden, ich habe es jetzt mit dem Durchprobieren aller Möglichkeiten hinbekommen und es geht erstaunlich schnell. Im schlimmsten Fall muss er ja 28 über 11 Möglichkeiten durchprobieren (ca. 21,5 Millionen), in der Regel aber eher so 22 über 11 (ca. 7 Millionen).
Mein Algorithmus kann bestimmt noch optimiert werden, aber für 8 Teilnehmer am Spiel dauert die Auswertung 15 Sekunden. Das ist für mein Vorhaben völlig vertretbar.

Er hat auch noch bessere Aufstellungen gefunden, auch wenn es sich da nur um 4 Punkte unterscheidet

Vielen Dank nochmal für eure Geduld und eure Hilfe!

Gruß EmaNymton

[Hyperion]

Ich hätte da jetzt durchaus Interesse am fertigen Algo Muss ja nicht das komplette Script sein, aber evtl. ein kleines Snippet als Demo?

[EmaNymton]

Kein Problem, aber ich muss dich enttäuschen, wenn du etwas anderes erwartest, als dass ihr es in 10 Minuten nicht auch hin bekommen hättet

Ich habe zunächst abgewägt, wie viele Möglichkeiten es gibt. Nach den bisherigen Spieltagen und Erfahrungen hat man es mit durchschnittlich 22 über 11 Möglichkeiten zu tun, so dass ich wirklich erst mal den dümmsten/einfachsten Ansatz gewählt habe, indem ich mir alle möglichen Mannschaften mit itertools.combinations generieren lasse und jede Möglichkeit auf die Regeln überprüfe. Hält sie den Regeln stand, werden die Punkte berechnet und mit der bisher besten Punktzahl verglichen.

Hier der Auszug:

Code: Alles auswählen

def besteMannschaft_bruteforce(sptag,mannschaft,mitspieler):
    besetzung_min = {'Torwart':1,'Abwehr':3,'Mittelfeld':3,'Sturm':2}
    positionen = {'Torwart':0,'Abwehr':0,'Mittelfeld':0,'Sturm':0}
    besteElf = []
    punkte = -10000
    # generiert ein liste mit allen Spielern, die gespielt haben:
    eingesetzteSpieler=[]
    for spieler in mannschaft:
        spieler = alleSpieler[spielerConvert[spieler[0]]]
        if sptag in spieler.bewertungen:
            eingesetzteSpieler.append((spieler.name,
                                       spieler.position,
                                       spieler.spieltagPunkte[sptag],
                                       spieler.verein))
    # wenn eine Mannschaft nicht die erforderliche Mindestbesetzung hat, wird sie mit Dummy aufgefüllt
    positionen_start = {'Torwart':0,'Abwehr':0,'Mittelfeld':0,'Sturm':0}
    for spieler in eingesetzteSpieler:
        positionen_start[spieler[1]] += 1
    for position in positionen_start:
            while positionen_start[position] < besetzung_min[position]:
                eingesetzteSpieler.append(('Dummy',position,-25,'Dummy'))
                positionen_start[position]+=1
    for elf in itertools.combinations(eingesetzteSpieler,11):
        if mannschaft_ok(elf):
            summe = sum(spieler[2] for spieler in elf)
            if summe > punkte:
                besteElf = elf
                punkte = summe

    .... [Ausgabe der Mannschaft auf der Konsole]

def mannschaft_ok(mannschaft):
    besetzung_min = {'Torwart':1,'Abwehr':3,'Mittelfeld':3,'Sturm':2}
    besetzung_max = {'Torwart':1,'Abwehr':5,'Mittelfeld':5,'Sturm':3}
    vereine = {}
    positionen = {'Torwart':0,'Abwehr':0,'Mittelfeld':0,'Sturm':0}
    # zähle positionen und vereine
    for name, position, punkte, verein in mannschaft:
        if verein in vereine:
            vereine[verein] += 1
        else:
            vereine[verein] = 1
        positionen[position] += 1
    # checke Positionen
    for position in positionen:
        anzahl_plaetze = range(besetzung_min[position],besetzung_max[position]+1)
        if positionen[position] not in anzahl_plaetze:
            return False
    # checke Vereinanzahl 
    for anzahl_verein in vereine.values():
        if anzahl_verein > 3:
            return False
    # Mannschaft ok
    return True

Es wäre jetzt evtl. zu überlegen, wie man das optimieren könnte. Da wären eure Vorschläge mit einem Baum besser, dass ich beim Befüllen des Baumes überprüfe, ob die Mannschaft durch Hinzufügen eines Spielers überhaupt noch zulässig ist. Für mein spezielles Problem reicht mir die Geschwindigkeit aus, allerdings will ich eigentlich auch noch eine Elf des Tages generieren, also aus allen Mannschaften, die gespielt haben die beste Elf. Das wären dann im Maximal-Fall 252 (18 Mannschaften * 14 (11+3) Spieler) über 11 Möglichkeiten (5225395795223303700) und minimal 198 über 11 (346204947854027808).

Mal gucken, ob ich das hinkriege...

Edit: Hab gerade mal abeschätzt, wenn er 100000 Mannschaften pro Sekunde testen kann, benötigt reines BruteForce wohl ca. 1,6 Mio. Jahre Rechenzeit.