Алгоритм для минимизации стоимости товаров от разных поставщиков, какие ресурсы изучить?
Пытаюсь на коленке для себя написать небольшой проект, но в алгоритмах не слишком силен. Встал в тупик и интересуюсь в какую сторону копать.
Задача:
Есть некое колличество различных товаров, в моих тестовых данных это 87.
Есть различные продавцы, которые продают эти товары. (В моих данных, 163) У каждого из них есть только некоторые из нужных товаров в наличии и различные цены + доставка.
Нужно найти, у кого и какие товары заказать, чтобы получилось дешевле всего. Так, чтобы в итоге мы получили все нужные товары. Цену доставки можно считать постоянной.
Примеры - у нас может быть один продавец, который продает все товары, но дороже чем остальные, у которых есть только часть товаров, мы можем заказать от разных продавцов, заплатив больше за доставку, но в итоге секономив засчет более низких цен. Или наоборот, у нас есть куча продавцов, которые продают по одному товару очень дешево, и один который продает все сразу, но дороже. Тогда мы можем заказать подороже, но секономив за счет того что доставку платим один раз.
Уже какое-то время пытаюсь решить задачу в лоб, не то чтобы сильно нужно было, но просто самому уже интересно разобраться :)
Пока что за вменяемое время получилось сделать только минимизацию колличества продавцов - делал из предположения, что разброс цен не сильный. Но быстро обнаружил, что у кого самый большой ассортимент - цены тоже самые большие, и получается так себе.
Цены минимизировать тупым перебором пробовал - но тоже получается очень долго т.к. слишком много возможных комбинаций, даже если делать оптимизации, подсовывая в начало перебора "наиболее перспективных" продавцов и обрывая перебор, если текущая цена уже превысила минимально найденную.
Уверен что на основе этого можно сделать быстрый поиск "достаточно оптимального" решения, если не перебирать все возможные комбинации, а останавливать это все через какое-то время, предполагая что с оптимальными продавцами в начале, мы за первые несколько проходов найдем приемлемое решение, а потом будем лишь в пустую бегать, выжимая оставшиеся копейки.
Собственно задача звучит как что-то, что где-то уже пытались решить, просто я об этом не знаю :) Поэтому в первую очередь интересно если есть какие-то готовые решения\структуры данных, которые умеют делать это или похожее. Понимаю, что скорее всего нужно копать куда-то в сторону комбинаторики, но не знаю правильные слова чтобы спросить гугл :)
Mors Clamor, Не совсем понимаю, что имеете ввиду. Вариант чего? Предлагаете рассчитывать граничные варианты - "заказываем и минимального колличества продавцов"/"заказываем по минимальным ценам игнорируя продавцов и доставку"?
угу. вы на своем примере поняли почему жадные алгоритмы не работают и практически пришли к branch-and-bound. "достаточно неплохое" решение можно получить эвристиками, лучшее - только перебором (правда, не полным, но иногда весьма длительным т.к. надо доказать что это действительно лучшее решение).
у вас задача о рюкзаке (наполнить рюкзак необходимым кол-вом товаров при условии минимизации общей цены).
вот тут я даже набрасывал пример решения такого типа задач с использованием готовых солверов (модель у вас другая, но принцип тот-же): Какие есть достойные альтернативы жадному алгоритму (greedy)?. По крайней мере там есть все ключевые слова чтоб понять что надо искать дальше
(ну и да, это далеко не единственный способ решения, я просто ленивый и описать модель для мип солвера у меня выходит быстрее всего. Илья Николаевский и Сергей Соколов смогут еще много интересного добавить)
Можно свести к линейному целочисленному программированию (linear integer programming).
Индикаторные переменные (0 или 1) - покупаете ли вы этот товар у этого продавца (x_ij).
Еще переменные - платите ли этому продавцу за доставку (y_j).
Ограничения:
y_j >= x_ij
sum_j (x_ij) = 1
Целевая функция - мнинимизировать затраты: sum_ij x_ij*c_ij + sum_j y_j*d_j
Потом решать каким-либо солвером (есть куча быстрых библиотек).
Еще можно всякие методы отжига или генетические алгоритмы использовать.
Можно еще полный перебор с отсечениями. Очевидно, что если мы берем какое-то множество продавцов, то каждый из них должен иметь минимальную цену по какому-то товару. Это значит, что можно поддерживать текущие минимальные цены на все товары у выбранных продавцов (+бесконечность, если никто не продает этот товар). Вы можете брать какого-то продавца, только если его цена по какому-то товару меньше. Ну и всякие ранние выходы - если сумма минимальных цен вообще по всем + текущие траты за доставку выше оптимального пока что ответа, дальше добавлять продавцов смысла нет.
Очевидно, что если мы берем какое-то множество продавцов, то каждый из них должен иметь минимальную цену по какому-то товару.
Один продавец имеет оба товара, еще два продавца имеют по одному товару дешевле, чем у первого, но если платить за доставку обоим, сумма выйдет больше, чем заказать два товара с общей доставкой у первого.
Adamos, Поэтому брать всех трех продавцов - невыгодно. Если какой-то продавец не дает минимум покакому-то товару, то все покупаемые у него товары можно купить у кого-то другого дешевле. Значит можно сделать так и выкинуть этого продавца и не платить ему за доставку.
Брать только перовго продавца или только двух других - локально оптимальные решения и их оба придется рассматривать в переборе.
Это лишь критерий оптимальности, достаточный, но не необходимый. Я предложил использовать его для отсечения в переборе.
Илья Николаевский, Да, если продавец не дает минимума ни по одному из товаров, купив у него все равно можно секономить на доставке. Условно доставка фиксированная 100 рублей. Он продает 2 товара по 110. Другие два продавца продают по одному товару по 100. Если закажем у других продавцов - получим 400 (200 за товары + 100 за доставку от каждого). Если закажем у него - 320.
Adamos, Как в вашем примере отсекается оптимальный вариант? Вариант "берем только первого продавца" - не отсекается, потому что он имеет минимум по всем товарам из всех взятых продавцов (он один).
Критерий не говорит, что какого-то продавца никогда не будет смысла брать потому что другие существуют. Он говорит, что не будет смысла брать его вместе с некоторыми другими.
Вот еще раз цитата:
Очевидно, что если мы берем какое-то множество продавцов, то каждый из них должен иметь минимальную цену по какому-то товару.
Илья Николаевский, видимо, я чего-то не понимаю, и ТС, видимо, тоже. Можете привести пример, чтобы не путаться в словах?
У первого продавца из примера выше нет минимальной цены ни на один товар по отдельности, может не быть даже минимальной цены на весь набор товаров. Просто логистика в остальных случаях сожрет больше, чем разница в цене товаров.
Илья Николаевский, кажется, дошло: вы имеете в виду отсечку не ДО перебора, а внутри перебора. Предполагая, что если мы точно берем вот у этого и вот того продавца, то для каждого из товаров, которые мы точно берем у того или другого, имеет смысл рассматривать только самый дешевый вариант. Возможно, и так.
Но вообще-то у них может быть "скидка 5% от суммы, начиная с...".
Или ограничения доставки, когда набор больше определенного веса - это уже другая доставка. Или, наоборот, бесплатная доставка при сумме заказа от...
Логистика вообще здорово запутывает этот перебор.
Adamos, Это конечно правильно, но для конкретно моей ситуации гораздо проще. Цена всех товаров у продавцов фиксированная и скидок нет, доставка тоже всегда по одной цене независимо от кол-ва товаров (на самом деле нет, но в 90% случаев это так, остальные можно откинуть руками).
Тарасов Константин, тогда при переборе действительно возможна оптимизация: выбирая, из какого магазина брать очередной товар, можно считать магазин, в котором эта цена минимальна, оптимальным при условии, что он назначен одному из предыдущих товаров. Не перебирая варианты этого товара в других магазинах.
Простой
