Mamy:
zbiór A zawierający p elementów: A = {x 1, x 2, ..., x p}
N zbiorów B, z których każdy jest jakimś podzbiorem A różnym od A. Każdy zbiór jest inny.
Zbiór C, określony podzbiór A.
Zadanie: znaleźć dowolny najmniejszy zbiór D, składający się ze zbiorów B oraz opcjonalnie elementów C, taki że różnica symetryczna wszystkich zbiorów B będących elementami D wraz z wybranymi elementami C jest równa zbiorowi C, a jednocześnie |D| < |C|. Zbiór D może nie istnieć.
Przykład:
A = {1, 2, 3, 4, 5, 6, 7, 8}
B 1 = {3, 4, 6, 7}; B 2 = {4, 6, 7, 8}; B 3 = {1, 2, 3, 5}
C = {1, 2, 3, 4, 5, 6, 7}
|C| = 7
Rozwiązanie:
D = {B 1, B 3, 3}
|D| = 3
B 1 ^ B 3 = {1, 2, 4, 5, 6, 7}
{1, 2, 4, 5, 6, 7} ^ {3} = C
lub
D = {B 2, B 3, 8}
B 2 ^ B 3 = {1, 2, 3, 4, 5, 6, 7, 8}
{1, 2, 3, 4, 5, 6, 7, 8} ^ {8} = C
Jakim algorytmem to rozwiązać? Bruteforce - sprawdzanie najpierw wszystkich B, potem wszystkich par B, potem wszystkich trójek... oczywiście działa, ale jest bardzo wolne.