Detección de la conservación, la pérdida o la ganancia en un juego de elaboración con artículos y recetas.

Question

Supongamos que estamos diseñando un juego como Minecraft donde tenemos muchos artículos $ i_1, i_2, ..., i_n \ in i $ < / span> y un montón de recetas $ r_1, r_2, ..., r_m \ en r $ . Las recetas son funciones $ r: (I \ Times \ MathBB {n}) ^ n \ RightArow I \ Times \ MathBB {n} $ , que son algunos artículos con pesos enteros no negativos y producir una cantidad entera de otro elemento.

Por ejemplo, la receta para pastel en Minecraft es:

3 Leche + 3 trigo + 2 azúcar + 1 huevo $ \ judowarrow $ 1 pastel

... y la receta para las antorchas es:

1 Stick + 1 carbón $ \ rudowarrow $ 4 antorchas

Algunas recetas podrían incluso ser reversibles, por ejemplo: 9 diamantes $ \ leftrightarrow $ 1 bloque de diamantes

Si hay alguna combinación de recetas, podemos aplicar repetidamente para obtener más de los elementos con los que comenzamos, entonces el juego está mal equilibrado y esto puede ser explotado por jugadores. Es más deseable que diseñemos el juego con recetas que conservemos artículos o posiblemente pierdan algunos artículos (entropía termodinámica en el mundo real: no puede generar fácilmente la brindis).

¿Hay un algoritmo eficiente que pueda decidir si un conjunto de recetas,

• Conservar artículos?
• perder artículos a la ineficiencia?
• obtener artículos?

¿Hay un algoritmo eficiente que pueda encontrar las recetas problemáticas si un juego está desequilibrado?

Mis primeros pensamientos son que hay una estructura de gráficos / un problema de flujo máximo aquí, pero es muy complejo, y que se parece a un problema de mochila. O tal vez podría formularse como un problema de SAT, esto es lo que estoy considerando codificarlo en este momento, pero podría existir algo más eficiente.

Podríamos codificar recetas en una matriz $ \ mathbf {r} ^ {m \ veces n} $ donde las filas corresponden a recetas y columnas corresponden a elementos. Las entradas de columna son negativas si un artículo es consumido por una receta, positiva si está producida por la receta, y cero si no se usa. Similar a un método de matriz bien conocido para la detección del ciclo de gráfico, podríamos recaudar $ \ mathbf {r} $ a un poco de alta potencia y obtener sumas de cada fila para ver si el artículo Los totales siguen subiendo, permanecen equilibrados o van negativos. Sin embargo, no estoy seguro de que esto siempre funciona.

Cualquier discusión, código o lectura recomendada es muy apreciada.

Answer 1

Esto debería ser solucible con la programación lineal.

Fondo y configuración

Deje que el vector estatal sea un vector del número de número de cada artículo que tiene. Si los artículos posibles son la leche, el trigo, el azúcar, el huevo, el pastel, los diamantes, luego la regla

3 Leche + 3 trigo + 2 azúcar + 1 huevo $ \ judowarrow $ 1 pastel

Afecta el vector del estado agregando $ (- 3, -3, -2, -1,1,0) $ a ella. Entonces, permita que $ A_I $ denote el vector de cambio para el $ i $ th regla.

ganando artículos

Afirmo que existe una forma de obtener artículos sin límite IFF existe una solución factible al programa lineal

$$ A_1 X_1 + \ DOTS + A_N X_N \ GE (0,0, \ puntos, 0), X_1 \ GE 0, \ Dots, X_N \ GE 0 $$

de tal manera que $ A_1 x_1 + \ DOTS + A_N X_N> (0,0, \ puntos, 0) $ . Aquí $ \ ge $ se define en los vectores puntualmente (es decir, $ u \ ge v $ iff $ u_i \ ge v_i $ tiene para todos $ i $ ) y de manera similar para $> $ . Esto se puede expresar como un programa lineal: maximiza la suma de las coordenadas de $ a_1 x_1 + \ dots + a_n x_n $ , sujeto a las desigualdades anteriores. Por lo tanto, puede resolverlo en tiempo polinomial utilizando un solucionador de programación lineal. Esto le dice si hay una manera de obtener algún artículo sin límite.

¿Por qué es verdad la reclamación? Bueno, si hay una solución factible para el programa lineal, entonces proporciona una forma de crecer el número de algún artículo sin límite. En particular, si comienza con un número muy grande de cada artículo, luego aplique la regla 1 $ x_1 $ veces, regla 2 $ x_2 $ veces, etc., terminará con un nuevo vector de estado que difiere de donde inició $ a_1 x_1 + \ dots + a_n x_n $ < / SPAN>, que es al menos tan grande en cada componente y es estrictamente mayor en al menos un componente. Además, si comienza con un número suficientemente grande de elementos, nunca "volverá negativo" en ningún paso intermedio de la aplicación de las reglas. Tenga en cuenta que si hay una solución a este programa lineal, existe una solución en las racionales, lo que produce una solución en los enteros (multiplicar por los denominadores constantes adecuados para borrar).

Por el contrario, si hay un método para aumentar el número de algún elemento sin límite, entonces hay una solución al programa lineal: solo deje que $ x_i $ cuenta El número de veces que la regla $ i $ se aplica en ese método, y verá que esto produce una solución válida al programa lineal.

Perdidos Perdidos

Creo que hay una equivalencia similar: existe una forma de perder artículos sin límite IFF existe una solución factible al programa lineal

$$ A_1 X_1 + \ DOTS + A_N X_N \ LE (0,0, \ puntos, 0), X_1 \ GE 0, \ Dots, X_N \ GE 0 $$

tal que $ A_1 x_1 + \ DOTS + A_N X_N <(0,0, \ PUNTS, 0) $ . Debe revisar mi razonamiento, ya que no he comprobado esto con cuidado.

Conservación

Finalmente, si no hay forma de ganar artículos sin límite o perder elementos sin límite, entonces creo que sigue que se conserva ese valor.

Answer 2

Su problema es equivalente a preguntar si hay alguna combinación lineal de vectores de fila de su $ \ mathbb r ^ {m \ veces n} $ matrix que tiene todo coeficientes positivos y sumas a un vector en el que (a) cada elemento es $ \ ge 0 $ y (b) al menos un elemento es $> 0 $ .

(Observe que la orden de las operaciones no importa: Ejecutarlos en algún orden puede causar que la cantidad de algún artículo se sumerja por debajo de cero, pero podemos buscar el agua baja -Mardecer y supongamos que tenemos al menos muchos de cada artículo para comenzar.)

Creo que esto puede resolverse por programación lineal: hacer una variable para cada coeficiente, agregue $ \ ge 0 $ restricciones para cada elemento en el vector de salida (cada uno El elemento es un producto de puntos de las variables de coeficiente y los coeficientes constantes de las recetas), más $ \ ge 0 $ restricciones para cada variable de coeficiente, y configure la función para maximizar para ser el Suma de todos los elementos. Para que se limite, establezca la suma de las variables de coeficiente a algunas constantes, por ejemplo. 1. IFF El valor de la solución es $> 0 $ , ¡no tiene conservación!

Tenga en cuenta que los valores fraccionarios no son un problema: deben ser racionales, por lo que siempre puede multiplicarse por todos los denominadores para obtener una solución de enteros puros.