Существует ли установленный алгоритм для достижения цели путем последовательного применения известных причинно-следственных кортежей?

Question

Допустим, я хочу создать вымышленный продукт под названием g.

Я знаю, что:

a+b=c
x+y=z
and finally that
c+z=g

Так ясно, если я начну с продуктов

a,b,x,y

Я могу создать g в три этапа:

a+b=c
x+y=z
c+z=g

Таким образом, наивный алгоритм для достижения цели может быть:

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

Но с этим алгоритмом есть недостатки.

Например, допустим, что моя причина и кортежи эффектов:

a+b=c
x+y+c=z (NOTE THE EXTRA 'c' REQUIRED!!)
c+z=g

Теперь, когда я запускаю свой наивный алгоритм, я сделаю

a+b=c
x+y+c=z (Using up the 'c' I created in the previous step)
c+z=g (Uh oh! I can't do this because I don't have the 'c' any more)

Кажется, что это довольно базовая c область исследований - как мы можем объединить Известные причины и следствия для достижения цели - так что я подозреваю, что работа над ней уже проделана, но я осмотрелся и ничего не смог найти, и я не знаю, где искать сейчас.

Большое спасибо за любую помощь!

Answer 1

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

a = min (b + c, d + e, f + g)

, где a - это стоимость продукта, который может быть произведен в альтернативные способы, один способ потребления единиц со стоимостью b и c, другой способ потребления единиц со стоимостью d и e, другой способ потребления единиц со стоимостью f и g и так далее. В связанном графике могут быть циклы.

Один из способов решения такой проблемы состоит в том, чтобы начать с присвоения бесконечности затрат всем продуктам, изначально не предоставленным в качестве входных данных (с затратами), а затем многократно сокращать затраты там, где уравнения показать способ расчета затрат, меньших текущих затрат, отслеживания перерасчетов, вызванных еще не учтенными ресурсами или сокращением затрат. На каждом этапе я бы рассматривал последствия наименьшего входного или пересчитанного значения, с разрывом связей по второму компоненту, который составляет налог на производство. Выходные данные, полученные в результате расчета, всегда, по крайней мере, равны любому входному значению, поэтому вновь созданные значения всегда больше, чем рассмотренное пересчитанное значение, и пересчитанное значение, рассмотренное на каждом этапе, никогда не уменьшается, что должно уменьшить повторный пересчет.

Другим способом было бы превратить это в линейную программу и запустить ее с высоко оптимизированным гарантированным полиномиальным временем (по крайней мере, на практике) для решателя линейного программирования.

a = min (b + c, d + e, f + g)

становится

a = b + c -x

a = d + ey

a = f + gz

x> = 0

y> = 0

z> = 0

минимизировать сумму (x + y + z + ....)