Algorithmus für konkretes Problem gesucht

[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.