Erkennen von Erhaltung, Verlust oder Gewinn in einem Handwerk mit Gegenständen und Rezepten

Question

Angenommen, wir entwerfen ein Spiel wie minecraft wo wir viele Artikel haben $ i_1, i_2, ..., i_n \ in i $ < / span> und ein paar rezepte $ r_1, r_2, ..., r_m \ in r $ . Rezepte sind Funktionen $ R: (i \ times \ mathbb {n}) ^ n \ rightarrow i \ times \ mathbb {n} $ , das sind sie einige Elemente mit nicht negativen Ganzzahlen gewichten und eine ganzzahlige Menge eines anderen Elements erzeugen.

Beispielsweise ist das Rezept für Kuchen in minecraft :

3 Milch + 3 Weizen + 2 Zucker + 1 Ei $ \ Rightarrow $ 1 Kuchen

... und das Rezept für Fackeln ist:

1 stick + 1 coal $ \ Rightarrow $ 4 Fackeln

Einige Rezepte könnten sogar reversibel sein, zum Beispiel: 9 Diamanten $ \ lefTrightarrow $ 1 Diamantblock

Wenn es eine Kombination von Rezepten gibt, können wir wiederholt anwenden, um mehr von den von uns angefangeneten Artikel zu erhalten, mit dem das Spiel schlecht ausbalanciert ist und dies von den Spielern ausgenutzt werden kann. Es ist wünschenswerter, dass wir das Spiel mit Rezepten entwerfen, die Gegenstände sparen oder möglicherweise einige Gegenstände verlieren (thermodynamische Entropie in der realen Welt - Sie können den Toast nicht leicht zu verbrennen).

Gibt es einen effizienten Algorithmus, der entscheiden kann, ob ein Satz von Rezepten wird:

.
• sparen Gegenstände?
• Artikel zu Ineffizienz verlieren?
• Artikel gewinnen?

Gibt es einen effizienten Algorithmus, der die problematischen Rezepte finden kann, wenn ein Spiel eingesetzt wird?

Meine ersten Gedanken sind, dass es hier eine Graphstruktur / maximales Fließproblem gibt, aber es ist sehr komplex, und dass es einem Rucksackproblem ähnelt. Oder vielleicht könnte es als ein Sat-Problem formuliert werden - dies ist, was ich in Betracht ziehe, um es im Moment zu codieren, aber etwas effizienter existieren könnte.

Wir könnten Rezepte in einer Matrix $ \ mathbf {r} ^ {m \ magen n} $ Spalteneinträge sind negativ, wenn ein Element von einem Rezept verbraucht wird, positiv, wenn es vom Rezept hergestellt wird, und null, wenn es ungenutzt ist. Ähnlich wie eine bekannte Matrixmethode zur Diagrammzykluserkennung können wir $ \ Mathbf {R} $ auf etwas hohe Leistung erheben und Summen jeder Zeile erhalten, um zu sehen, ob der Artikel angezeigt wird Summen gehen weiter, bleiben ausgewogen oder negativ. Ich bin jedoch nicht sicher, dass das immer funktioniert.

Jede Diskussion, Code oder empfohlene Lesen ist sehr geschätzt.

Answer 1

Dies sollte mit linearer Programmierung lösbar sein.

Hintergrund und Setup

Lassen Sie den Zustandsvektor ein Vektor der Anzahl der Anzahl jedes von Ihnen gewünschten Artikels sein. Wenn die möglichen Gegenstände Milch, Weizen, Zucker, Ei, Kuchen, Diamanten sind, dann die Regel

3 Milch + 3 Weizen + 2 Zucker + 1 Ei $ \ Rightarrow $ 1 Kuchen

wirkt sich auf den Zustandsvektor durch Hinzufügen von $ (- 3, -3, -2, -1,1,0) $ darauf. Lassen Sie also $ A_I $ den Änderungsvektor für den $ i $ th hero.

Artikel gewinnen

Ich behaupte, dass es einen Weg gibt, um Gegenstände ohne gebundene IFF zu erlangen, gibt es eine realisierbare Lösung für das lineare Programm

$$ A_1 x_1 + \ dots + a_n x_n \ ge (0,0, \ Punkte, 0), x_1 \ ge 0, \ dots, x_n \ ge 0 $$

