6

要素のユニバース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)。

s1 <- set(4, 3, 1)
s2 <- set(3, 1)
s3 <- set(4)
s <- set(s1, s2, s3)

乾杯

4

4 に答える 4

7

これが打撃集合問題であり、基本的に要素と集合の役割が入れ替わった集合被覆問題です。A = {4、3、1}およびB = {3、1}およびC = {4}とすると、要素セットの包含関係は次のようになります。

  A B C
1 + + -
2 - - -
3 + + -
4 + - +

したがって、基本的に、{A、B、C}をセット1 = {A、B}および2={}および3={A、B}および4 = {A、C}でカバーする問題を解決する必要があります。

おそらく、集合被覆の重要なインスタンスを実際に解決する最も簡単な方法は、RまたはC++へのインターフェイスを備えた整数計画パッケージを見つけることです。あなたの例は、LP形式の次の整数プログラムとしてレンダリングされます。

Minimize
    obj: x1 + x2 + x3 + x4
Subject To
    A: x1 + x3 + x4 >= 1
    B: x1 + x3 >= 1
    C: x4 >= 1
Binary
    x1 x2 x3 x4
End
于 2011-07-19T22:46:09.633 に答える
2

最初、私は問題の複雑さを誤解し、m セットをカバーするセットを見つける関数を思いつきましたが、それが必ずしも最小のものではないことに気付きました。

cover <- function(sets, elements = NULL) {
  if (is.null(elements)) {
    # Build the union of all sets
    su <- integer() 
    for(si in sets) su <- union(su, si)
  } else {
    su <- elements
  }

  s <- su
  for(i in seq_along(s)) {
    # create set candidate with one element removed
    sc <- s[-i] 

    ok <- TRUE
    for(si in sets) {
      if (!any(match(si, sc, nomatch=0L))) {
        ok <- FALSE
        break
      }
    }

    if (ok) {
      s <- sc
    }
  }

  # The resulting set
  s
}

sets <- list(s1=c(1,3,4), s2=c(1,3), s3=c(4))
> cover(sets) # [1] 3 4

次に、時間を計ります。

n <- 100  # number of elements
m <- 1000 # number of sets
sets <- lapply(seq_len(m), function(i) sample.int(n, runif(1, 1, n)))
system.time( s <- cover(sets) ) # 0.53 seconds

それほど悪くはありませんが、それでも最小のものではありません。

明らかな解決策: 要素のすべての順列を生成し、それをカバー関数に渡し、最小の結果を保持します。これは「永遠」に近いでしょう。

もう 1 つのアプローチは、限られた数のランダム順列を生成することです。このようにして、最小セットの近似値を取得します。

ns <- 10 # number of samples
elements <- seq_len(n)
smin <- sets
for(i in seq_len(ns)) {
   s <- cover(sets, sample(elements))
   if (length(s) < length(smin)) {
     smin <- s
   }
}
length(smin) # approximate smallest length
于 2011-07-20T15:17:37.037 に答える
1

各セットが 2 つの要素を持つように制限すると、np-complete 問題ノード カバーが得られます。より一般的な問題も完全な NP になると思います (正確なバージョンの場合)。

于 2011-07-19T16:51:33.477 に答える
1

(効率的/実行可能なアルゴリズムではなく) アルゴリズムにのみ関心がある場合は、増加するカーディナリティの宇宙のサブセットを生成し、S のすべてのセットとの交差が空でないことを確認できます。機能するものを手に入れたらすぐにやめてください。カーディナリティは可能な限り最小です。

これの複雑さは 2^|U| です。最悪の場合だと思います。Foo Bahの答えを考えると、多項式時間の答えが得られるとは思いません...

于 2011-07-19T16:53:44.613 に答える