Вариация на проблему покрытия множества в R / C ++

Question

Учитывая вселенную элементов U = {1, 2, 3, ..., n} и количество множеств в этой вселенной {S1, S2, ..., Sm}, какое наименьшее множество мы можем создать, что будет охватывать хотя бы один элемент в каждом из m наборов?

Например, учитывая следующие элементы U = {1,2,3,4} и наборы S = {{4,3,1}, {3,1}, {4}}, следующие наборы будут охватывать хотя бы один элемент из каждого набора: {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)

Приветствия

Answer 1

Это задача о наборе ударов , которая, в основном, ставится на прикрытие ролями элементов и взаимозаменяемыми наборами. Если 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

Answer 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

Не так уж плохо, но все же не самое маленькое.

Очевидное решение: генерировать все перестановки элементов и передавать их функции покрытия и сохранять наименьший результат.Это займет около «навсегда».

Другой подход заключается в создании ограниченного числа случайных перестановок - таким образом вы получите аппроксимацию наименьшего набора.

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 

Answer 3

Если вас просто интересует алгоритм (а не эффективный / выполнимый алгоритм), вы можете просто сгенерировать подмножества юниверса с возрастающей мощностью и проверить, что пересечение со всеми наборами в S не пусто.Остановитесь, как только вы получите тот, который работает;количество элементов является минимально возможным.

Сложность этого равна 2 ^ | U |в худшем случае, я думаю.Учитывая ответ Фу Баха, я не думаю, что вы получите ответ за полиномиальное время ...

Answer 4

Если вы ограничите каждый набор двумя элементами, у вас будет покрытие проблемного узла np-complete. Я предполагаю, что более общая проблема также была бы завершена NP (для точной версии).