Hallo zusammen,

ich bräuchte mal einen Rat, wie ich folgendes Problem am besten angehe. Ich habe vor einigen Jahren mal eine Flash Anwendung geschrieben (nein keine sorge ich verschone euch mit dem Code), welches einen OreCalculator darstellen sollte.

Es gibt 8 Rohmaterialen, welche man eintragen kann. Ziel des Programm soll es sein, die "bestmögliche" Lösung zu liefern.

Hier einen Link zur swf (www.andrus-brothers.de/Orecalc.swf). Dies soll nur zur veranschaulichung dienen (es ist teilfunktional).

Es geht darum, das verschiedene erze, eine definierte Anzahl an Rohmaterialen enthält (in diesem fall mineralien).

Aufgabe des Orecalculators soll es sein, je nach auswahl der "erze" - die geringstmögliche Anzahl aus Kombinationsmöglichkeiten aus den selektierten Erzen zu generieren.

Da dies ein P=NP Problem ist, kann man hier nur bruteforcen.

Im Moment versuche ich mir ein Konzept zu erarbeiten, wie ich das Problem am besten angehe.

Ich hatte anfangs gedacht, das ich erstmal hundert möglichkeiten durchspiele, diese bewerte - und dann die lösung wähle, die am wenigsten "material" benötigt.

Leider habe ich moment noch überhaupt keinen Ansatz dafür, wie ich das programmatisch lösen könnte.

Erst hatte ich die Überlegung, je nach mineralienart, einen fiktiven Wert einzusetzen (Bewertung) und anhand dieser Bewertung, eine Entscheidung zu treffen.

Ich bin mir sicher, das es einen Begriff für dieses Problem gibt.

Habt ihr eine Ahnung wie man sowas nennt ?


Moderiert von Th69: Topic aus C# - Die Sprache verschoben am Di 26.02.2019 um 08:44

Hallo,

stellst Du Dir einen wikipedia: Evolutionärer_Algorithmus vor?

Gruß Horst

Ich bin mir nicht ganz sicher, ob ich das Problem richtig verstanden habe.

Du hast also 8 Rohmaterialien. Diese sind in unterschiedlichen Mengen (Anteilen bzw. Konzentrationen) in bestimmten Erzen enthalten. Gegeben ist dann eine Liste von diesen Rohmaterialien mit Mengenangaben, und gesucht ist die minimale Anzahl/Menge von den verschiedenen Erzen, die man abbauen muss, um diese Material-Anforderung zu erfüllen?

Bin jetzt auf Anhieb nicht sicher, ob das wirklich NP-Vollständig ist, aber kann sehr gut sein. Hat ja irgendwie was vom Rucksackproblem.

Muss es denn die beste Lösung sein, oder reicht auch eine gute? Müsste man mal genauer untersuchen, aber eventuell kommt man ja mit Greedy-Methoden zu einer sehr guten Lösung. D.h. man wählt schrittweise immer die Erz-Art, die einen am meisten bringt (insgesamte Anzahl an noch benötigten Material sinkt am stärksten, oder man nimmt die Erz-Art, bei der das Verhältnis der benötigten Materialien am besten passt?).

Bei einer exakten Lösung (durch Austesten aller Möglichkeiten) würde ich erstmal für jedes Erz die sinnvolle Maximalmenge bestimmen, die man benötigt, um dafür die Schleifengrenzen festzulegen (soll heißen: Mehr davon ist nicht sinnvoll, weil man damit die erforderliche Menge für alle in dem Erz vorkommenden Mineralien erfüllt) - und dann laufen lassen.

Ansonsten helfen vielleicht auch allgemeine Techniken für das Finden einer "guten" (aber nicht unbedingt optimalen) Lösung solch schwerer Probleme. Ein Beispiel ist Simulated_Annealing. Bezogen auf das Problem hier könnte man mit einer Lösung starten, und bei der Modifikation ein Erz reduzieren, und dafür andere erhöhen, bis es wieder passt ... ist alles etas unausgegoren, aber vielleicht gibt das ja einen Stups in die richtige Richtung.

Nun, hier mal ne bessere Erklärung (hoffe ich).

Du hast ja unterschiedliche Materialien. Z.bsp. Veldspar. Veldspar enthält nur Tritanium. Dann gibts andere Materialien, die andere Mineralien enthalten können. Z.bsp. Spodumain, das enthält, nur tritanium pyerite und mexallon.

Habe hier mit einer Bit-Codierung gearbeitet, sozusagen als Wiederspiegelung der Verteilung. also 1000000 enthält z.bsp. nur Tritanium. 10100100 wäre z.bsp. das beispiel für das tritanium, pyerite und mexallon problem.

Und da man hier ja selektieren kann, welche Erze man möchte, gibt es hier immer eine unterschiedliche Konfiguration.

Hier müßte man eine optimale Lösung finden.

Rucksackproblem, ja, das kommt gut hin.

Ich setzte mich mal die Tage ran, und entwerfe ein Konzept zur umsetzung. Würde mich über Tipps freuen!

Grüße