6

解決方法がわからない問題が発生しました：

セットのセットがあり、セットがありA = {A_1, A_2, ..., A_n}ますB。

B現在の目標は、 (作成中の)から可能な限り少ない要素を削除することです。これB'により、すべての の要素を削除した後1 <= i <= n、はのサブセットでA_iはなくB'なります。

たとえば、 と がある場合、A_1 = {1,2}, A_2 = {1,3,4}, A_3={2,5}たとえばB={1,2,3,4,5}から 1 と 2 を削除できます (これにより、 のいずれかのスーパーセットではないBが生成されます)。B'={3,4,5}A_i

削除する (最小数の) 要素を決定するアルゴリズムはありますか?

4

3 に答える 3

8

fromの最小ヒット セットを削除したいようです(これは、頂点カバーの問題と密接に関連しています)。AB

一部のセットのセットのヒット セットAは、それ自体がセット内の各セットから少なくとも 1 つの要素を含むようなセットですA(各セットに「ヒット」します)。最小ヒッティング セットは、最小のヒッティング セットです。したがって、set-of-sets の MHS がある場合A、各セットの要素が にありますA。これを から削除Bすると、 のセットをAのサブセットにすることはできませんB。

必要なのは、(A 1、A 2、... A n ) の MHS を計算し、それを から削除することだけですB。残念ながら、MHS を見つけることは NP 完全問題です。ただし、いくつかのオプションがあります。

  1. データセットが小さい場合は、明らかなブルートフォースソリューションを実行してください
  2. 確率的アルゴリズムを使用して、高速でおおよその答えを得る (この PDFを参照)
  3. 遠く離れて逆方向に走って
于 2010-05-19T12:10:56.920 に答える
0

これらのセットから最小の長さを見つけて、このセットにあるこれらの要素を削除する必要があると思います。

于 2010-05-19T19:22:54.387 に答える
0

概算が必要なだけの場合は、A の最小セットから始めて、B から 1 つの要素を削除します。必要な速さ）

ここで、A の最小のセットは B のサブセットではありません。そこから先に進みますが、最初に、調べているセットがこの時点でサブセットであるかどうかを確認してください。

これは頂点被覆問題を思い起こさせ、これに似た近似アルゴリズムをいくつか覚えています。

于 2010-05-19T23:49:26.163 に答える