Wariacja na temat problemu z ustawioną pokrywą w R/C++

Question

Biorąc pod uwagę wszechświat elementów U = {1, 2, 3, ..., n} i pewną liczbę zestawów w tym Wszechświecie {S1, S2, ..., Sm }, jaki jest najmniejszy zestaw, który możemy utworzyć, który obejmie co najmniej jeden element w każdym z zestawów m?

Na przykład, biorąc pod uwagę następujące elementy U = {1,2,3,4} i zestawy S = {{4,3,1}, {3,1}, {4}}, następujące zestawy będą obejmuje co najmniej jeden element z każdej serii: {1,4} lub {3,4} więc minimalne wielkości zestaw wymaga tutaj to 2.

każdy myśli, jak to może być zwiększana, aby rozwiązać problem dla m = 100 lub m = 1000 zestawów? Albo myśli, jak to zakodować w R lub C++?

Przykładowe dane, z góry, przy użyciu R library(sets).

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

Cheers

Answer 1

Jeśli ograniczysz każdego zestawu mieć 2 elementy, trzeba pokrywę węzła problemem NP-zupełny. Sądzę, że bardziej ogólnym problemem byłby również NP complete (dla dokładnej wersji).

Answer 2

Jeśli interesuje Cię algorytm (a nie efektywny/wykonalny algorytm), możesz po prostu wygenerować podzbiory wszechświata o rosnącej liczności i sprawdzić, czy przecięcie ze wszystkimi zestawami w S nie jest puste. Zatrzymaj się, gdy tylko uzyskasz taką, która działa; liczebność jest minimalna możliwa.

Złożoność tego jest 2^| U | w najgorszym przypadku, myślę. Biorąc pod uwagę odpowiedź Foo Bah, nie sądzę, że dostaniesz odpowiedź wielomianową ...

Answer 3

Jest to hitting set problem, która jest w zasadzie ustawiona na okładkę z rolami elementów i zestawów zamienionych. Pozwalając = {4, 3, 1}, B = {3, 1}, a C = {4}, element zestawu powstrzymywanie związek jest

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

więc zasadniczo Aby rozwiązać ten problem pokrywania { A, B, C} z zestawami 1 = {A, B} i 2 = {} i 3 = {A, B} i 4 = {A, C}.

Prawdopodobnie najłatwiejszym sposobem na rozwiązanie nietrywialnych instancji zestawu osłon w praktyce jest znalezienie pakietu programowania liczb całkowitych z interfejsem do R lub C++. Twój przykład będzie renderowany jako następujący program liczbowy w formacie 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 4

Początkowo źle złożoność problemu i podszedł z funkcji, która znajdzie się zestaw, który obejmuje zestawy M - ale potem zrozumiał, że niekoniecznie jest to najmniejszy:

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 

Wtedy możemy limit czasu go:

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 

nie jest tak źle, ale nadal nie najmniejszy.

Oczywistym rozwiązaniem: wygenerowanie wszystkich permutacji elementów i przekazanie jest funkcja okładki i zachowanie najmniejszego wyniku. To zbliży się do "na zawsze".

Innym podejściem jest generowanie ograniczonej liczby losowych permutacji - w ten sposób uzyskuje się przybliżenie najmniejszego zestawu.

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