Suche Idee für Algorithmus zum Finden der optimalen Verteilung

Eine Karte ist in 8*9 rechteckige Felder geteilt, auf den Feldern willkürlich verteilt befinden sich zwei verschiedene Ressourcen (X, Y) verteilt, welche zusammen insgesamt 12 Felder belegen.
Auf den noch freien Feldern kann man nun eine begrenzte Anzahl an vier unterschiedlichen Fabriken (A, B, C, D) bauen.
Die Fabriken A, B und C produzieren hierbei unterschiedliche Waren (1, 2, 3).
Fabrik D produziert nichts, sorgt aber dennoch für Vorteile, siehe weiter unten.

Die Fabriken A und B erbringen einen zusätzlichen Gewinn, wenn sie direkt neben ein Feld von Ressource X gebaut werden. Dies kann auch diagonal zu einem Feld der Ressource X sein (Dies gilt für alle Fabriken).

Die Fabrik C erbringt nur dann einen Gewinn, wenn sie an Ressource Y gebaut wird, allerdings profitiert sie auch, wenn sie Direkt neben Fabrik A steht.

Fabrik A profitiert wiederum, wenn sie noch neben Ressource D steht.
Ressource D erbringt keine Vorteile, es sei denn sie Steht neben einer oder mehreren Fabrik A, dann sorgt sie für überdeutliche Gewinne in Fabrik A.

Frage:

Wie kann man nun algorithmisch eine optimale Verteilung der Fabriken finden,
wenn die Karte und die Ressourcen vorgegeben sind und man priorisieren kann, welche Waren (1, 2, 3) besonders stark produziert werden sollen?

Welche Algorithmen eignen sich für eine solche Aufgabe?

Noch eine Ergänzung:

Wenn eine Fabrik neben mehreren Resourcenfeldern oder anderen Fabriken die ihr Vorteile verschaffen (siehe obige Regeln) steht, dann erhöht sich der Gewinn mit jedem zusätzlichen Resourcenfeld bzw. Fabrik an dem die Fabrik steht.

Noch eine kleine Anmerkung.

In der Überschrift habe ich optimale Verteilung geschrieben, das ist so nicht ganz richtig, es genügt auch, wenn die Verteilung besonders gut ist.
Wenn es also algorithmisch nicht lösbar ist, eine optimale Verteilung zu finden, dann würde mir ein Vorschlag für einen Algorithmus genügen, der eine besonders gute Verteilung bewirkt.

So wie du das Problem stellst, kann man es nicht lösen. Zum Beispiel macht es einen beachtlichen Unterschied, ob "zusätzlicher Gewinn" 1% Gewinnsteigerung bedeutet oder 100%. Und es ist auch nicht klar, was "optimal" sein soll und was "priorisieren" bedeutet (nur Typen vom Fabrik B wären optimal für Waren 2, für Waren 1 ist es wieder unklar, weil der Effekt von Fabrik D nicht definiert ist).

Deshalb kann man nur allgemein antworten.

Angenommen, die Effekte sind klar festgelegt, dann bin ich ziemlich sicher, dass es mit DP löstbar ist. Streifen der Länge 8 sind je dein State, darauf aufbauend wird gebruteforced, macht 8*4^16 operationen, was 10¹⁰ Operationen sind, also etwa 10 Sekunden. Wird aber in der Praxis weniger sein, weil einige Felder vorgegeben sind, sollte bei zufälliger Verteilung in etwa 1 Sekunde machbar sein.

Mit DP kann man eine beliebige Bewertungsfunktion nehmen.

Einfacher wäre, das Spielfeld zufällig auszufüllen und versuchen, das Ergebnis zu einem lokalen Maximum zu führen. Wenn das oft wiederholt wird, solltest du nahe am Maximum ankommen.

Gruum

Probier systematisch alle Möglichkeiten aus, bewerte sie und nehm dann die beste.

Gruum schrieb:

Probier systematisch alle Möglichkeiten aus, bewerte sie und nehm dann die beste.

Das sind 4^60 Möglichkeiten, das würde eine Milliarde mal so lange dauern, wie das Universum besteht.

Gruum

Wie kommst du auf 4^60? (das war ne rethorische Frage, ich weiss wie du darauf kommst)
Die Anzahl der Fabriken die man setzen kann ist begrenzt. Wieviele möglichkeiten es gibt hängt davon ab wieviele Fabriken man setzen darf. Ich bin jetzt ersteinmal von einer kleinen Anzahl ausgegangen.

Ich würde auch erstmal prüfen ob es nicht durchs ausprobieren zu ermitteln ist. Du musst dann aber versuchen die Möglichkeiten klein zu halten und struktuieren wann welche Information feststehen muss um damit zB den nächsten Schritt schneller zu gestalten.

Jester

Wenn man mal Alle Fabriken von Typ, sagen wir, C und D gesetzt hat, dann hängt der Gewinn für das Setzen von einer Fabrik von Typ A oder B nur noch vom jeweiligen Feld ab, sonst nichts mehr. Das kann man dann recht bequem als gewuchtetes Matching-Problem formulieren (damit keine zwei Fabriken dasselbe Feld belegen). Damit kriegt man die Anzahl der Fälle schonmal klein. Ob man noch mehr feinformuliert kriegt in das Matching bin ich mir grad unsicher (und mir fehlt die Zeit zum nachdenken).

Wenn Du es praktisch und schnell lösen willst, würde ich es als (gemischt) ganzzahliges lineares Programm formulieren. Das ist relativ einfah und Du kannst irgendeinen beliebigen Löset verwenden. Aufgrund der Ähnlichkeit zu Matching-Problemen würde ich mir eine sehr gute Performance erwarten. Empfehlenswert ist zum Beispiel gurobi, kriegt man sehr leicht als studentenversion, ist super leicht mit c++ zu benutzen und gleichzeitig sehr performant.