Algorytm wyszukiwania podzbioru

9

Załóżmy, że mam listę $\cal X$ podzbiorów $\{1, ..., n\}$ . W razie potrzeby mogę wykonać wstępne przetwarzanie na tej liście. Po tym wstępnym przetwarzaniu otrzymuję kolejny zestaw $A \subseteq \{1, ..., n \}$ . Chcę zidentyfikować żadnych zestawów z . $B \in \mathcal X$ $B \subseteq A$

Oczywisty algorytm (bez wstępnego przetwarzania) wymaga czasu - po prostu testujesz dla każdego osobno. Czy jest coś lepszego niż to? $O(n |\cal X|)$ $A$ $B \in \mathcal X$

Jeśli to pomoże, możesz założyć, że dla dowolnego całkowita liczba dopasowań jest ograniczona przez coś takiego jak . $A$ $B \in \mathcal X$ $O(1)$

ds.algorithms ds.data-structures David Harris
źródło

3

To nie jest odpowiedź. To prosta, ale długa obserwacja. Mam nadzieję, że się przyda.

Wersja decyzyjna twojego problemu to: Tak $\cal X$ zawierają podzbiór $A$ ?

Problem ten związany jest z problemem oceny monotonicznych funkcji boolowskich $n$ zmienne. Podzbiór $\{1,\ldots,n\}$ jest równoważne z $n$ -bitstring, więc rodzina $\cal X$ jest równoważne funkcji boolowskiej $f$ z $n$ zmienne. Biorąc pod uwagę funkcję $f$ , można zdefiniować najmniej monotoniczną funkcję, która nie jest większa niż $f$ , mianowicie $g(y)=(\exists x\subseteq y,\,f(x))$ . Pierwotny problem sprowadza się następnie do oceny $g(A)$ . I odwrotnie, problem oceny monotonicznej funkcji boolowskiej można sprowadzić do pierwotnego problemu, albo naiwnie, przyjmując $f=g$ lub wybierając $f$ sprawia, że $\cal X$ mniejszy.

W praktyce dyski BDD zwykle działają dobrze. Jednym z możliwych podejść jest zbudowanie BDD $f$ , pochodzą z niego BDD dla $g$ , a następnie oceń $g$ . Średnia wielkość BDD dla $g$ musi być $\Omega\left(\binom{n}{n/2}\right)$ , ponieważ istnieje wiele monotonicznych funkcji boolowskich . Stąd teoretycznie jest to złe rozwiązanie.

Ale (1) możliwa jest lepsza analiza i (2) mogą istnieć poprawki w tym podejściu, które czynią go lepszym. Na przykład nie użyłem w żaden sposób korelacji między wielkością $\cal X$ i rozmiar $g$ BDD. (Musi istnieć korelacja, ale nie wiem, czy jest tutaj prosta czy użyteczna).

Dla kompletności, prosty algorytm obliczania BDD dla $g$ z BDD dla $f$ jest następujący.

m (x ? {fa}_{1} : {fa}_{0}) = x ? (m ({fa}_{0}) \lor m ({fa}_{1})) : m ({fa}_{0})

$m(x?f_1:f_0)=x?(m(f_0)\lor m(f_1)):m(f_0)$ Tutaj

\lor

$\lor$ jest standardową operacją na dyskach BDD.

Radu GRIGore
źródło

2

Czy to nie jest mniej więcej równoznaczne z wstępnym obliczeniem odpowiedzi dla każdego podzbioru

{1, 2, . . ., n}

$\{1,2,...,n\}$ , buforowanie wszystkich wyników w binarnym drzewie wielkości

2^{n}

$2^n$ , a następnie szukając właściwego wyniku (na czas

O (n)

$O(n)$ ) po otrzymaniu

A

$A$ ?

mjqxxxx

Używanie wykładniczej przestrzeni do przechowywania wstępnie przetworzonych danych brzmi dla mnie jak oszustwo, chociaż nie jest to zabronione w pytaniu. Ale mogę być stronniczy w stosunku do Kościoła o największej złożoności.

Tsuyoshi Ito

mjqxxxx i Tsuyoshi: Zgadzam się z oboje. Przepisałem tekst tak, aby, mam nadzieję, wyraźniej wyrazić zgodę. :)

Radu GRIGore

3

Być może możesz użyć techniki „wyszukiwania informacji”: w fazie przetwarzania wstępnego zbuduj odwrócony indeks (w twoim przypadku prosty $n \times | {\cal X}|$ wystarczy tablica dwuwymiarowa), która odwzorowuje element $x_i \in \{1,...,n\}$ do zbiorów w $\cal X$ które go zawierają: $inv(x_i)= \{ X_j \in {\cal X} \; | \; x_i \in X_j \}$ .

Skonfiguruj tablicę liczb całkowitych $occ$ długości $|\cal X|$ .

Następnie dla każdego $y_i \in A$ odzyskać $inv(y_i)$ i dla każdego $X_j \in inv(y_i)$ zrobić $occ[j] = occ[j]+1$

Na koniec potrzebne są zestawy, dla których $|X_j|=occ[j]$ .

Możesz dowolnie przyspieszyć proces (kosztem przestrzeni wykładniczej), indeksując dwa lub więcej elementów razem.

Marzio De Biasi
źródło

Algorytm wyszukiwania podzbioru

Odpowiedzi: