Daję ci listę wektorów bitowych o szerokości . Twoim celem jest zwrócenie dwóch wektorów bitowych z listy, które nie mają wspólnych 1, lub zgłoszenie, że taka para nie istnieje.$n$$k$

Na przykład, jeśli dam ci wówczas jedynym rozwiązaniem jest . Alternatywnie, wejście nie ma rozwiązania. Każda lista zawierająca całkowicie zerowy bitvector i inny element ma trywialne rozwiązanie .$[00110, 01100, 11000]$$\{00110, 11000\}$$[111, 011, 110, 101]$$000...0$$e$$\{e, 000...0\}$

Oto nieco trudniejszy przykład, bez rozwiązania (każdy wiersz jest nieco wektorem, czarne kwadraty to 1s, a białe kwadraty to 0s):

■ ■ ■ ■ □ □ □ □ □ □ □ □ □
■ □ □ □ ■ ■ ■ □ □ □ □ □ □ 
■ □ □ □ □ □ □ ■ ■ ■ □ □ □
■ □ □ □ □ □ □ □ □ □ ■ ■ ■
□ ■ □ □ □ ■ □ □ □ ■ ■ □ □
□ ■ □ □ ■ □ □ □ ■ □ □ □ ■
□ ■ □ □ □ □ ■ ■ □ □ □ ■ □ <-- All row pairs share a black square
□ □ ■ □ □ □ ■ □ ■ □ ■ □ □
□ □ ■ □ □ ■ □ ■ □ □ □ □ ■
□ □ ■ □ ■ □ □ □ □ ■ □ ■ □
□ □ □ ■ ■ □ □ ■ □ □ ■ □ □
□ □ □ ■ □ □ ■ □ □ ■ □ □ ■
□ □ □ ■ □ ■ □ □ ■ □ □ ■ □

Jak skutecznie można znaleźć dwa nienakładające się wektory bitowe lub pokazać, że nie istnieją?

Naiwnym algorytmem, w którym po prostu porównujesz każdą możliwą parę, jest . Czy można to zrobić lepiej?$O(n^2 k)$

Rozgrzewanie: losowe wektory bitowe

Jako rozgrzewkę możemy zacząć od przypadku, w którym każdy bitvector jest wybierany losowo równomiernie. Potem okazuje się, że problem można rozwiązać w czasie (a dokładniej można zastąpić ).O ( N : 1,6 min ( k , lg n ) ) 1,6 lg $O(n^{1.6} \min(k, \lg n))$$1.6$$\lg 3$

Rozważymy następujący dwuczęściowy wariant problemu:

Podane zestawy z bitvectors określić, gdzie istnieje nienakładające się para .S , T ⊆ { 0 , 1 } k s ∈ S , t ∈ $S,T \subseteq \{0,1\}^k$$s \in S, t \in T$

Podstawową techniką rozwiązania tego jest dzielenie i podbijanie. Oto algorytm czasowy przy użyciu funkcji dziel i zwycięż:$O(n^{1.6} k)$

