アルゴリズム：サブセットを強制するために、セットからできるだけ少ない要素を削除する

Question

私は解決する方法がわからない問題を抱えています：

一連のセットがあります 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}, 、それはの1つのスーパーセットではありません A_i).

削除する（最小数の）要素を決定するためのアルゴリズムはありますか？

Answer 1

最小限を削除したいように聞こえます ヒットセット の A から B （これは頂点カバーの問題に密接に関連しています）。

いくつかのセットのヒットセット A それ自体は、各セットから少なくとも1つの要素を含むようにセットです A （各セットを「ヒット」します）。最小限の打撃セットは、そのような最小のヒットセットです。したがって、セットのMHSがある場合 A, 、各セットの要素があります A. 。これを削除します B 設定されていないことを意味します A のサブセットにすることができます B.

あなたがする必要があるのは、MHSを計算することだけです（₁, 、a₂, 、... a_n）、それからそれを削除します B. 。残念ながら、MHSを見つけることはNP完全な問題です。ただし、いくつかのオプションがあります。

1. データセットが小さい場合は、明らかなブルートフォースソリューションを実行します
2. 確率的アルゴリズムを使用して、高速でおおよその回答を取得します（参照 このPDF)
3. 遠く、反対方向に走ります

Answer 2

近似が必要な場合は、Aの最小のセットから始めて、Bから1つの要素を削除します（ランダムに1つをつかむか、どの要素がAのほとんどのセットにあるかを確認することができます。必要な速さ）

これで、Aの最小のセットはBのサブセットではありませんが、そこから移動しますが、最初に確認しているかどうかを確認して、この時点でサブセットであるかどうかを確認します。

これは、頂点をカバーする頂点を思い出させ、これに似た近似アルゴリズムを覚えています。

Answer 3

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