Задача алхимика (целочисленная оптимизация)

[mbaitoff]

У алхимика есть $N$ типов ингридиентов, каждого типа ингридиента у него $I=\{I_k, k=1..N\}$ штук. Алхимик знает несколько ($M$) рецептов $R=\{R_p, p=1..M\}$, согласно которым смесь из нескольких ингридиентов превращается в смесь других. Пусть у алхимика есть функция, которая по набору ингридиентов определяет "ценность" этого набора:$F(I)=X$. Необходимо по данному начальному набору веществ $I_0$ указать такую последовательность применения рецептов $p=\{p_1, p_2,..., p_j\}$, которая в конце максимизирует ценность полученного набора веществ.

Несколько мыслей:
1. Набор ингридиентов ($I$) - вектор длины $N$, каждый компонент которого содержит количество данного ингридиента.
2. Каждый рецепт ($R_k$) - это тоже вектор длины $N$, который описывает превращение: если элемент вектора отрицательный, то данное вещество поглощается в результате реакции, если положительное - это вещество рождается в результате реакции. Для простоты можно считать, что не существует рецептов, у которых и в поглощении, и в рождении участвует одно и то же вещество.
3. Тогда "реакция" - это просто операция сложения векторов: $I_1=I_0+R_k$.
4. Пусть функция ценности - линейная, то есть является "стоимостью" набора веществ и описывается вектором "цены" $W$ тоже длины $N$. То есть, $F=\left<I,W\right>$.
5. Тогда задача состоит в нахождении последовательности прибавления векторов из набора рецептов: $I_j = I_0 + R_p_1 + R_p_2 +...+ R_p_j$, при этом на каждом этапе сложения в векторе веществ не должно быть отрицательных элементов (реакция "в кредит" не идёт).

Как решать?

[nn910]

mbaitoff в сообщении #236423 писал(а):

Тогда "реакция" - это просто операция сложения векторов: $I_1=I_0+R_k$.
?

А кто запретил менять дозировки: $I_1=I_0+c_k R_k$ :?:

[mbaitoff]

nn910 в сообщении #236425 писал(а):

mbaitoff в сообщении #236423 писал(а):

Тогда "реакция" - это просто операция сложения векторов: $I_1=I_0+R_k$.
?

А кто запретил менять дозировки: $I_1=I_0+c_k R_k$

ой, забыл. ингридиенты дискретны. то есть, типа "перо вороны, кошачий глаз - по 1шт".

[nn910]

mbaitoff в сообщении #236427 писал(а):

ингридиенты дискретны. то есть, типа "перо вороны, кошачий глаз - по 1шт".

Задачу можно свести к задаче максимизации последнего ингредиента. Добавить "реакции реализации "каждого ингредиента, представляющего ценность, и саму ценность в качестве ингредиента.Пример с мехмата.Вначале 5 ингр.:1)водка,2)пиво,3)светлые бутылки,4)темные бутылки,5)деньги. Вводим 6)кол-во алкоголя в крови. Реакции:а)потребления(-1,-1,1,1,0,2),(-1,0,1,0,0,1), (0,-1,0,1,0,0)-тк.2без1=деньги на ветер
б)сдачи(0,0,-1,0,1,0),(0,0,0,-1,1,0)
в)закупки(1,0,0,0,-30,0),(0,1,0,0,-5,0)-всего 7 реакций
Ответ для произвольного начального расклада (a,b,c,d,e,f) считался $f+a+min(a,b)+\sigma_{35} (\dfrac{a+b+c+d+e}{35})$ где $\sigma_{35}$ -сумма "цифр" целой части числа в 35-ричной системе. Но требует корректировки в части зависимости от b, а также сбоит при раскладе (0,0,300,755,0,0)

[Xaositect]

Я практически уверен, что задача NP-трудная, ибо сильно смахивает на целочисленное линейное программирование.
ILP решается обычно перебором с отсечением, но здесь я как-то не могу сходу придумать, откуда взять оценки для отсечения.

