Zestaw uproszczeń

Question

Powiedz, że mam dwa zestawy: set1 = {a,b,c,d,e,f} i set2 = {a,b,c,d,e,g}. Zamiast wyrażanie ich wyraźnie, chcę stworzyć coś jak

common = {a,b,c,d,e} 
set1 = common + f 
set2 = common + g 

Gdybyśmy chcieli reprezentować {a,b,c,h}, możemy reprezentować go jako common - d - e + h.

Moim celem jest generowanie optymalnej wspólnej porcji. Mając tylko jedną wspólną sekcję, nie jest to zbyt trudne, ale muszę pozwolić na więcej niż jedną (ale nie nieograniczoną, lub korzyści uzyskane byłyby trywialne).

Optymalnie, mam na myśli "najmniejszą liczbę wyrażonych elementów". Tak więc w powyższym przykładzie "kosztuje" 5 (liczba elementów), aby utworzyć zmienną common. Następnie ustawia 1 i 2 zarówno koszt 2 (jeden do odniesienia wspólnego, jeden do dodania dodatkowego elementu), w sumie 7. Bez podstawienia kosztowałoby to 12 do przechowywania (po 6 elementów). Podobnie, odejmując element z wymienionej będzie „kosztu” 1.

Innym przykładem {a,b,c,d}, {a,c,d,e}, {e,f,g,h} and {e,f}

może być

common1 = {a,c,d} 
common2 = {e,f,g} 
set1 = common1 + b 
set2 = common1 + e 
set3 = common2 + h 
set4 = common2 - g 

umożliwiając wielu wspólnych części tego staje się o wiele trudniejsza. Czy istnieje nazwa tego typu problemu lub coś podobnego? Wygląda na to, że może to być związane z kompresją, ale nie byłem w stanie znaleźć zbyt wielu informacji na temat tego, od czego zacząć.

Niektóre inne szczegóły, które mogą być dowiemy się z:

• pozwolono odwołać wiele wspólnych części reprezentować jeden zestaw może być ważne, ale nie jest wymagane.
• Dla mojego przypadku użycia, zestawy będą zwykle około 20 elementów i około 10 różnych zestawów.

Answer 1

Można znaleźć wszystkie zestawy atomowe, czyli wszystkie zestawy, które nigdy nie są widziane oddzielnie.

{a,b,c,d,e,f,g,h}  | {a,b,c,d} = {a,b,c,d},{e,f,g,h} 
{a,b,c,d},{e,f,g,h}  | {a,c,d,e} = {a,b,c,d},{e,f,g,h} 
{a,c,d},{b},{e},{f,g,h} | {e,f,g,h} = {a,c,d},{b},{e},{f,g,h} 
{a,c,d},{b},{e},{f,g,h} | {e,f}  = {a,c,d},{b},{e},{f},{g,h} 

{a,b,c,d} = {a,c,d},{b} 
{a,c,d,e} = {a,c,d},{e} 
{e,f,g,h} = {e},{f},{g,h} 
{e,f}  = {e},{f} 

Jest to trochę bliżej, ale nie rozwiązuje minimalnej awarii.

Nie sądzę, że można znaleźć minimalny, ponieważ podejrzewam, że jest NP-Hard. Jeśli weźmiesz pod uwagę zestaw S i stworzysz wykres, w którym każdy możliwy podzbiór S jest węzłem G. Teraz podaj masę węzła zgodnie z długością podzbioru i narysuj krawędź między każdym węzłem odpowiadającym ilości zmian. {abc} -> {a} ma wagę 2. {bcd} -> {abe} ma wagę 4. Aby znaleźć minimalne rozwiązanie wspólnego problemu, musisz znaleźć drzewo o minimalnej wadze, które obejmuje każdy z zestawów, które Cię interesują. Jeśli okaże się, że możesz go użyć do zbudowania minimalnego wspólnego zestawu, to byłoby to ekwiwalentne. Znalezienie drzewa o minimalnej wadze na wykresie ważonym węzłem nazywa się Problemem drzewka Steinera ważonym węzłem. Węzeł drzewa Steinera z ważonym węzłem może być pokazany jako równoważny problemowi drzewa Steinera. Problem z drzewem Steinera może być pokazany jako NP-trudny. Tak więc mocno podejrzewam, że problem, który próbujesz rozwiązać, jest NP-trudny.

http://theory.cs.uni-bonn.de/info5/steinerkompendium/node15.html

http://theory.cs.uni-bonn.de/info5/steinerkompendium/node17.html