Kombinationen erzeugen

[Phash]

Moin,

mir ist gerade langweilig, und ich versuche mir ein wenig meine Zeit zu vertreiben.

Ich habe mir eine Aufgabe gesucht, an der ich mir allerdings gerade die Zähne ausbeisse... ich habe eine Denkblockade

Aufgabenstellung:
Ich habe eine Gruppe von Spieleinheiten, die über verschiedene Attribute verfügen.
Der Gegner hat auch eine Gruppe von Spieleinheiten.

die maximale Anzahl der Einheiten ist jeweils 100.

Die Einheiten des Gegners sind bekannt. Ich möchte nun alle meine Spieleinheiten dagegen testen. Bzw alle Kombinationen daraus.

das heisst: ich habe 50 Bogenschützen, 100 Soldaten, 50 Reiter und 20 Katapulte (Nur um einen Einblick zu erhalten)

Welche Kombination ist nun die beste gegen den Gegner?


Meine Idee wäre jetzt einfach gewesen, alle möglichen Kombinationen meiner Einheiten in 10er Schritten zu erzeugen, und die dann in einer Simulation gegen den Feind antreten zu lassen. Danach merk ich mir die Effizienz der Aufstellung.
Am Ende weiss ich, welche Aufstellungen am besten waren, und ich würde evtl die besten 3 Aufstellungen nochmal um +/-10 variieren lassen um dann zu ermitteln, wer jetzt der beste ist.


Da die Einheitenarten nicht auf 4 beschränkt sind, sondern jederzeit neue hinzu kommen könnten, fällt ein Ansatz mit verschachtelten for-Schleifen weg.


Meine Frage: wie finde ich am effizientesten alle möglichen Kombinationen, und: gibt es vielleicht eine elegantere Lösung?

 

[kaetzacoatl]

Was meinst du mit Kombinationnen?
Zeig mal den code von dem, das das
Ergebnis berechnet.

 

[Marco13]

So pauschal: Vergiss es. Wenn du von "100" redest und von "alle Kombinationen", dann wird da sicher irgendwo was mit "100!" drin vorkommen (9.33262154 × 10^157). Die einzige Möglichkeit ist, ggf. vorhandenes Wissen auszunutzen, und damit die Anzahl der Möglichkeiten zu reduzieren. Vielleicht um den Faktor 1000000000000000000000000000000000000000000000000000000000000000000, damit man nur noch 10^100 Möglichkeiten untersuchen muss :joke:

 

[Phash]

deswegen ja die Idee, in 10er Schritten zu kombinieren und nur Kombinationen die dann sinnvoll sind weiter zu untergliedern

 

[Marco13]

Wenn "10er-Schritte" nur heißt, dass man das von 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 auf 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 reduziert, bringt das nicht viel. Es gibt sicher jede Menge Einschränkungen und Zusatzinformationen, die du noch nicht genannt hast (EIN Bogenschütze gegen 100 Reiter ist sinnols, ZWEI Bogenschützen gegen 100 Reiter ist sinnlos, DREI Fledermäus.. äh... Bogeschützen gegen 100 Reiter ist sinnlos...)

Hier war auch mal ein Thread, wo jemand solche Kombinationen durchprobieren wollte, um eine Strategie (Cheat Sheet) für irgendein Online-Spiel zu erhalten, hab' ihn jetzt auf die Schnelle nicht gefunden, aber kannst ja ggf. mal suchen.

Allgemeine Utilities zu Kombinationen gibt's z.B. unter http://www.java-forum.org/codeschnipsel-u-projekte/81973-combinatorics.html#post646341 , aber wenn man nicht einen Wegweiser hat, mit dem man die Suche drastisch einschränken kann, würde ich da eher zu einer Heuristik greifen. Sowas wie Hillclimbing, irgendwas Generic Algorithm-artiges, oder Simulated Annealing ... das ist für spezielle Fälle meistens gar nicht sooo aufwändig.