1. Podziel i podstawie pierwszej pozycji bitu. Innymi słowy, formularz , , , .S T S 0 = { s ∈ S : s 0 = 0 } S 1 = { s ∈ S : s 0 = 1 } T 0 = { t ∈ T : t 0 = 0 } T 1 = { t ∈ T : t 0 = 1 $S$$T$$S_0 = \{s \in S : s_0=0\}$$S_1 = \{s \in S : s_0 = 1\}$$T_0 = \{t \in T : t_0 = 0\}$$T_1 = \{t \in T : t_0 = 1\}$

2. Teraz rekurencyjnie szukaj pary nienakładającej się z , z oraz z . Jeśli jakieś wywołanie rekurencyjne znajdzie parę, która się nie nakłada, wyślij ją, w przeciwnym razie wyślij „Nie ma pary nakładających się”.S 0 , T 0 S 0 , T 1 T 1 , S $S_0,T_0$$S_0,T_1$$T_1,S_0$

Ponieważ wszystkie wektory bitowe są wybierane losowo, możemy spodziewać się i . Mamy więc trzy rekurencyjne wywołania i zmniejszyliśmy rozmiar problemu dwa razy (oba zestawy są zmniejszone dwa razy). Po jeden z dwóch zestawów ma rozmiar 1, a problem można rozwiązać w czasie liniowym. Otrzymujemy relację powtarzalności wzdłuż linii , których rozwiązaniem jest . Uwzględniając czas wykonywania dokładniej w przypadku dwóch zestawów, widzimy, że czas działania wynosi .| S b | ≈ | S | / 2 | T b | ≈ | T | / 2 lg min ( | S | , | T | ) T ( n ) = 3 T ( n / 2 ) + O ( n k ) T ( n ) = O ( n 1,6 k ) $|S_b| \approx |S|/2$$|T_b| \approx |T|/2$$\lg \min(|S|,|T|)$$T(n) = 3T(n/2) + O(nk)$$T(n) = O(n^{1.6} k)$$O(\min(|S|,|T|)^{0.6} \max(|S|,|T|) k)$

Można to jeszcze poprawić, zauważając, że jeśli , prawdopodobieństwo istnienia pary, która się nie pokrywa, jest wykładniczo małe. W szczególności, jeśli są dwoma losowymi wektorami, prawdopodobieństwo, że się nie pokrywają, wynosi . Jeśli , istnieje takich par, więc przez związanie, prawdopodobieństwo istnienia pary, która się nie nakłada, wynosi najwyżej . Kiedy , to . Tak więc, jako etap wstępnego przetwarzania, jeślik ≥ 2,5 lg n + 100 x , r ( 3 / 4 ), k | S | = | T | = N n 2 n 2 ( 3 / 4 ) k k ≥ 2,5 lg n + $k \ge 2.5\lg n+100$$x,y$$(3/4)^k$$|S|=|T|=n$$n^2$$n^2 (3/4)^k$$k \ge 2.5 \lg n+100$ ≤ 1 / 2 100 K ≥ 2,5 lg n + $\le 1/2^{100}$$k \ge 2.5 \lg n + 100$, wówczas możemy natychmiast zwrócić „Nie ma pary nienakładającej się” (prawdopodobieństwo, że jest to niepoprawne, jest pomijalnie małe), w przeciwnym razie uruchomimy powyższy algorytm.

W ten sposób osiągamy czas działania (lub dla wariantu dwóch zestawów zaproponowanego powyżej), dla specjalnego przypadku, w którym bitwektory są wybierane równomiernie losowo.O ( n 1,6 min ( k , lg n ) ) O ( min ( | S | , | T | ) 0,6 maks. ( | S | , | T | ) min ( k , lg n ) $O(n^{1.6} \min(k, \lg n))$$O(\min(|S|,|T|)^{0.6} \max(|S|,|T|) \min(k, \lg n))$

Oczywiście nie jest to najgorsza analiza. Losowe wektory bitowe są znacznie łatwiejsze niż najgorszy przypadek - ale traktujmy to jako rozgrzewkę, aby uzyskać kilka pomysłów, które być może moglibyśmy zastosować w przypadku ogólnym.

Lekcje z rozgrzewki

Możemy nauczyć się kilku lekcji z powyższej rozgrzewki. Po pierwsze, pomocna jest funkcja dziel i zwyciężaj (dzielenie na pozycję bitową). Po drugie, chcesz podzielić się na pozycji bitowej z jak największą liczbą w tej pozycji; im więcej , tym mniejsze zmniejszenie wielkości podproblemu.1 $1$$0$

Po trzecie, sugeruje to, że problem staje się trudniejszy, gdy gęstość jest mniejsza - jeśli wśród bitvektorów jest bardzo niewiele (są to w większości ), problem wygląda dość trudny, ponieważ każdy podział zmniejsza się wielkość podproblemów trochę. Zdefiniuj więc gęstość jako ułamek bitów, które są (tj. Spośród wszystkich bitów ), a gęstość pozycji bitu aby była ułamkiem wektorów bitowych, które są w pozycji .1 1 0 Δ 1 n k i 1 $1$$1$$0$$\Delta$$1$$nk$$i$$1$$i$

Obsługa bardzo niskiej gęstości

W kolejnym kroku możemy zastanawiać się, co się stanie, jeśli gęstość będzie wyjątkowo mała. Okazuje się, że jeśli gęstość w każdej pozycji bitowej jest mniejsza niż , gwarantujemy, że istnieje para nie nakładająca się: istnieje (niekonstruktywny) argument istnienia wskazujący, że niektóre nie nakładające się para musi istnieć. To nie pomaga nam go znaleźć, ale przynajmniej wiemy, że istnieje.$1/\sqrt{k}$

Dlaczego tak jest? Powiedzmy, że para wektorów bitowych jest objęta pozycją bitu jeśli . Zauważ, że każda para nakładających się wektorów bitowych musi być zakryta przez jakąś pozycję bitu. Teraz, jeśli naprawimy określoną pozycję bitu , liczba par, które mogą być objęte tą pozycją bitu, wynosi co najwyżej . Podsumowując wszystkie pozycji bitów, stwierdzamy, że łączna liczba par objętych pewną pozycją bitową wynosix , y i x I = Y i = 1 i ( n Δ ( I ) $x,y$$i$$x_i=y_i=1$$i$ 2 < n 2 / k k < n $(n \Delta(i))^2 < n^2/k$$k$$< n^2$. Oznacza to, że musi istnieć para, która nie jest objęta żadną pozycją bitową, co oznacza, że ​​ta para się nie nakłada. Jeśli więc gęstość jest wystarczająco niska w każdej pozycji bitowej, z pewnością istnieje para, która się nie nakłada.

Jednak nie mogę zidentyfikować szybkiego algorytmu, aby znaleźć taką nie nakładającą się parę w tych reżimach, nawet jeśli jedna z nich istnieje. Nie widzę od razu żadnych technik, które zapewniłyby czas działania zależny od kwadratury od . Jest to więc miły szczególny przypadek, na którym można się skoncentrować, jeśli chcesz poświęcić trochę czasu na przemyślenie tego problemu.$n$

W kierunku algorytmu ogólnego przypadku

W ogólnym przypadku naturalna heurystyka wydaje się być: wybierz pozycję bitu z największą liczbą (tj. O największej gęstości) i podziel na nią. Innymi słowy:i $i$$1$

1. Znajdź pozycję bitową która maksymalizuje .i Δ ( i $i$$\Delta(i)$

2. Podział i podstawie pozycji bitu . Innymi słowy, formularz , , , .S T i S 0 = { s ∈ S : s i = 0 } S 1 = { s ∈ S : s i = 1 } T 0 = { t ∈ T : t i = 0 } T 1 = { t ∈ T : t i = 1 $S$$T$$i$$S_0 = \{s \in S : s_i=0\}$$S_1 = \{s \in S : s_i = 1\}$$T_0 = \{t \in T : t_i = 0\}$$T_1 = \{t \in T : t_i = 1\}$

3. Teraz rekurencyjnie szukaj pary nienakładającej się z , z oraz z . Jeśli jakieś wywołanie rekurencyjne znajdzie parę, która się nie nakłada, wyślij ją, w przeciwnym razie wyślij „Nie ma pary nakładających się”.S 0 , T 0 S 0 , T 1 T 1 , S $S_0,T_0$$S_0,T_1$$T_1,S_0$

Wyzwanie polega na analizie jego wydajności w najgorszym przypadku.

Załóżmy, że jako krok przetwarzania wstępnego najpierw obliczamy gęstość każdej pozycji bitu. Ponadto, jeśli dla każdego , przyjmijmy, że krok wstępnego przetwarzania daje wynik „Istnieje nakładająca się para” (zdaję sobie sprawę, że nie pokazuje to przykładu nakładającej się pary, ale odłóżmy to na bok jako osobne wyzwanie). Wszystko to można zrobić w czasie . Informacje o zagęszczeniu mogą być skutecznie utrzymywane, gdy wykonujemy połączenia rekurencyjne; nie będzie dominującym czynnikiem wpływającym na czas działania.Δ ( i ) < 1 / √k iO(nk$\Delta(i) < 1/\sqrt{k}$$i$$O(nk)$

Jaki będzie czas trwania tej procedury? Nie jestem pewien, ale oto kilka spostrzeżeń, które mogą pomóc. Każdy poziom rekurencji zmniejsza rozmiar problemu o około bitvectors (np. Od bitvectors do bitvectors). Dlatego rekurencja może wchodzić tylko na głębokości około . Jednak nie jestem od razu pewny, jak policzyć liczbę liści w drzewie rekurencyjnym (jest dużo mniej niż liści), więc nie jestem pewien, jaki czas powinien to prowadzić do.$n/\sqrt{k}$ n n - n / $n$k$n-n/\sqrt{k}$k 3$\sqrt{k}$$3^{\sqrt{k}}$

Szybsze rozwiązanie, gdy , przy użyciu mnożenia macierzy$n \approx k$

Załóżmy, że . Naszym celem jest osiągnięcie lepszych wyników niż czas działania .$n = k$$O(n^2k) = O(n^3)$

Możemy myśleć o wektorach bitowych i pozycjach bitowych jak o węzłach na wykresie. Pomiędzy węzłem bitvector a węzłem pozycji bitowej występuje krawędź, gdy bitvector ma 1 w tej pozycji. Powstały wykres jest dwustronny (z węzłami reprezentującymi bitvector z jednej strony i węzłami reprezentującymi położenie bitowe z drugiej) i ma węzłów.$n + k = 2n$

Biorąc pod uwagę macierz przylegania wykresu, możemy stwierdzić, czy istnieje ścieżka dwóch przeskoków między dwoma wierzchołkami, poprzez podniesienie kwadratu i sprawdzenie, czy otrzymana macierz ma „krawędź” między tymi dwoma wierzchołkami (tj. Wejście krawędzi w macierz kwadratową jest niezerowa). Dla naszych celów zero wpisu w kwadratowej macierzy przylegania odpowiada nie nakładającej się parze wektorów bitowych (tzn. Rozwiązanie). Brak zer oznacza, że ​​nie ma rozwiązania.$M$ $M$

Kwadratowanie macierzy nxn można wykonać w czasie , gdzie wiadomo , że ma mniej niż a przypuszcza się, że wynosi .$O(n^\omega)$$\omega$$2.373$$2$

Algorytm jest następujący:

• Konwertuj bitwektory i pozycje bitów na dwuczęściowy wykres z węzłów i co najwyżej krawędzi . To zajmuje czas .$n+k$$nk$$O(nk)$
• Oblicz macierz przyległości wykresu. To zajmuje czas i przestrzeń.$O((n+k)^2)$
• Wyprostuj macierz przylegania. Zajmuje to czas .$O((n+k)^\omega)$
• Przeszukaj sekcję bitvector macierzy przyległości pod kątem zerowych wpisów. Zajmuje to czas .$O(n^2)$

Najdroższym krokiem jest podniesienie kwadratu macierzy sąsiedztwa. Jeśli to ogólny algorytm zajmuje czas , co jest lepsze niż naiwny czas .$n=k$$O((n+k)^\omega) = O(n^\omega)$$O(n^3)$

To rozwiązanie jest również szybsze, gdy rośnie niezbyt dużo wolniej i nie zbyt szybko niż . O ile i , to jest lepsze niż . Dla co przekłada się na (asymptotycznie). Jeśli ogranicza się do 2, wówczas granice rozszerzają się w kierunku .$k$$n$$k \in \Omega(n^{\omega-2})$$k \in O(n^\frac{2}{\omega-1})$$(n+k)^\omega$$n^2 k$$w \approx 2.373$$n^{0.731} \leq k \leq n^{1.373}$$w$$n^\epsilon \leq k \leq n^{2-\epsilon}$

Jest to równoważne ze znalezieniem wektora bitowego, który jest podzbiorem dopełniacza innego wektora; tzn. jego 1 występuje tylko wtedy, gdy 0 występuje w drugim.

Jeśli k (lub liczba 1) jest mała, możesz uzyskać czas , po prostu generując wszystkie podzbiory dopełniacza każdego bitvectora i umieszczając je w trie (używając cofania). Jeśli w trie zostanie znaleziony bitvector (możemy sprawdzić każdy przed wstawieniem podzbioru dopełniacza), mamy parę, która się nie nakłada.$O(n2^k)$

Jeśli liczba 1 lub 0 jest ograniczona do jeszcze niższej liczby niż k, wykładnik można zastąpić tym. Indeksowanie podzbiorów może dotyczyć każdego wektora lub jego dopełniacza, o ile w sondowaniu stosuje się coś przeciwnego.

Istnieje również schemat wyszukiwania supersetów w trie, który przechowuje każdy wektor tylko raz, ale przeskakuje bity podczas sond, dla których, moim zdaniem, jest podobna złożoność złożona; tzn. ma wstawienie ale wyszukiwania .o ( k ) o ( 2 k$o(k)$$o(2^k)$

Reprezentują wektory wiertła, z n x k macierzy M . Take I i J pomiędzy 1 i n .$n\times k$$M$$i$$j$$n$

( M M T ) i j , iloczyn iloczynu i- tego i j- tego wektora, jest niezerowy, jeśli i tylko wtedy, gdy wektory i i j mają wspólną 1. Więc, aby znaleźć rozwiązanie, oblicz M M T i zwraca pozycję zerowego wpisu, jeśli taki wpis istnieje.$(MM^T)_{ij}$$i$$j$$i$$j$$MM^T$

Złożoność

Korzystanie z naiwnego mnożenia wymaga operacji arytmetycznych O ( n 2 k ) . Jeśli n = k , wymaga operacji O ( n 2.37 ) przy użyciu całkowicie niepraktycznego algorytmu Coppersmith-Winograd lub O ( n 2.8 ) przy użyciu algorytmu Strassena. Jeśli k = O ( n 0,302 ) , problem można rozwiązać za pomocą operacji n 2 + o ( 1 ) .$O(n^2k)$$n=k$$O(n^{2.37})$$O(n^{2.8})$$k=O(n^{0.302})$$n^{2 + o(1)}$