問題タブ [set-cover]

可能なセットの組み合わせをすべて作り、それが最小解であるかどうかを検証することで、セットカバー問題を解くことができます。現在、「n」がセットの数である場合、最大 2^n のセットの組み合わせを持つことができます。

したがって、このアプローチの複雑さは O(2^n) になるはずです。ただし、ウィキペディアには、「セット カバー問題の複雑さは m^n であり、m は宇宙のサイズであり、n はコレクション内のセットの数です」と記載されています。

複雑さが O(m^n) であり、O(2^n) ではないことを誰かが説明できますか?

前もって感謝します。

セットカバー問題は、次の要素で構成されています。

与えられた:

1. アイテムUのセット。

2. それぞれが U からのアイテムを含むセット S のセット。

次のような集合 C の集合を見つけます。

1. C は S のサブセットです。
2. C のセットには、U のすべての項目が含まれます (少なくとも 1 回)。

オプションで、最小Cを見つけることができます。つまり、|C| はできるだけ小さいです。

カバー問題を設定するための Wiki リンク

SCP は NP 完全であり、MSCP (または最適な SCP) は NP 困難であり、それを見つけるために多くの手法 (貪欲アルゴリズム、遺伝的アルゴリズム、人工ニューラル ネットワーク) のいずれかを使用できることを理解しています。

ただし、C のサイズ (つまり |C|) を見つけることも NP 困難であるかどうかを尋ねたいと思います。

例を示すには:

|C|を見つけたい 問題を解決せずに。これはNPハードですか？そうでない場合、どうすればこれを見つけることができますか?

この問題はグリーディ セット カバーの問題と完全に同じではありませんが、同じ考えを共有しています。

df2 のキーのセットで構成される 1 つの列 df['s'] を持つ Pandas データフレーム df1 があるとします。

上記のデータフレーム df2 には、重複したキーを含めることができます。私たちは最後のものを選びます。たとえば、上記のキー「3」に対して値「1.0」を選択します。

対応するキーの値の合計を最大にすることができる df['s'] の上位 6 行を見つけ、新しいデータフレームの行を値の寄与度で並べ替えたいと考えています。これを行う最速の方法は何ですか?

上記のデータセットの場合、結果データフレームの最初の 2 行は次のようになります。

上の 2 番目は set([16]) ではありません。set([1,16]) には既に "16" が含まれており、set([16]) からの加算値は 0 であるためです。

セットのキーの対応する値の合計によってソートされます。

アップデート：

この問題を簡単にするために、df2 に一意のキーのみが含まれていると考えてみましょう。アンドリューのトリックに基づいて簡単に修正できます。

私は文字列のセットを持っています

[ abcd, efgh, abefg]

すべての文字をカバーする文字列の最小数を見つける方法 ( abcdefgh)

答えはabcdとefghです。しかし、この答えを見つけるためのアルゴリズムは何でしょうか?

私はMatlabを使用してコードに取り組んでおり、参照リストのすべての要素をカバーするために必要な最小数のリスト(特定のリストのセット)を見つける必要があります。

たとえば、私の参照リストが

そして、次のような一連のリストがあります。

のすべての要素をカバーするために必要なリストの最小数Xは2(BとC) ですが、最初に最も多くの要素 ( A) をカバーするリストのみを検索し、残りの要素をカバーする他のリストを見つけようとすると、少なくとも3リストを使用することになります。これに必要な最小数のリストを検索できるコードを作成する最良の方法は何でしょうか (これにより、Bandの出力が得られますC)。どんな助けでも大歓迎です...この問題への最善のアプローチ方法の概念的な説明(実際のコードではない)だけでも、大きな助けになります!

Rのセットカバー問題の近似を解決または実装しようとしています。このようなデータフレームが与えられます。

列内の一意の要素数は次のnとおりです。

setsn (宇宙) のすべての一意の要素をカバーする少数のセット (列 ) を計算したいと思います。この例では、s1 {1, 2, 3} と s4 {4, 5} の 2 つのセットがあります。ウィキペディアとインターネットでそれについて読んだことがありますが、貪欲なアルゴリズムを適用して近似値を見つけることができることを知っています。このような問題を解決するための 2 つのパッケージについて言及しているこのリンクも確認しましたが、開始方法さえわかりません。私の実際の例では、40,000 を超えるセットがあり、各セットには 1,000 から 10,000 の要素があり、80,000 の unviverse または一意の要素があります。LPsolveRsymphony

開始または続行する方法についてのヘルプまたはガイドは、非常に高く評価されます。

データ