3

問題は次のとおりです。

ユーザーは商品を含むショッピング バスケットを持っています。各商品には、定義された全体的なセットから選択されたサブセットである一連の利用可能な配送タイプがあります (例: [「英国第 2 クラス」、「英国第 1 クラス」、「英国記録配送」] 、しかし正確な名前にこだわりすぎないでください)。

チェックアウト プロセスを実行する際に、ユーザーに別々の配送か組み合わせた配送のオプションを提示する必要があります。

分割は簡単です。各アイテムがそれぞれの行にある表が表示され、列のセットはアイテム間で利用可能な配送タイプの結合と一致します。各行にはラジオ ボタン セットが含まれており、そのアイテムで利用可能な配信タイプの各列に 1 つのボタンがあります。

組み合わせてどうアプローチしたらいいのかわからない。アイテムをグループにまとめることができるのは、そのグループ内のすべてのアイテムが利用可能な配送タイプのサブセットを共有している場合のみです。相互に排他的な配送タイプを持つアイテムは、同じグループに属することはできません。バスケットには、複数のベンダーのアイテムを含めることができます。この場合、異なるベンダーの製品は、配送タイプが同じであっても、グループ化されない場合があります。

クライアントは、各タイプの郵便料金のコストに関係なく、グループの最小数が計算されることを要求します。はい、つまり、4 つの商品を別々に配送すると 1 ポンド + 2 ポンド + 3 ポンド + 4 ポンド (4 つの異なる配送タイプ) の費用がかかるが、すべての商品が 15 ポンドの費用がかかる 5 番目の配送タイプを共有している場合、ユーザーは次のようになります。 「組み合わせた」オプションのその単一のより高価なグループが提示されました。

以下は、個別/結合オプションの HTML の例です。

アイテムの利用可能な配信タイプは、ストアド プロシージャを使用してデータベースから取得され、タイプ ID とベンダー ID から作成された一意の識別子を持っているため、タイプ間の同等性を簡単に比較できます。ただし、比較を行ってグループを生成するための効率的なアルゴリズムを思いつくことはできないようです。

データ構造に関して私が望んでいる最終結果は（疑似コード）です：

Basket { List<Item> Items }
=>
GroupsTable {
    List<SelectableDeliveryType> Columns,
    List<Group { List<Item> }> Rows
}

それぞれItemに独自のものが含まれており、ラジオボタンを配置する列をList<AvailableDeliveryType>簡単に決定するために使用できます。SelectableDeliveryType

これをカバーする一般的なアルゴリズムの概念への考え、ポインター（たとえば、セットカバーの問題ではないと思います）などは大歓迎です。

4

1 に答える 1

3

この問題は、グラフ彩色からの削減によりNP困難です。エッジで接続されたノードのセットで構成されるグラフの場合、そのグラフのk-coloringは、接続された2つのノードが同じ色にならないようにグラフの各ノードに色を付ける方法です。色数の問題は次のとおりです-グラフに色を付けることができる最小の色数はいくつですか？

次のように、NP困難である色数問題のインスタンスを問題に減らすことができます。ノードごとに、新しい製品を作成します。エッジごとに、これら2つの製品を同じクラスターにグループ化できないことをマークします。次に、これらの製品のクラスタリングは色付けに対応します。各クラスター内のすべてのノードを同じ色に着色するだけです。したがって、問題を最適に解くことはグラフ彩色を解くことと同等であり、したがって（ P≠NPと仮定して）多項式時間アルゴリズムはありません。

残念ながら、グラフ彩色は概算するのが非常に難しいことが知られています。最適の定数係数内、または任意のε>0に対してn1 -εの係数内にさえ入ることができる既知の多項式時間アルゴリズムはありません。Chaitinのアルゴリズムのようなヒューリスティックを使用するか、この問題についての別の考え方。

否定的な結果で申し訳ありませんが、うまくいけばこれが役立つでしょう！

于 2012-07-10T21:24:52.217 に答える