saroff
@saroff
Enterprise Java Developer

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

Пытаюсь на коленке для себя написать небольшой проект, но в алгоритмах не слишком силен. Встал в тупик и интересуюсь в какую сторону копать.
Задача:
Есть некое колличество различных товаров, в моих тестовых данных это 87.
Есть различные продавцы, которые продают эти товары. (В моих данных, 163) У каждого из них есть только некоторые из нужных товаров в наличии и различные цены + доставка.
Нужно найти, у кого и какие товары заказать, чтобы получилось дешевле всего. Так, чтобы в итоге мы получили все нужные товары. Цену доставки можно считать постоянной.
Примеры - у нас может быть один продавец, который продает все товары, но дороже чем остальные, у которых есть только часть товаров, мы можем заказать от разных продавцов, заплатив больше за доставку, но в итоге секономив засчет более низких цен. Или наоборот, у нас есть куча продавцов, которые продают по одному товару очень дешево, и один который продает все сразу, но дороже. Тогда мы можем заказать подороже, но секономив за счет того что доставку платим один раз.

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

Собственно задача звучит как что-то, что где-то уже пытались решить, просто я об этом не знаю :) Поэтому в первую очередь интересно если есть какие-то готовые решения\структуры данных, которые умеют делать это или похожее. Понимаю, что скорее всего нужно копать куда-то в сторону комбинаторики, но не знаю правильные слова чтобы спросить гугл :)
  • Вопрос задан
  • 91 просмотр
Пригласить эксперта
Ответы на вопрос 2
ayazer
@ayazer
Sr. Software Engineer
угу. вы на своем примере поняли почему жадные алгоритмы не работают и практически пришли к branch-and-bound. "достаточно неплохое" решение можно получить эвристиками, лучшее - только перебором (правда, не полным, но иногда весьма длительным т.к. надо доказать что это действительно лучшее решение).

у вас задача о рюкзаке (наполнить рюкзак необходимым кол-вом товаров при условии минимизации общей цены).

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

(ну и да, это далеко не единственный способ решения, я просто ленивый и описать модель для мип солвера у меня выходит быстрее всего. Илья Николаевский и Сергей Соколов смогут еще много интересного добавить)
Ответ написан
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, гуглер, экс-олимпиадник.
Можно свести к линейному целочисленному программированию (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

Потом решать каким-либо солвером (есть куча быстрых библиотек).

Еще можно всякие методы отжига или генетические алгоритмы использовать.

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Bnovo Санкт-Петербург
от 110 000 до 140 000 ₽
Spice IT Recruitment Москва
от 160 000 до 200 000 ₽
03 мар. 2021, в 12:09
2000 руб./за проект
03 мар. 2021, в 12:07
200 руб./за проект
03 мар. 2021, в 12:07
11000 руб./за проект