saroff
@saroff
Enterprise Java Developer

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

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

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

Собственно задача звучит как что-то, что где-то уже пытались решить, просто я об этом не знаю :) Поэтому в первую очередь интересно если есть какие-то готовые решения\структуры данных, которые умеют делать это или похожее. Понимаю, что скорее всего нужно копать куда-то в сторону комбинаторики, но не знаю правильные слова чтобы спросить гугл :)
  • Вопрос задан
  • 146 просмотров
Пригласить эксперта
Ответы на вопрос 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

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

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

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

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

Войти через центр авторизации
Похожие вопросы