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

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

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

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

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

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

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

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

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

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

Ответ 1

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

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

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

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

Ответ 2

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

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

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

Ответ 3

Я сам обдумал это. Рассмотрим следующее:

Если вам понадобится неделя, чтобы понять, кода, отладки и алгоритма, которые дает только 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: Учитывая это, это удивительно крутая проблема, и ее нужно решить, если у вас есть время.

Ответ 4

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

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

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

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

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

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

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

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

Ответ 5

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

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

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

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

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

Ответ 6

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

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

Ответ 7

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

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

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

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

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

Ответ 8

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

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

Ура!