Какой алгоритм использовать для подбора ингредиентов по составу?

Question

[Rukis]

Подскажите название алгоритма или как бы вы решали такую задачу?

В чём суть: есть целевой состав смеси, например a: 10%, b: 40%, c: 25%, ... и есть набор ингредиентов, которые включают в себя 1 или несколько из a, b, c в разных пропорциях. От программы требуется подобрать ингредиенты (то есть рассчитать какие именно и в каком количестве взять) таким образом, чтобы наилучшим (допускается приближенное решение) образом соответствовать целевому составу смеси.

То же самое, на примере кулинарии: надо получить смесь максимально близкую к такому составу: белков 10%, жиров 40%, углеводов 25%. Даны ингредиенты: сахар, масло, мука, сало, хлеб... (для всех известен БЖУ состав).

Целевой состав и доступные ингредиенты - это входные данные, ограничены сверху 10 штуками. То есть состав может быть от 1 до 10 позиций и набор ингредиентов от 1 до 10 штук.

ещё пример с решением

цель:
a: 10%, b: 40%, c: 25%

ингредиенты:
D: [a: 5, b: 10]
E: [c: 50]
F: [b: 20]

решение:
2D + 0.5E + 1F

Comments

[mayton2019]

Похоже на решение системы линейных уравнений. Кстати надо проверить существует ли решение.

[Akina]

mayton2019, почему "похоже"? СЛАУ и есть...

[Wataru]

Rukis,

наилучшим (допускается приближенное решение) образом

Что значит "наилучшим образом"? Может можнго подобрать все кроме одного ингредиента идеально, а остальной вообще не так. Или можно все чуть-чуть с откланениями набрать. Какой вариант лучше и почему?

Если есть точное решение, то это будет решением простой системы линейных уравнений : представьте, что вы берете x_i i-ого товара по весу. Тогда составьте уравнения - ингредиента ото всех товаров по весу столько же, соклько должно быть в общем весе всех взятых товаров. Плюс еще уравнение, что сумма всех весов равна 1, потому что любое решение можно отмасштабировать, просто взяв всех товаров чуть меньше или больше.

Ну и там еще нужны условия, что все переменные неотрицательны.

Если точного решения нет, то там какая-то задача оптимизации. Какая именно, и как ее решать - зависит от того, что вы считаете "наилучшим" образом.

[Rukis]

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

[Wataru]

Rukis,

под наилучшим имею ввиду результат с наименьшим отклонением от цели,

Ну вот, допустим надо набрать (10%, 20%, 30%). Есть варианты набрать (12%, 18%, 32%) или (11%, 19%, 35%). Какой лучше и почему?

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

[Adamos]

Wataru, если прикладывать задачу к реальности - придется вводить веса ингредиентов по важности отклонений.
Например, в рецепте бисквита лишнее яйцо некритично, а вот лишняя ложка соли - весьма ;)

[Wataru]

Adamos, Ну веса в метрику добавить элементарно. Но это автор должен сформулировать как именно определять наименьшее отклонение. Хотя бы словами.

[Rukis]

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

По правде говоря оба предложенных вами варианта выглядят вполне приемлемыми в качестве ответа.

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

[Wataru]

Rukis, Раз нужно относительно, то предлагаю такую метрику: sum_i w[i]^2 (actual[i]/ needed[i] - 1) ^ 2.

w[i] - важность данного ингредиента, это если вам какой-то ингридиент важнее.

needed[i] - соклько его надо

actual[i] - сколько получили.

[hint000]

Wataru,

важность данного ингредиента

А ещё можно представить себе несимметричную важность отклонения. Как выше Adamos привёл пример с бисквитом: плюс одна ложка соли его испортит критично, а минус одна ложка соли (от идеального количества) лишь сделает пресноватым, но всё ещё вполне съедобным. И наоборот, избыток воды обычно легче компенсировать при дальнейшей термообработке, а при недостатке воды либо подгорит, либо останется сырым...

Answer 1

[Сергей П]

Выглядит как NP-полная задача, чем-то напоминающая задачу укладки многомерного рюкзака или n--мерную задачу раскроя.
Но ваши ограничения в 10 компонентов позволяют решать эту задачу перебором. Тем более для кулинарии допустимо не слишком упарываться с точностью и ввести квантиикацию компонентов, чтобы иметь дело с целочисленными пропорциями.

Кстати, я так понимаю, что во всех ингридиентах и результирующем блюде должен быть ещё какой-то специальный ингридиент Z, который будет дополнять выделенные компоненты (например БЖУ) до 100%. Типа инертный наполнитель.
Допустим у вас есть полный перечень из N доступных ингридиентов. записанных в виде многомерных векторов.
Вам нужно взять из него подмножество M <= 10 и просуммировать с коэффициентами так, чтобы получилось равенство. Найти нужно x1, x2, x3...x10 - коэффициенты.

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

Решать можно генетическими алгоритмами или роевыми.
Фитнес функцией будет норма отклонения от пропорции.

Answer 2

[Wataru]

Как выяснили в комментариях, метрика будет sum_i w[i]^2 (actual[i]/ needed[i] - 1) ^ 2.

пусть x[i] - соклько i-ого продукта
Пусть a[i][j] - сколько в еденице i-ого продукта j-ого ингредиента. Тогда всего j-ого ингредиента будет sum_i a[i][j] x[i].

Тогда получаем следующую оптимизационную задачу:

Sum_j (sum_i A'[i][j] x[i] - C[i]) ^ 2 -> min
sum_i x_i = 1
x_i >= 0

Сумма всего приравнивается к 1, потому что иначе надо считать пропорции и получится вообще ужас-ужас.

A'[i][j], C[i] - какие-то числа, которые элементарно получаются из a[i][j], w[i] и needed[i].
A'[i][j] = a[i][j]*w[j]/needed[j]
C[j] = w[j] / needed[j];

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

Можно применить метод лагранжа, а точнее метод Каруша — Куна — Таккера

Сначала выразите x_1 = 1 -sum_j>1 x_j, подставьте во все уравнения и получите:
Sum_j (sum_i A''[i][j] x[i] - C'[i]) ^ 2 -> min
sum_i x_i -1 <= 0
x_i >= 0

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

Для условия жесткости придется рассмотреть 2 случая - лямбда - 0 или тогда sum_i x_i - 1 = 0

Прорешать оба случая (СЛАУ) и взять те, где все получается положительным.

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