問題タブ [set-cover]

セットカバー問題を「解決」するのにどれくらいの時間がかかるかをテストするために、このプログラムを書きました。

これは貪欲な次善のソリューションですが、それでも実行に 147 秒かかりました。ただし、このソリューションは最適にかなり近いはずなので、私の目的には十分であると思います。どうすれば高速化できますか？

良いことよりも悪いことの方が多いので、いくつかの行をコメントアウトしました。編集：宇宙の計算は、実際にはタイミングから離れるべきではありません...それは事前に知ることができます。

私には次のシナリオがあります（長さについての予備的な謝罪ですが、できるだけ説明的にしたかったです）：

特定のタスクを完了するために、提示された順序で実行する必要のある「レシピ」（Ri）のリストが表示されます。各レシピは、それを完了するために必要なパーツ（Pj）のリストで構成されています。レシピには通常、最大3つまたは4つのパーツが必要ですが、最大16のパーツが必要になる場合があります。レシピリストの例は次のようになります。

• R1 = {P1}
• R2 = {P4}
• R3 = {P2、P3、P4}
• R4 = {P1、P4}
• R5 = {P1、P2、P2}//特定のパーツが複数必要になる場合があることに注意してください。（ここ、P2）
• R6 = {P2、P3}
• R7 = {P3、P3}
• R8 ={P1}//レシピがリスト内で繰り返される場合があることに注意してください。（R1と同じ）

最長のリストは数百のレシピで構成されている場合がありますが、通常、一部のレシピの繰り返しが多数含まれているため、同一のレシピを削除すると、通常、リストは50未満の一意のレシピになります。

私はマシンのバンク（Mk）を持っており、それぞれが利用可能なタイプのパーツの一部（またはすべて）を生成するように事前にプログラムされています（これはリスト処理が開始される前に1回行われます）。

フルフィルメントプロセスの反復は、次のように発生します。

• リスト内の次のレシピは、マシンのバンクに提示されます。
• 各マシンで、このレシピに必要なパーツの1つを作成するために、使用可能なプログラムの1つが選択されます。このレシピに必要ない場合は、「オフライン」に設定されます。
• 「クランク」が回され、各マシン（「オフライン」になっていない）が1つのパーツを吐き出します。
• クランクを1回転させることでできた部品を組み合わせることで、レシピが完成します。順序は関係ありません。たとえば、レシピ{P1、P2、P3}を実行することは、レシピ{P1、P3、P2}を実行することと同じです。

機械は瞬時に並行して稼働し、原材料は無制限であるため、リソースや時間/スケジュールの制約はありません。マシンバンクのサイズkは、少なくとも最長のレシピの要素数と等しくなければならず、したがって、上記のレシピの長さとほぼ同じ範囲（通常は3〜4、場合によっては最大16）になります。したがって、上記の例では、k = 3（R3とR5のサイズによって決定される）が妥当な選択のようです。

当面の問題は、銀行が特定のリストのすべてのレシピを実行できるように、マシンを事前にプログラムする方法です。マシンバンクはメモリの共通プールを共有するため、合計メモリ負荷の量を最小限に抑えるために、マシン間の冗長性を（完全に、または可能な限り）排除するプログラミング構成を生成するアルゴリズムを探しています。マシンバンクのサイズkは柔軟性があります。つまり、特定のリスト内の最長レシピの長さを超えてマシンの数を増やすと、リストのより最適なソリューションが生成される場合（ただし、16のハード制限を維持する場合）は問題ありません。

今のところ、これは単一コストの問題であると考えています。つまり、各プログラムは同じ量のメモリを必要としますが、将来的にはプログラムごとの均等化を柔軟に追加したいと考えています。上記の例では、すべてのレシピを考慮すると、P1は最大1回、P2は最大2回（R5）、P3は最大2回（R7）、P4は最大1回発生するため、理想的にはこれに一致する構成-P1を生成するように構成された1台のマシン、P2を生成するように構成された2台のマシン、P3を生成するように構成された2台のマシン、およびP4を生成するように構成された1台のマシンのみ。マシンバンクサイズk=3を使用した、上記の例で考えられる最小構成の1つは、次のとおりです。

• M1は、P1またはP3のいずれかを生成するようにプログラムされています
• M2は、P2またはP3のいずれかを生成するようにプログラムされています
• M3は、P2またはP4のいずれかを生成するようにプログラムされています

ここにはジョブショップタイプの制約がないので、私の直感では、これは集合被覆問題に還元されるはずだと教えてくれます。これは、デジタルシステムの設計で見られる最小限の集合被覆問題のようなものです。しかし、これらのアルゴリズムに関する私の（確かに限られた）知識をこのシナリオに適応させることはできないようです。誰かがこのアプローチの実現可能性を確認または否定できますか？どちらの場合でも、いくつかの有用なアルゴリズムに私を向けることができますか？BerkeleyのEspressoのように事前にパッケージ化されたものではなく、既存のコードのチャンクに統合できるものを探しています。

ありがとう！

要素のユニバースU={1、2、3、...、n}と、このユニバース内のセットの数{S1、S2、...、Sm}が与えられた場合、作成できる最小のセットはどれですか。 mセットのそれぞれで少なくとも1つの要素をカバーしますか？

たとえば、次の要素U={1,2,3,4}およびセットS={{4,3,1}、{3,1}、{4}}の場合、次のセットは少なくとも1つをカバーします。各セットの要素：{1,4}または{3,4}なので、ここで必要な最小サイズのセットは2です。

これをスケールアップしてm=100またはm=1000セットの問題を解決する方法について何か考えはありますか？または、これをRまたはC ++でコーディングする方法について考えますか？

