Вариация на задаче покрытия множества в 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 (для точной версии).