Обнаружение сохранения, потери или выгоды в крафтинговой игре с предметами и рецептами

Question

Предположим, мы проектируем игру, как Minecraft , где у нас есть много предметов $ i_1, i_2, ..., i_n \ in i $ < / span> и куча рецептов $ r_1, r_2, ..., r_m \ in r $ . Рецепты являются функциями $ r: (i \ turs \ mathbb {n}) ^ n \ prightarrow i \ turs \ mathbb {n} $ , то есть они берут некоторые предметы с неотрицательными целочисленными весами и создавать целое число другого предмета.

Например, рецепт для торта в Minecraft :

3 молоко + 3 пшеницы + 2 сахара + 1 яйцо $ \ pruralarrow $ 1 торт

... и рецепт факелов:

1 палка + 1 уголь $ \ pruralarrow $ 4 горелки

Некоторые рецепты могут даже обратимы, например: 9 Diamonds $ \ leftrightarrow $ 1 алмазный блок

Если есть некоторая комбинация рецептов, мы можем неоднократно применять, чтобы получить больше элементов, которые мы начали с того, что игра плохо сбалансирована, и это может быть использовано игроками. Более желательно, чтобы мы разработали игру с рецептами, которые сохраняют предметы или, возможно, теряют некоторые предметы (термодинамическая энтропия в реальном мире - вы не можете легко сжигать тосты).

Есть эффективный алгоритм, который может решить, будет ли набор рецептов:

.
• Сохранить предметы?
• потерять предметы неэффективности?
• усиление предметов?

Есть эффективный алгоритм, который может найти проблемных рецептов, если игра несбалансирована?

Мои первые мысли - это то, что есть структура графа / максимальная проблема расхода здесь, но она очень сложная, и что это напоминает проблему рюкзака. Или, может быть, это может быть сформулировано как проблема SAT - это то, что я рассматриваю, чтобы кодировать его в данный момент, но может существовать что-то более эффективное.

Мы могли бы кодировать рецепты в матрице $ \ mathbf {r} ^ {m \ mans n} $ где строки соответствуют рецептам и столбцам соответствуют элементам. Записи столбцов отрицательны, если элемент потребляется рецептом, положительным, если он производится рецептом и ноль, если он не используется. Подобно хорошо известному методу матрицы для обнаружения цикла графиков, мы могли бы поднять $ \ mathbf {R} $ на некоторую высокую мощность и получить суммы каждой строки, чтобы увидеть, если элемент Итоги продолжаются вверх, оставаться сбалансированным или идти отрицательным. Однако я не уверен, что это всегда работает.

Любое обсуждение, код или рекомендуемое чтение очень ценится.

Answer 1

Это должно быть разрешимо с линейным программированием.

Фон и настройка

Пусть вектор состояния будет вектор подсчета количества каждого элемента, который у вас есть. Если возможные предметы молоко, пшеница, сахар, яйцо, торт, бриллианты, затем правило

3 молоко + 3 пшеницы + 2 сахара + 1 яйцо $ \ pruralarrow $ 1 торт

влияет на вектор состояния, добавив $ (- 3, -3, -2, -1,1,0) $ . Итак, пусть $ a_i $ обозначает вектор изменения для $ i $ th.

Получение предметов

Я утверждаю, что существует способ получения предметов без связи IFF существует возможное решение для линейной программы

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

такое, что $ a_1 x_1 + \ dots + a_n x_n> (0,0, \ dots, 0) $ . Здесь $ \ GE $ определяется по векторами по точке (т.е. $ u \ ge v $ iff $ u_i \ ge v_i $ Держит для всех $ I $ ) и аналогично для $> $ . Это может быть выражено в виде линейной программы: вы максимизируете сумму координат $ a_1 x_1 + \ dots + a_n x_n $ , при условии неравенства выше. Следовательно, вы можете решить его в многочленом времени с использованием решателя линейного программирования. Это говорит вам, есть ли способ получить какой-то пункт без границы.

Почему претензия правда? Ну, если есть возможное решение для линейной программы, то она обеспечивает способ выращивать количество какого-либо пункта без границ. В частности, если вы начинаете с очень большого количества каждого элемента, примените правило 1 $ x_1 $ times, правило 2 $ x_2 $ Times и т. Д., Вы в конечном итоге с новым вектором состояния, который отличается от того, где вы начали с $ a_1 x_1 + \ dots + a_n x_n $ < / span>, который, по меньшей мере, настолько больший в каждом компонент и строго больше, чем хотя бы на один компонент. Более того, если вы начнете с достаточно большого количества предметов, вы никогда не будете «негативно» на любом промежуточном этапе применения правил. Обратите внимание, что если для этой линейной программы есть решение, существует решение в рационализации, что дает раствор в целых числах (умножения на соответствующую константу к четкому знаменателю).

И наоборот, если есть способ выращивания количества какого-либо пункта без границ, то существует решение в линейной программе: просто позвольте $ x_i $ count Количество временных правил $ i $ применяется в этом методе, и вы увидите, что это дает допустимое решение линейной программы.

Потеря предметов

Я считаю, что существует аналогичная эквивалентность: существует способ потерять предметы без связи IFF, существует возможное решение для линейной программы

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

такое, что $ a_1 x_1 + \ dots + a_n x_n <(0,0, \ dots, 0) $ . Вы должны проверить мои рассуждения, так как я не проверял это тщательно.

Сохранение

Наконец, если нет способа получить элементы без связанных или потерять предметы без границ, то я думаю, что следует, что значение сохраняется.

Answer 2

Ваша проблема эквивалентна спрашивать, есть ли линейную комбинацию векторов строк от вашего $ \ mathbb r ^ {m \ times n} $ matrix, которая имеет все Коэффициенты положительные и суммы к вектору, в котором (а) каждый элемент представляет собой $ \ ge 0 $ и (b), по меньшей мере, один элемент - $> 0 $ .

(обратите внимание, что порядок операций не имеет значения: запуск их в некоторых заказах может привести к тому, что количество какого-либо пункта погружается ниже нуля, но мы можем просто искать низкую воду - Предполагается, что у нас есть как минимум, многие из каждого элемента для начала.)

Я думаю, что это можно решить с помощью линейного программирования: сделайте переменную для каждого коэффициента, добавить $ \ GE 0 $ Ограничения для каждого элемента в векторном выходе (каждый Элемент - это точечный продукт переменных коэффициентов и постоянных коэффициентов из рецептов), более $ \ ge 0 $ ограничения для каждой переменной коэффициента и установка функции для максимизации Сумма всех элементов. Чтобы сделать его ограниченным, установите сумму коэффициентов переменных в некоторую константу, например, 1. IFF Значение решения составляет $> 0 $ , у вас нет сохранения!

Обратите внимание, что дробные значения не являются проблемой: они должны быть рациональными, поэтому вы всегда можете размножаться всеми знаменателями, чтобы получить чистое решение.