Detectando conservação, perda ou ganho em um jogo de artesanato com itens e receitas

Question

Suponha que estejamos projetando um jogo como Minecraft onde temos muitos itens $i_1,i_2,...,i_n\em I$ e um monte de receitas $r_1,r_2,...,r_m\em R$.Receitas são funções $r:(I imes\mathbb{N})^n ightarrow I imes\mathbb{N}$, ou seja, eles pegam alguns itens com pesos inteiros não negativos e produzem uma quantidade inteira de outro item.

Por exemplo, a receita de bolo em Minecraft é:

3 leites + 3 trigos + 2 açúcares + 1 ovo $ ightarrow$ 1 bolo

...e a receita das tochas é:

1 pau + 1 carvão $ ightarrow$ 4 tochas

Algumas receitas podem até ser reversíveis, por exemplo:9 diamantes $\esquerdadireita$ 1 bloco de diamante

Se houver alguma combinação de receitas que possamos aplicar repetidamente para obter mais itens com os quais começamos, o jogo ficará mal equilibrado e isso poderá ser explorado pelos jogadores.É mais desejável que projetemos o jogo com receitas que conservem itens ou possivelmente percam alguns itens (entropia termodinâmica no mundo real - você não pode queimar a torrada facilmente).

Existe um algoritmo eficiente que pode decidir se um conjunto de receitas irá:

• conservar itens?
• perder itens por ineficiência?
• ganhar itens?

Existe um algoritmo eficiente que possa encontrar as receitas problemáticas se um jogo estiver desequilibrado?

Meu primeiro pensamento é que há um problema de estrutura gráfica/fluxo máximo aqui, mas é muito complexo e se assemelha a um problema de mochila.Ou talvez pudesse ser formulado como um problema SAT - é isso que estou pensando em codificá-lo no momento, mas pode existir algo mais eficiente.

Poderíamos codificar receitas em uma matriz $\mathbf{R}^{m \vezes n}$ onde as linhas correspondem às receitas e as colunas correspondem aos itens.As entradas da coluna são negativas se um item for consumido por uma receita, positivas se for produzido pela receita e zero se não for utilizado.Semelhante a um método matricial bem conhecido para detecção de ciclo gráfico, poderíamos levantar $\mathbf{R}$ para uma potência alta e obtenha as somas de cada linha para ver se os totais dos itens continuam aumentando, permanecem equilibrados ou ficam negativos.No entanto, não estou confiante de que isso sempre funcione.

Qualquer discussão, código ou leitura recomendada é muito apreciada.

Answer 1

Isso deve ser solucionável com programação linear.

fundo e configuração

Deixe o Vector do estado ser um vetor da contagem de número de cada item que você tem. Se os possíveis itens forem leite, trigo, açúcar, ovo, bolo, diamantes, então a regra

3 leite + 3 trigo + 2 açúcar + 1 ovo $ \ rightarrow $ 1 bolo

Afeta o vetor do estado adicionando $ (- 3, -3, -2, -1,1,0) $ para ele. Então, deixe $ a_i $ denotar o vetor de alteração para a $ i $ th regra.

ganhando itens

Eu afirmo que existe uma maneira de ganhar itens sem limite IFF Existe uma solução viável para o programa linear

$$ a_1 x_1 + \ Dots + a_n x_n \ ge (0,0, \ pontos, 0), x_1 \ ge 0, \ pontos, x_n \ ge 0 $$

Tal que $ a_1 x_1 + \ dots + a_n x_n> (0,0, \ pontos, 0) $ . Aqui $ \ GE $ é definido nos vetores pontual (ou seja, $ u \ ge v $ IFF $ u_i \ ge v_i $ mantém para todos $ i $ ) e similarmente para o recipiente de matemática $> $ . Isso pode ser expresso como um programa linear: você maximiza a soma das coordenadas de $ a_1 x_1 + \ pontos + a_n x_n $ , sujeito às desigualdades acima. Portanto, você pode resolvê-lo no tempo polinomial usando um solucionador de programação linear. Isso informa se há uma maneira de obter algum item sem limite.

Por que a reivindicação é verdadeira? Bem, se houver uma solução viável para o programa linear, ele fornece uma maneira de aumentar o número de algum item sem limite. Em particular, se você começar com um número muito grande de cada item, aplicar a regra 1 $ x_1 $ vezes, regra 2 $ x_2 $ vezes, etc., você vai acabar com um novo vetor de estado que difere de onde você iniciou por $ a_1 x_1 + \ pontos + a_n x_n $ < / span>, que é pelo menos tão grande em cada componente e é estritamente maior em pelo menos um componente. Além disso, se você começar com um número suficientemente grande de itens, nunca "irá negativo" em qualquer etapa intermediária de aplicação das regras. Note que se houver uma solução para este programa linear, há uma solução nos racionais, que produz uma solução nos inteiros (multiplicação pela constante apropriada para denominadores claros).

Por outro lado, se houver um método para aumentar o número de algum item sem limite, então há uma solução para o programa linear: basta deixar $ x_i $ contar O número de vezes a regra $ i $ é aplicado nesse método, e você verá que isso produz uma solução válida para o programa linear.

Perdendo itens

Eu acredito que há uma equivalência semelhante: existe uma maneira de perder itens sem vincular se existe uma solução viável para o programa linear

$$ a_1 x_1 + \ pontos + a_n x_n \ le (0,0, \ pontos, 0), x_1 \ ge 0, \ pontos, x_n \ ge 0 $$

De modo que $ a_1 x_1 + \ dots + a_n x_n <(0,0, \ pontos, 0) $ . Você deve verificar meu raciocínio, pois não verifiquei isso com cuidado.

Conservation

Finalmente, se não houver maneira de ganhar itens sem vincular ou perder itens sem limite, então acho que segue esse valor é conservado.

Answer 2

Seu problema equivale a perguntar se existe alguma combinação linear de vetores linha de seu $\mathbb R^{m\vezes n}$ matriz que tem todos os coeficientes positivos e soma um vetor no qual (a) cada elemento é $\ge 0$ e (b) pelo menos um elemento é $> 0$.

(Observe que o ordem das operações não importa:Executá-los em alguma ordem pode fazer com que a quantidade de algum item caia abaixo de zero, mas podemos apenas procurar o limite mínimo e supor que temos pelo menos essa quantidade de cada item para começar.)

Acho que isso pode ser resolvido por programação linear:Faça uma variável para cada coeficiente, adicione $\ge 0$ restrições para cada elemento no vetor de saída (cada elemento é um produto escalar de variáveis ​​de coeficiente e coeficientes constantes de receitas), mais $\ge 0$ restrições para cada variável de coeficiente e defina a função para maximizar como a soma de todos os elementos.Para torná-lo limitado, defina a soma das variáveis ​​dos coeficientes como alguma constante, por ex.1.Se o valor da solução for $> 0$, você tem não conservação!

Observe que os valores fracionários não são um problema:Eles devem ser racionais, então você sempre pode multiplicar por todos os denominadores para obter uma solução inteira pura.