Алгоритм поиска оптимального сочетания товаров и магазинов для минимизации затрат

Question

Привет, люди Stackoverflow,

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

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

• Цена книги постоянна для магазина.
• Цена доставки может варьироваться в зависимости от количества книг или общей стоимости книг.
• Каждый объект магазина может взять массив книг и вернуть стоимость доставки.
• Часто не каждый магазин продает каждую книгу.

Не уверен, стоит ли ссылаться на мой сайт здесь, но он указан в моем профиле пользователя.

Я бы хотел найти самую дешевую комбинацию магазинов и книг.

Боюсь, это требует подхода грубой силы - и с 35 магазинами количество комбинаций будет огромным для скромного количества книг. Я чувствую, что количество комбинаций (#shops) ^ (# books) - но не 100%

Вопрос в том, какой подход я должен использовать? Эта проблема вписывается в хорошо известный класс проблем? Если требуется грубая сила, каков хороший способ сделать это в Ruby, и могу ли я расставить приоритеты в магазинах, чтобы попробовать в первую очередь?

Answer 1

К сожалению, это пример комбинаторной задачи оптимизации, которая не имеет простого решения. Вы правы, что на самом деле вам нужен подход грубой силы. Тем не мение! Я подозреваю, что в этой проблеме есть какая-то особая структура, которая поможет. Например, стоимость доставки не будет меняться случайным образом при изменении комбинации книг - она, вероятно, будет расти сублинейно и / или насыщаться при добавлении книг.

Вот что я рекомендую, тогда:

1. В автономном режиме, оцените правила доставки каждого магазина, чтобы, учитывая книги (и, возможно, их вес), вы могли оценить стоимость доставки без со ссылкой на их сайты.
2. Для каждого магазина подсчитайте, сколько будет стоить каждая книга, если она имеется.
3. В автономном режиме, пройдите через каждый магазин или набор магазинов и оцените, используя ваши правила доставки в автономном режиме, сколько будет стоить общая сумма.
4. Выберите магазин (или магазины) с самой дешевой стоимостью. Если есть несколько похожих, рассчитайте точный ответ.

Это должно начать вас, и вам не хватит полного поиска.

Answer 2

Попробуйте использовать подход динамического программирования. Вы можете прочитать об этом здесь: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg Также вы можете прочитать об этом в википедии или в книге «Введение в алгоритмы» (Cormen).

Это вполне стандартная проблема.

Answer 3

Это вариант того, что классически называется «Задача назначения». Классическая точка доступа имеет несколько стандартных решений, включая алгоритм Munkres (он же «венгерский») и алгоритм JVC (Junker Volgenant Castanon iirc).

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

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

Удачи, звучит как забавная проблема!

Answer 4

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

Хотя я не уверен на 100%, но думаю, что это связано с проблемой Рюкзак , которая (как мы все сейчас должны, хаха ..) является NP-полной.

Сейчас нет ничего лучше, но удачи!

Answer 5

это может быть проблема с lp? http://en.wikipedia.org/wiki/Linear_programming