[mbaitoff]

можно ли здесь воспользоваться каким-либо методом динамического программирования, используя то, что если состояние на каком-либо шаге $I_k$ является одним из состояний на пути к решению $I_{opt}$ из начального состояния $I_0$, то это самое $I_k$ является оптимальным решением для начального состояния $I_0 = I_0-I_k$ (или это не так?).

-- Чт авг 20, 2009 16:24:05 --

nn910 в сообщении #236467 писал(а):

Задачу можно свести к задаче максимизации последнего ингредиента.

а как это упростит задачу? судя по "сумма цифр в 35-ричной системе", дело пахнет $O(N!)$

[Xaositect]

mbaitoff в сообщении #236488 писал(а):

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

Это не так.
Пример:
$I_{0} = (10,0,0)$
$R_1 = (-1,1,0)$
$R_2 = (0,-10,1)$
$W = (2,1,1000)$
Оптимальное решение - $10R_1 + R_2$, но каждое $R_1$ уменьшает цену.

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

[nn910]

mbaitoff в сообщении #236488 писал(а):

а как это упростит задачу?

Так я вижу, что перебор большой, и пытаюсь Вас навести на изменение мат.модели. Разрешить сколь угодно мелко дробить ингредиенты, а то что в непрерывном случае получится, с доверительной вероятностью и с непонятной точностью ,но отобразит правильный ответ в дискретном случае. Еще бы метод отбрасывать "линейно зависимые" и "заведомо неоптимальные" реакции" пригодился- так давайте в более простом (непрерывном) случае сформулируем. Вот если Вас попросят разбить число на 2 части,чтоб максимизировать произведение, Вы сначала ответите" на равные" а потом поинтересуетесь четностью.Потому что первое дает принцип , а 2е поправку к нему. Так и здесь я бы предпочел (вместе с Вами) искать Принцип.

[mserg]

Сколько я таких задач ни видел - еще никто не превзошел линейное программирование. Разумеется самописные программы будут работать погано, т.к. разработка подобного вида - дело всей жизни.

Давайте данные - получите ответ. Не проблема.

[fiktor]

Есть следующая задача, про которую известно, что она NP-сложна.
Есть множество из N целых чисел. Нужно узнать, существует ли такое его непустое подмножество, элементы которого в сумме дают 0.
Вот описание этой задачи на en.wikipedia.org.

Сведем вашу задачу к этой. Пусть есть массив целых чисел S длиной N.
Возьмем в вашей задаче N+2 ингридиента и назовем их так: первое число из S, ..., N-ое число из S, сумма взятых, усталость.
В начале есть по одному числу из S: I= (1,1,..., 1,1, 0, 0)
Операции "взять число i" выглядят так:
$R_i$ = (0,...,0, -1 на i-ом месте, 0,...,0, S_i, 1)
А функция F выглядит так:
F(I) = 1 если $I_{N+1}$=0 и $I_{N+2} > 0$
и F(I) = 0 в противном случае.

В результате решения вашей задачи мы узнаем, чему равна максимальная ценность F. Если она равна 1, то такое непустое подмножество есть, если нулю --- нет.

Таким образом ваша задача NP - сложна.

[mbaitoff]

fiktor в сообщении #236521 писал(а):

Таким образом ваша задача NP - сложна.

есть ли шанс упростить эту задачу, перейдя к непрерывным, а не дискретным ингридиентам (например, вводом весов $c_k$ в реакциях), или как-то её видоизменить, например, задав исходное количество ингридиентов бесконечным, и поставив вопрос о том, какое из веществ самое необходимое (наиболее расходуемоме, "популярное")?

зы. задача родилась после одной он-лайновой флеш-игрушки, типа тетриса, в которой вместо кубиков - разные вещества; выигранные вещества можно смешивать в "котле" и получать другие вещества, включая "жетон" на дополнительную игру. http://www.naturalchemist.com