Алгоритм, чтобы найти, что оптимальная комбинация продуктов и магазинов минимизирует стоимость
Привет там люди Stackoverflow,
Я выполняю сайт, который находит его пользователей самым дешевым местом для покупки книг. Это легко для единственной книги, но для нескольких книг может иногда быть более дешево купить одну книгу в одном хранилище и другую книгу от другого хранилища.
В настоящее время я нахожу самое дешевое хранилище, которое продает все книги в списке пользователя, но я хочу иметь более умную систему. Вот еще некоторая информация:
- Цена книги является постоянной для хранилища.
- Цена поставки может варьироваться, в зависимости от # книг или итогового значения книг.
- Каждый объект магазина может взять массив книг и возвратить стоимость доставки.
- Часто, не каждый магазин продает каждую книгу.
Не уверенный, если здорово связаться с моим сайтом здесь, но это перечислено в моем профиле пользователя.
Я хотел бы смочь найти самую дешевую комбинацию хранилищ и книг.
Я боюсь, что это требует метода решения "в лоб" - и с 35 магазинами, количество комбинаций будет огромно для скромного количества книг. У меня есть чувство, что количество комбинации (#shops) ^ (#books) - но не 100%
Вопрос, какой подход я должен использовать? Эта проблема помещается в известный класс проблем? Если грубая сила требуется, что такое хороший способ сделать это в Ruby, и я могу расположить по приоритетам магазины для попытки сначала?
5 ответов
К сожалению, это пример задачи комбинаторной оптимизации, которая не имеет простого решения. Вы правы, что, в общем-то, вам нужен подход грубой силы. Однако! Подозреваю, что в этой задаче есть какая-то особая структура, которая поможет. Например, стоимость доставки не будет меняться случайным образом по мере изменения комбинации книг - она, вероятно, будет увеличиваться сублинейно и/или насыщенно по мере добавления книг.
Вот что я рекомендую, то:
- Оффлайн, оценить политику доставки каждого магазина, так что, учитывая книги (и, возможно, их вес) вы можете оценить стоимость доставки без со ссылкой на свои сайты.
- Для каждого магазина рассчитайте, сколько будет стоить каждая книга, если она есть в наличии.
- Оффлайн, пройти через каждый магазин или набор магазинов, и оценить, используя ваши оффлайн политики доставки, сколько будет стоить общая стоимость.
- Выберите магазин (или магазины) с самой низкой стоимостью. Если есть несколько похожих магазинов, рассчитайте точный ответ.
Это поможет вам начать поиск, и вы не сможете воспользоваться полным поиском.
Это разновидность того, что классически называется "проблемой присвоения". Классическая АП имеет несколько стандартных решений, включая алгоритм Мункреса (также известный как "венгерский") и алгоритм JVC (Junker Volgenant Castanon iirc).
Основная идея состоит в том, чтобы вычислить стоимость каждого задания (то есть стоимость покупки каждой книги в каждом магазине), а затем выбрать набор заданий, которые минимизируют общую стоимость. Полагаю, это можно сделать в полиномиальное время.
Тот факт, что стоимость доставки от каждого продавца зависит от общего заказа, значительно усложняет ситуацию. Вы можете использовать гибридный подход, который изначально не учитывает стоимость доставки, а затем делает это для совокупных заказов, как только вы определили несколько многообещающих заданий.
Удачи, звучит забавно!
Попробуйте использовать динамический подход к программированию. Вы можете прочитать об этом здесь: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg Также вы можете прочитать об этом в Википедии или в книге "Введение в алгоритмы" (Cormen).
Это довольно стандартная проблема.
Грубая сила почти всегда может быть заменена на хорошую эвристическую, т.е. алгоритм, который, как известно, работает не оптимально, но "достаточно хорошо".
Хотя я не уверен на 100%, я думаю, что это связано с проблемой рюкзака , которая ( как мы все теперь должны хаха... ) NP-завершена.
Сейчас нечего предложить, но удачи!
может это проблема с липопротезированием? http://en.wikipedia.org/wiki/Linear_programming