so, dass $ A_1 x_1 + \ dots + a_n x_n> (0,0, \ Punkte, 0) $ . Hier ist $ \ ge $ auf vektoren positionszweig (dh $ u \ ge v $ iff $ u_i \ ge v_i $ Hält für alle $ i $ ) und ähnlich für $> $ . Dies kann als lineares Programm ausgedrückt werden: Sie maximieren die Summe der Koordinaten von $ A_1 x_1 + \ dots + a_n x_n $ , unterliegen den obigen Ungleichungen. Daher können Sie es in der Polynomzeit mit einem linearen Programmierlöser lösen. Dies sagt Ihnen, ob es einen Weg gibt, um einen Artikel ohne Grenzen zu erhalten.

Warum ist der Anspruch wahr? Wenn es eine realisierbare Lösung für das lineare Programm gibt, gibt es einen Weg, um die Anzahl einiger Artikel ohne gebunden zu wachsen. Wenn Sie insbesondere mit einer sehr großen Anzahl von jedem Element beginnen, wenden Sie die Regel 1 $ X_1 $ mal, Regel 2 $ x_2 $ Times usw. Sie landen mit einem neuen Zustandsvektor, der sich von dort unterscheidet, wo Sie mit $ A_1 X_1 + \ DOTS + A_N X_N $ << / span>, das mindestens in jeder Komponente mindestens so groß ist und in mindestens einer Komponente streng größer ist. Wenn Sie außerdem mit einer ausreichend großen Anzahl von Elementen beginnen, werden Sie niemals in einem intermediären Anwendungsschritt der Regeln "negativ" negativen ". Beachten Sie, dass, wenn es eine Lösung für dieses lineare Programm gibt, eine Lösung in den Rationalen gibt, die eine Lösung in den Ganzzahlen ergibt (multiplizieren Sie mit der entsprechenden Konstante zu klaren Nennern).

Umgekehrt, wenn es eine Methode gibt, um die Anzahl einiger Artikel ohne gebunden zu wachsen, gibt es eine Lösung für das lineare Programm: Lassen Sie einfach $ x_i $ count Die Anzahl der Male-Regel $ I $ wird in dieser Methode angewendet, und Sie werden sehen, dass dies eine gültige Lösung für das lineare Programm ergibt.

Verlust von Elementen

Ich glaube, dass es eine ähnliche Äquivalenz gibt: Es gibt einen Weg, um Gegenstände ohne gebundene IFF zu verlieren, es gibt eine realisierbare Lösung für das lineare Programm

$$ A_1 x_1 + \ dots + a_n x_n \ le (0,0, \ Dots, 0), x_1 \ ge 0, \ dots, x_n \ ge 0 $$

so, dass $ A_1 x_1 + \ dots + a_n x_n <(0,0, \ dots, 0) $ . Sie sollten meine Argumentation überprüfen, da ich dies nicht sorgfältig überprüft habe.

Erhaltung

Endlich, wenn es keine Möglichkeit gibt, Gegenstände ohne gebundene oder verlorene Gegenstände zu erlangen, dann denke ich, dass es folgt, dass der Wert konserviert ist.

Answer 2

Ihr Problem ist gleichwertig zu fragen, ob es eine lineare Kombination von Zeilenvektoren von Ihrem $ \ Mathbb R ^ {m \ times n} $ Matrix gibt, die alle hat Koeffizienten positiv und Summen an einen Vektor, in dem (a) jedes Element $ \ ge 0 $ und (b) mindestens ein Element ist, ist $> 0 $ .

(Beachten Sie, dass die bestellung der Operationen spielt keine Rolle: Wenn Sie sie in einiger Reihenfolge leiten, können dazu führen, dass die Menge einiger Artikel unter Null eintauchen kann, aber wir können nur nach dem niedrigen Wasser suchen -Marke und vermuten, dass wir zumindest so haben, dass viele von jedem einzelnen Artikel beginnen.)

Ich denke, dies kann durch lineare Programmierung gelöst werden: Machen Sie eine Variable für jeden Koeffizienten, fügen Sie $ \ ge 0 $ Einschränkungen für jedes Element in dem Ausgabevektor hinzu (jeweils Das Element ist ein Punktprodukt von Koeffizientenvariablen und konstanten Koeffizienten von Rezepten), mehr $ \ ge 0 $ Einschränkungen für jede Koeffizientenvariable, und legen Sie die Funktion ein, um das Gerät zu maximieren Summe aller Elemente. Um es gebunden zu machen, setzen Sie die Summe der Koeffizientenvariablen auf einige konstante, z. 1. IFF Der Lösungswert ist $> 0 $ , Sie haben keine Konservierung!

Beachten Sie, dass Fractions-Werte kein Thema sind: Sie müssen rational sein, sodass Sie sich immer von allen Nennern multiplizieren können, um eine reine ganzzahlige Lösung zu erhalten.