問題タブ [set-theory]

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

与えられた:

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ハードですか？そうでない場合、どうすればこれを見つけることができますか?

私はdjangoに2つのモデルを持っていますが、それらをどのように書くか(抽象モデルと継承など...または2つの異なるモデルを持つかどうか)はわかりませんが、一般的に2つのタイプのオブジェクトAとBがあります.

A と B は単なるアイテムなのでまったく同じです。どちらも次の属性を持っています。

名前、価格

ここで、A と B のすべての類似のアイテムを比較し (類似のアイテムは同じ名前のアイテムです)、それらの間の価格の違いを確認したいと思います (注: 重複はないと仮定しますが、交差点には存在しない可能性のあるアイテムが含まれていると仮定します)。 A または B またはその両方。つまり、A と B は同一のデータ セットではないため、A には 20 個の項目があり、B には 643 個の項目がある可能性があります)

モデルなどを使用してDjangoでこれを行うにはどうすればよいですか...

次のようなモデルがあります。

2 つのデータ ソースがあるので、ベンダー A からアイテムを取得し、ベンダー B からアイテムを取得します。

場合によっては、ベンダー A がベンダー B と同じアイテムを持っていないことがあります。たとえば、ベンダー A が 30 個のアイテムを持っていて、ベンダー B が 442 個のアイテムを持っていて、そのうち 6 個のアイテムだけが共通しているとします。共通のアイテムは、まったく同じ名前を持つアイテムとして定義されます。

また、ベンダー a とベンダー b のアイテムに共通するアイテム、つまり、ベンダー a とベンダー b で同じ名前を持つアイテムの価格の違いを見つける必要があります。私は大きなノーを持っています。ベンダーごとに最大 10,000 個のアイテムになる可能性があるので、これを行う効率的な方法が必要ですか?

私は下のテーブルを持っています

列 X と Y は文字列を保持します。例として数値を指定しました。

以下のように、このテーブルからの出力が必要です

つまり、テーブルからの一意のセット。行 1 (1,2) と行 3 (2,1) のうち、必要なセットは 1 つだけです。これは、私のセットでは (1,2)=(2,1) であるためです。同様に (1,3)=(3,1) です。したがって、このテーブルの一意のセットは (1,2) (1,3) と (3,5) です。

以下の SQL を試しました。ROWID で「>」または「<」を使用できるかどうかわからないため、より良い方法があれば教えてください。

タイトルが間違っていたり、わかりにくかったらすみません。

私は2つのソースファイルで作業しています（csvファイルをExcelに変換するか、別のOracleテーブルにロードすると考えてください）。2 つのファイルのデータは、ビジネスの観点から関連付けられています。

ファイル 1 には、一連の行と列が含まれています。例えば：

ファイル 2 には同様のデータが含まれていますが、未知の方法で集約されています。

明らかに、私はそれをかなり単純化しすぎました。

私が探しているのは、ファイル 1 の行がファイル 2 の行にどのように関連しているかを判断する方法です。

この場合、考えられる結果は次のとおりです。

...等々...

除外される (まったく使用されない) 行がある場合があります。2x 使用される行がある可能性があります。おそらく 1 つの関連付けがあるかもしれませんし、2 つまたは 3 つの関連付けがあるかもしれません。残念ながら、データ ファイルはあまり明確に定義されていません (ここで古いメインフレーム システムについて話します)。

明らかに、自分で調べて手動で理解しようとすることはできますが、行き止まりで時間を無駄にするだけの膨大な数の組み合わせを試すことになります。入力を受け取り、それらがどのように関連しているかを確認できるシステムがあれば素晴らしいことです。すべての可能な解決策は、事後に自分で手動で分析して、それが理にかなっており、すべてのデータセットで機能することを確認する必要があることを認識しています.

私が探しているものが可能かどうか、または私の問題を説明する正しい用語についてアドバイスをいただければ幸いです。

可能性のある解決策がクエリ形式であるか、機能を提供する既存のアプリケーション/プログラム/Web サイトであっても問題ありません。

ありがとう！

次の質問を検討してください。

とL1をL22 つの言語にします。以下の re 言語のクラスの閉鎖性を証明または反証する

1. 違い(L1 - L2)

2. 積(積の語尾が不明な場合と同様に、どこで終わる(L1 x L2) かがわかっているという仮定の下で、積を証明してみてください。L1

ここで、閉鎖性とは、L1およびL2がツーリング マシンによって受け入れられる場合、(L1 - L2)または(L1 x L2)

ノート

結合と補完 (結合: 閉じている; 補完: 閉じていない) の解決策を見つけることはできますが、上記 (違いまたは製品) の解決策はわかりません。