Как найти лучшую цену за колоду коллекционных карт?

Question

Или Путешествующий продавец играет в Магию!

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

TCGPlayer.com продает коллекционные карты для различных игр, в том числе Магическое Собрание .Вместо того, чтобы просто продавать карты из своего инвентаря, они на самом деле являются перепродавцем от нескольких продавцов (50+).Каждый продавец имеет различный инвентарь карт и разную цену за карту .Каждый поставщик также взимает фиксированную ставку за доставку (обычно).Учитывая все это, как найти лучшую цену за колоду карт (скажем, 40 - 100 карт)?

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

Однажды вечером я написал простой HTML Scraper (с использованием HTML Agility Pack ), который собирает все разные цены для каждой карты, а затем находит всех продавцов, которые несут все карты вколода, суммирует цены карт от каждого продавца и сортирует по цене.Это было действительно легко.Общие цены оказались близкими к общей средней цене для всех карт.

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

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

Если бы вы собирались заняться этим, как бы вы это сделали?Чисто Грубая сила вычисляет каждую возможную комбинацию комбинаций карт / вендоров?Процесс, который с большей вероятностью будет выполнен в моей жизни, может включать методическую серию оценок в течение фиксированного числа итераций.У меня есть пара идей, но мне любопытно, что могут предложить другие.

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

Answer 1

Я бы просто был жадным.

Предположим, что вы собираетесь съесть стоимость доставки и купить у всех поставщиков.Определите самую низкую цену, которую вы получите.Затем для каждого продавца определите, насколько экономит вас возможность купить у них несколько карт по сравнению с кем-то еще.Заказывайте поставщиков по отгрузке - дополнительная экономия.

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

Это должно найти хорошее решение, но не гарантировано, что вы найдете лучшее решение.Однако найти абсолютное лучшее решение, скорее всего, непросто.

Answer 2

Это изоморфно некапитализированной локации объекта проблема.

• карта в колоде: клиент

• продавец: возможное местоположение объекта

• стоимость доставки поставщика: стоимость открытия объекта в местоположении

• стоимость карты с конкретным поставщиком: "«расстояние» от клиента до объекта

Расположение объекта - хорошо изученная проблема в литературе по комбинаторной оптимизации.

Answer 3

А как насчет использования генетического алгоритма? Я думаю, что попробую это сам. Вы можете манипулировать пулом, добавив как хромосому с самыми низкими ценами, так и другую с самыми низкими затратами на доставку.

Кстати, вы, наконец, реализовали какое-либо из представленных здесь решений? который из? почему?

Ура! * * 1005

Answer 4

Я на самом деле написал именно эту вещь в прошлом году. Первое, что я делаю после загрузки всех цен, я отсеиваю свой пул карт:

• Каждый поставщик может иметь несколько версии каждой карты, так как есть перепечатки. Найти самый дешевый.
• Удалите все карты, стоимость которых больше, чем самая дешевая карта + комбо доставки. То есть, если я могу купить карту дешевле в качестве единовременного для продавца, чем добавить ее к существующему заказу в вашем магазине, я куплю ее у другого продавца.
• Исключите любого продавца, предложение которого я могу купить дешевле (для каждой карты) у другого продавца. По сути, если другой продавец переоценивает вас по каждой карте и по сумме + доставка, то вы ушли.

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

Во всяком случае, я настроил его до такой степени, что я могу сделать 70 карт и в течение минуты получить в пределах 5% от оптимальной цели. И через час менее 2%. А потом, через пару дней, фактический, окончательный результат.

Я собираюсь прочитать больше о планировании объекта. Спасибо за этот совет!

Answer 5

Как насчет этого:

1. Рассчитайте среднюю цену за заказанную карту для всех поставщиков.
2. Для каждого продавца, у которого есть хотя бы одна из карт, рассчитайте общую экономию для всех карт в заказе как разницу между ценой каждой карты у этого продавца и средней ценой.
3. Начните с продавца с наибольшей общей суммой сбережений и выберите все эти карты от этого продавца.
4. Продолжайте выбирать поставщиков со следующей по величине общей суммой сбережений до тех пор, пока все карты в выбранном порядке не будут выбраны. Пропустите поставщиков, у которых нет карт, которые вам все еще нужны.
5. Из выбранного списка продавцов перераспределите покупки по карточкам среди поставщиков с лучшей ценой для этой карточки.
6. Из оставшегося списка поставщиков, и, если список достаточно мал, вы можете грубо заставить любых поставщиков с низким количеством карт проверить, можете ли вы переместить карты другим поставщикам, чтобы исключить стоимость доставки.

Answer 6

мой алгоритм выглядит следующим образом:

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

Я все еще думаю над следующими шагами, но я ставлюгрубая идея здесь

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

я знаю, что это потребует огромной оптимизации.но это то, что я понял, надеюсь, это поможет

Answer 7

Интересный вопрос!:)

Так что, если у нас n карт и m поставщиков, подход грубой силы может потребовать проверить до n ^ m комбинаций, верно (немного меньше, поскольку не у каждого продавца есть каждая карта, но я предполагаю, чтоне имеет большого значения в общей схеме вещей;).

Давайте на секунду предположим, что у каждого поставщика есть каждая карта, а затем посмотрим, как все изменится, если они этого не сделают.

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

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

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

---

Хорошо, после написания всего этого я понялпредположение n ^ m на самом деле неверно.После того, как вы выбрали набор поставщиков для покупки, вы можете просто выбрать самого дешевого поставщика для каждой карты.Это большое преимущество, потому что индивидуальный выбор места покупки каждой карты не мешает друг другу.

Что это значит для нашей проблемы?На первый взгляд, это означает, что выбор дилеров - это проблема (с точки зрения вычислительной сложности), а не индивидуальное распределение ваших вариантов покупки.Таким образом, вместо n ^ m вы получаете 2 ^ m возможных конфигураций в худшем случае.Так что нам нужна эвристика для выбора поставщиков, а не отдельных карт.Что может сделать эвристику сверху еще более оправданной.

Answer 8

Я сам обдумывал это.Подумайте над следующим:

Если вам понадобится неделя, чтобы выяснить, написать код, отладку и алгоритм, который предоставляет только 1% скидку, вы бы это сделали?* Ответ, вероятно, «Нет» (если вы не тратите все свои сбережения на карты, в этом случае вы можете быть сумасшедшими).=) ... или Amazon.com

Следовательно, уже существует простой алгоритм аппроксимации:

Wait until you're buying lots of cards (reduce the shipping overhead).
Buy the cards from 3 vendors:
    - the two with the cheapest-but-most-diverse inventories
    - a third which isn't really cheap but definitely has every card you'd want.
Optimize accordingly (for each card, buy from the cheaper one).
Also consider local vendors you could just walk to, pre-constructed decks, and trading.

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

Я вспоминаю старую поговорку: «Никогда не оптимизируйте, пока это не станет абсолютно необходимым; скорее всего, вам это не понадобится, или вы бы оптимизировали не то». (например, ваше время также является ресурсом и также имеет денежную ценность)

edit: Учитывая это, это удивительно крутая проблема, и ее нужно решить, если есть время.