Rを使用した上からのサンプルデータlibrary(sets)。

乾杯

私は集合I={P1、P2、...、Pm}を持ち、次のようにR1、R2、...、Rnで表されるIのn個の有限部分集合を持っています。

R1 = {P1、P2}

R2 = {P2、P4}

R3 = {P2、P3、P4}

R4 = {P1、P2、P4}

...。

ここで、円周率は整数を示します。

Riごとに、そのすべての要素の積を計算したいと思います。私の目的は、Ri（i = 1,2、...、n）間でいくつかの共通部分を共有することにより、乗算と除算をできるだけ少なくすることです。

たとえば、最初にP2 * P4を計算できる場合、この結果はR3とR4のすべての要素の積を計算する際に使用できます。

除算も許可されていることに注意してください。たとえば、最初にA = P1 * P2 * P3 * P4を計算し、次にA / P1を使用してR3のすべての要素の積を計算し、R4にA/P3を使用できます。

最小の乗算と除算を使用して、Iのすべてのサブセットのすべての積を計算したい場合、それは集合被覆問題ですか？NP完全？ところで、ここのようにそれを記述するために整数線形計画法の定式化を与えることができますか？

どんな提案でも大歓迎です！

コミュニティ編集：追加の仮定：

• 乗算と同じコストで、除算が許可されます
• 特定のセットに繰り返される要素はありません。例：R5 = {P1, P1, P1, P2}許可されていません

私は最近、セット カバーの問題のフォークと思われる問題に取り組んでいます。ただし、私の問題のセット数は 2^n にもなります。そして、私が見つけたおおよそのアルゴリズムは、セットがあまり多くない場合にのみ効果があるようです. 2^n集合に合うアルゴリズムってあるのかな？

ご回答ありがとうございます!!!

欲張りアルゴリズムを使用して、集合被覆問題の解決策を実装しようとしています。

そのための古典的な欲張り近似アルゴリズムは

私は2つの部分で質問があります：

a。アルゴリズムを逆に実行することは有効なアルゴリズムになりますか？

b。問題の性質は、Cを取得するのが簡単で、冗長なセットの数が限られている（<5）というものです。この場合、この削除アルゴリズムのパフォーマンスは向上しますか？

Googleの公開されているngramデータから導き出された、最も頻繁に使用される単語のリストがあります。

私は持っています：

6800頻繁な2グラム4800頻繁な3グラム2500頻繁な4グラム1100頻繁な5グラム

例2ngramは、次のようになります。

「犬」「本」「椅子3脚」など

例5ngramは、「ある時はそこにあった」「ある時はあった」「それは暗かった」などのようになります。

よく使う単語のリストも2,000語あります。

1）さまざまなリストの中で最も少ない数のngramのどの組み合わせに、頻繁な単語のリストからの最も多くの単語が含まれているかを調べたい。

たとえば、200個の2グラム、40個の3グラム、50個の4グラム、および20個の5グラムで、1800個の頻繁な単語を使用していることがわかった場合、それは成功です。私はそれらの比率を上げましたが、単語の大部分を使用する500未満の組み合わせを見つけたいと思います。

2）また、リストから単語の総数が最も多いさまざまなngramの組み合わせの最小数を見つけたいと思います。

たとえば、2000を超える異なる単語を使用する500 ngramを見つけることができれば、それは素晴らしいことです。

私が抱えている問題は、これをどうやってやるのかわからないということです。hadoopとmapreduceは正しい方向に進んでいると思います...しかし、助けていただければ幸いです。

次のような最小集合被覆問題を解きたいと思います。すべてのリストには 1 と 0 のみが含まれます。

正確に記号 を挿入して作成できる場合、リストはリストAをカバーすると言います。BBAx

lengthnと setの 1 と 0 のすべての 2^n リストを考えますx = n/3。2n/3それらすべてをカバーする 長さのリストの最小セットを計算します。

これが私が始めた素朴なアプローチです。長さのすべての可能なリストに対して、2n/3この関数 (DSM によって作成された) を使用して作成できるすべてのリストのセットを作成します。

n = 6次に、例として使用して、次のようにセットのセットを作成します。

結合が であるカバーセットからセットの最小セットを見つけたいと思いますallset = set(product([0,1], repeat=n))。

この場合、set(all_fill([1,1,1,1],2)), set(all_fill([0,0,0,0],2)), set(all_fill([1,1,0,0],2)), set(all_fill([0,0,1,1],2))行います。

私の目的は の問題を解決することですn = 12。外部ライブラリが役立つ場合は喜んで使用しますn。最悪の場合、時間が指数関数的になると予想しています。

たとえば、集合カバー決定問題は NP 完全問題として知られています。この問題の入力は、ユニバース U、U のサブセットのファミリ S、および整数 k () です。

私が混乱していることの 1 つは、k=1 とすると、S の各要素をチェックするだけで、明らかに時間 |S| で問題を解決できるということです。より一般的には、k が定数の場合、問題は次のようになります。 |S| の多項式時間で解かれます。このように、|S|/2、|S|/3... のように、k も |S| とともに増加する場合にのみ、時間計算量は指数関数的に高くなります。

だからここに私の質問があります：

1. 私の現在の理解では、NP 完全問題の時間計算量の測定は、最悪のケースで測定されます。理解が正しいかどうか誰か教えてください。

2. 私は誰かが別の問題が NP 困難であることを証明するのを見ました<U,S,|U|/3>。なぜ彼は??<U,S,|U|/3>ではなく、だけを証明したのだろうと思っています。<U,S,ARBITRARY k>そのような証拠は信頼できますか？

どうもありがとう！