3

ユーザーが選択した小売製品のバスケットを 1 つ以上の有効なプロモーションに一致させる従来のシステムを再開発しています。これらのプロモーションは、業界標準の BOGOF (1 つ購入すると 1 つ無料)、2 つ購入すると 3 つ目が無料になる、製品 X と Y を購入すると 10% オフになる、などです。これらのプロモーションを満たすもの。

注文時に単一の製品を照合する従来の方法とは対照的に、小売商品のバスケット全体を取得して 1 回の操作で分析するソリューションが必要です。(現在の解決策は望ましくない制限につながります)

各プロモーションには、プロモーションをトリガーするために存在する必要がある一連の適格な製品があります。これらは n 個のセット (または位置) に配置されます。たとえば、次のようになります。

Example "Buy two get third free" Promotion =

| Item 1 |             | Item 1 |             | Item 2 |
|   or   |             |   or   |             |   or   |
| Item 2 |     AND     | Item 4 |     AND     | Item 6 |
|   or   |             |   or   |             |   or   |
| Item 3 |             | Item 9 |             | Item 4 |

  Set 1                   Set 2                  Set 3

アイテムが同じセットに複数回登場する場合を除き、各プロモーションには、存在する各グループから 1 つの製品を含める必要があります。プロモーションには、製品の「セット」を無制限に (通常は 10 未満) 含めることができます。

簡単な例として、 のショッピング バスケットがItem 1, Item 4 and Item 6プロモーションをトリガーし、同様に のバスケットもプロモーションをItem 1, Item 1 and Item 2トリガーします。Item 1, Item 2 and Item 3しかし、各セットが満たされていないので、バスケットはそうではありません。

プロモーションがいつトリガーされたかを検出する最善の方法に関する明白な質問は別として、価格設定などの詳細を処理するために、アイテムが一致したセット (位置) を回復する必要もあります。それも望ましいでしょう。プロモーションに割り当てる際に、より高価な (通貨換算で) アイテムがより安価な (同等に一致する) アイテムよりも優先される場合。

次の部分が解決策に役立つことを願っています。不要なノイズが発生するほど不明瞭な音ではありません。無視してかまいません。

これまでの私の最善の解決策は、このアイテムが満足するプロモーション セット (位置) を保持する「ショッピング バスケット」内の各小売アイテムに対して新しいセットを作成することです。すなわち。

Item 1 satisifies sets: {1,2}
Item 4 satisifies sets: {2,3}
Item 6 satisifies sets: {3}

次に、このセットのリストに各ポジションに固有のアイテムが含まれていること、および各プロモーションポジションが満たされていることを「確認」するというのが私の理論です。これまでのところ、私の作業例はすべて、ブルートフォース、ループ、または再帰を使用して、セットのすべての組み合わせ (上記) を生成し、一意の組み合わせがあるかどうかを確認しようとしています。これはスケーリングが非常に悪く、非常に些細な例以外では、現実の世界ではまったく機能しません。(この関数は、アイテムがバスケットに追加されるとリアルタイムで呼び出されるため、高速である必要があります)

多くの研究は、二部マッチングが望ましい結果を生み出すことを示唆していますが、私は研究記事と、この主題に関するかなり複雑な数学的テキストしか見つけることができません. いくつかの疑似コードまたは基本的なロジックは素晴らしいでしょう。

私の2つの質問は基本的に次のとおりです。

1) 顧客バスケットを分析してマッチング プロモーションを作成するための、より優れた/より迅速な/簡単な方法を知っている人はいますか?
2) アイテムを関連する位置に一致させる最も効率的な方法を特定したと仮定すると、プロモーションに対して記録する小売アイテムのリストを決定する最も安価な方法は何ですか.

トンネルの終わりに光が見えなくなったので、どんな支援もありがたく受け取られます! (最終的なソリューションは .NET であり、SQL Server 2008 R2 を使用します。)

4

1 に答える 1

1

特定のショッピング カートで各プロモーションの有効性を確認する作業は、 Max Flowに減らすことができます。私のソリューションの説明では、グラフベースの Max フローの問題を実装して解決できると想定しています。そうでない場合、それは解決すべき 2 番目の問題です (幸いなことに、はるかに一般的な問題です)。

アルゴリズムへの入力を次のようにします。

  • すべての有効なアイテムのセットI。アルゴリズムの最終的なコーディングで必ずしも使用されるわけではありません。
  • Cサイズのショッピング カート、含まれるアイテムnのサブセット。したがって、IC_1 ... C_nC = {C_i}i = 1...n
  • それぞれが可変数のアイテムを保持するサブセットでP構成される単一のプロモーション。m各サブセットSは のサブセットですI。各サブセットは重複することはできませんが、1 つのアイテムが複数のサブセットにまたがって存在することはできます。

次のようにグラフGを作成します。

  • ラベル付けされたスーパー ソース ノードを追加します。SOURCE
  • ラベル付けされたスーパー シンク ノードを追加します。SINK
  • C_iショッピング カート内の一意のアイテムごとCに、使用可能なアイテム ノードを追加し、次に、 inの出現回数に等しい容量を持つA_iエッジ からSOURCEを追加します。A_iC_iC
  • Promotion のサブセットごとに、以下を追加します S_i。P
    • 1 つのセット ノードと、 からまでS_iのエッジと容量。S_iSINK1
    • の必須項目ごとI_jにS_i、必須項目ノード、および容量からまでB_i_jのエッジ。B_i_jS_i1
  • 最後に、ノードの各ペアについてA_x、B_yそれらが表す項目が同等であるように、 からA_xへのエッジB_yと capacity 1.

SOURCE最後に、ソースおよびSINKシンクとして最大フロー アルゴリズムを実行します。結果の最大フローの値がサブセットの数 ( ) と等しい場合m、出力 true - このショッピング カートでプロモーションを満足させることができます。それ以外の場合は false を出力 - このショッピング カートではプロモーションを満たすことができません。

たとえば、セットの例では、ショッピング カートを使用{1,1,4,6}して、次のグラフを作成する必要があります。

たとえば、サンプル グラフ

予想される時間の複雑さ。アイテムn数は 、プロモーションのサブセット数はm:

  • グラフの構築:
    • 追加SOURCEしてSINK-O(1)
    • カートからのユニークなアイテムとソースからのエッジの追加 -O(N)
    • サブセットと必要な項目ノード、および間のエッジを追加 -O(N*M)
    • サブセット ノードからシンクへのエッジの追加 -O(M)
    • 対応する項目ノード間にエッジを追加 -O(N^2)
    • 合計 -O(N^2 + N*M) = O(N * (N+M))
  • Max Flow Algorithm - ウィキペディアのページを参照してください。簡単な実装コスト - O((N*M)^3). より複雑なアルゴリズムで改善できます。
  • 解決策を取得しています - O(1)。
于 2016-01-21T18:04:12.497 に答える