8

こんにちはStackoverflowの人々、

私は、そのユーザーが本を買うのに最も安い場所を見つけるサイトを運営しています。これは1冊の本の場合は簡単ですが、複数の本の場合は、ある店舗で1冊の本を購入し、別の店舗で別の本を購入する方が安い場合があります。

現在、ユーザーリストにあるすべての本を販売している最も安い店を見つけましたが、よりスマートなシステムが必要です。ここにいくつかのより多くの情報があります：

  • 本の価格は店にとって一定です。
  • 送料は、本の数や本の総額によって異なります。
  • 各ショップオブジェクトは、一連の本を受け取り、送料を返すことができます。
  • 多くの場合、すべての店がすべての本を販売しているわけではありません。

ここで私のサイトにリンクするのがクールかどうかはわかりませんが、それは私のユーザープロファイルにリストされています。

一番安いお店と本の組み合わせを見つけたいです。

総当たり攻撃が必要になるのではないかと心配しています。35のショップがあるため、適度な数の本の場合、組み合わせの数は膨大になります。組み合わせの数は（#shops）^（＃books）だと思いますが、100％ではありません

問題は、どのようなアプローチを使用すべきかということです。この問題は、よく知られているクラスの問題に当てはまりますか？ブルートフォースが必要な場合、Rubyでこれを行うための良い方法は何ですか？ショップに優先順位を付けて最初に試すことはできますか？

4

6 に答える 6

6

残念ながら、これは簡単な解決策がない組み合わせ最適化問題の例です。一般的に、ブルートフォースアプローチが必要です。でも！この問題には、役立つ特別な構造があるのではないかと思います。たとえば、書籍の組み合わせを変更しても送料はランダムに変更されません。書籍を追加すると、おそらく亜直線的に増加したり、飽和したりします。

これが私がお勧めするものです：

  1. オフラインで、各ショップの配送ポリシーを見積もります。これにより、本（およびおそらくその重量）が与えられた場合、サイトを参照せずに送料を見積もることができます。
  2. 店舗ごとに、利用可能な場合は、各本の費用を計算します。
  3. オフラインで、各ショップまたは一連のショップを調べ、オフライン配送ポリシーを使用して、合計金額を見積もります。
  4. 最も安いショップを選択してください。類似するものが複数ある場合は、正確な答えを計算してください。

それはあなたが始めるはずであり、あなたを完全な検索に近づけないでしょう。

于 2010-01-08T05:13:15.763 に答える
2

これは、古典的に「代入問題」と呼ばれるもののバリエーションです。従来の AP には、Munkres (別名「ハンガリー語」) アルゴリズムや JVC (Junker Volgenant Castanon iirc) アルゴリズムなど、いくつかの標準的なソリューションがあります。

基本的な考え方は、割り当てごとのコスト (つまり、各店舗で各本を購入するコスト) を計算し、合計コストを最小化する一連の割り当てを選択することです。これは多項式時間で実行できると思います。

各小売業者からの送料が注文の合計に依存するという事実は、物事をかなり複雑にします. 最初は送料を考慮せず、いくつかの有望な割り当てを特定したら、総注文に対して考慮するハイブリッド アプローチを使用できる場合があります。

がんばってください、楽しい問題ですね！

于 2010-01-08T05:15:20.293 に答える
2

動的計画法のアプローチを使用してみてください。ここでそれについて読むことができます: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg また、ウィキペディアまたは「アルゴリズムの紹介」本 (コーメン) でそれについて読むことができます。

ごく標準的な問題です。

于 2010-01-08T05:16:15.300 に答える
1

ブルートフォースは、ほとんどの場合、優れたヒューリスティック、つまり、最適ではないが「十分に優れた」パフォーマンスを発揮することが知られているアルゴリズムに置き換えることができます。

100％確信はありませんが、これはナップサック問題に関連していると思います。これは（私たち全員が今ハハになっているはずですが..）NP完全です。

今すぐ提供できるものはありませんが、頑張ってください！

于 2010-01-08T05:14:14.117 に答える
0

これはlpの問題でしょうか？http://en.wikipedia.org/wiki/Linear_programming

于 2010-01-08T05:34:49.400 に答える