1

これは私のCSクラスの1つの問題セットで、ちょっと行き詰まっています。これが問題の要約です。

Create a program that will:
1) take a list of grocery stores and its available items and prices
2) take a list of required items that you need to buy
3) output a supermarket where you can get all your items with the cheapest price

input: supermarkets.list, [tomato, orange, turnip]
output: supermarket_1

The list looks something like
supermarket_1
$2.00 tomato
$3.00 orange
$4.00 tomato, orange, turnip

supermarket_2
$3.00 tomato
$2.00 orange
$3.00 turnip
$15.00 tomato, orange, turnip

If we want to buy tomato and orange, then the optimal solution would be buying 
from supermarket_1 $4.00. Note that it is possible for an item to be bough 
twice. So if wanted to buy 2 tomatoes, buying from supermarket_1 would be the 
optimal solution.

ここまでで、データセットを簡単に操作できるデータ構造に入れることができました。私は基本的にスーパーマーケットの辞書を持っており、値は各エントリからその価格へのマッピングを含む別の辞書を指します。

supermarket_1 --> [turnip --> $2.00]
                  [orange --> $1.50]

1 つの方法は、ブルート フォースを使用して、すべての組み合わせを取得し、解を満たすものを見つけて、最小のものを見つけることです。これまでのところ、これは私が思いつくことができるものです。2 つのアイテムの組み合わせの価格が、それぞれを個別に購入するよりも安くなるという仮定はありません。

提案のヒントは大歓迎です

4

3 に答える 3

2

特定のスーパーマーケットの最適解を見つけることは、セット カバー問題(NP 完全) の一般化です。削減は次のように行われます: セット カバー問題のインスタンスが与えられた場合、各組み合わせに 1 を割り当てるコスト関数を定義し、問題を解決するアルゴリズムを適用すると、セット カバー インスタンスの最適解が得られます。(したがって、最小価格を見つけることは、カバー セットの最小数を見つけることに対応します。) したがって、問題はNP 困難であり、多項式時間で実行される解を見つけることは期待できません。

あなたが言及したブルートフォース方式を本当に実装する必要があります。最初のステップとしてこれを行うことをお勧めします。パフォーマンスが十分でない場合は、MIP フォーミュレーションと CPLEX などのソルバーを使用して試すか、ヒューリスティックなアプローチを開発する必要があります。

単一のスーパーマーケットの場合、混合整数計画法 (MIP)を見つけるのはかなり簡単です。x_i製品の組み合わせiがソリューションに含まれる頻度、c_iそのコスト、および製品の組み合わせにw_ij製品が含まれる頻度の整数を とします。次に、最小化していますji


sum_i x_i * c_i

のような条件に応じて


sum_i x_i * w_ij >= r_j,

r_j製品jが必要な頻度の数字はどこにありますか。

于 2012-04-20T05:32:16.703 に答える
1

さて、あなたは 1 つのメソッドを持っているので、今それを実装して、送信するために機能するものを用意します。ブルート フォース ソリューションのコードを作成するのに時間はかからないはずです。その後、パフォーマンス データを取得し、問題についてより深く考えることができます。大都市の合理的なショッピング範囲にあるスーパーマーケットの数を推測します。多くのスーパーマーケット レコードを作成し、それらをランダムな価格の製品テーブルにリンクします (これは解決策よりも手間がかかります)。

ブルートフォース ソリューションを実行します。それは機能しますか？解決策が出力された場合は、「手動で」価格を合計し、ランダムに取得された他の 3 つの「スーパーマーケット」レコードに対してそれらを一覧表示して (数字を選択するだけです)、合計が以下であることを示します。リストのアイテムの価格を変更して、ソリューションが安くならないようにし、再実行して、別のソリューションを取得します。

それ以上の作業が正当化されないほど高速ですか? もしそうなら、あなたのレポートの結論セクションでそう言って、あなたの教授/TAにロットを投稿してください. タスクを理解し、それについて考え、解決策を考え出し、それを実装し、代表的なデータセットでテストし、機能が実証可能であり、パフォーマンスが適切であることを示しました - あなたの課題は終わり、バーに行き、次のことを考えますビールを飲みながら。

于 2012-04-19T08:15:13.757 に答える
0

「ブルートフォース」ソリューションの意味がわかりません。各スーパーマーケットの商品リストのコストを計算して、最小値を選択してみませんか？複雑さはO（#items x #supermarkets）にあります。これは良いことです。

データ構造に関しては、単純にマトリックス（2次元配列）price [super] [item]を設定し、スーパーマーケット/アイテムのIDを使用することもできます。

于 2012-04-19T10:32:06.740 に答える