Liczenie wysp w macierzach boolowskich

Biorąc pod uwagę $n \times m$ Macierz boolowska $\mathrm X$, pozwolić $0$ pozycje reprezentują morze i $1$wpisy reprezentują ziemię. Zdefiniuj wyspę jako sąsiadującą pionowo lub poziomo (ale nie po przekątnej)$1$ wpisy.

Pierwotne pytanie polegało na zliczeniu liczby wysp w danej matrycy. Autor opisał rozwiązanie rekurencyjne ($\mathcal{O}(nm)$ pamięć).

Ale bezskutecznie próbowałem znaleźć rozwiązanie strumieniowe (od lewej do prawej, a następnie do następnego rzędu), które dynamicznie liczy wyspy z $\mathcal{O}(m)$ lub $\mathcal{O}(n)$ lub $\mathcal{O}(n+m)$pamięć (nie ma ograniczeń złożoności czasowej). Czy to jest możliwe? Jeśli nie, jak mogę to udowodnić?

Kilka przykładów oczekiwanych wyników dla niektórych danych wejściowych dla countfunkcji:

$count\begin{pmatrix} 010\\ 111\\ 010\\ \end{pmatrix} = 1; % count\begin{pmatrix} 101\\ 010\\ 101\\ \end{pmatrix} = 5; % count\begin{pmatrix} 111\\ 101\\ 111\\ \end{pmatrix} = 1;$

$count\begin{pmatrix} 1111100\\ 1000101\\ 1010001\\ 1011111\\ \end{pmatrix} = 2$

$count\begin{pmatrix} 101\\ 111\\ \end{pmatrix} = 1$

Oto szkic algorytmu, który zachowuje tylko dwa wiersze w pamięci, więc $O(m)$pamięć. Ale ponieważ można uruchomić ten algorytm przy transpozycji macierzy bez problemów, faktyczna złożoność jest taka$O(\min(m, n))$pamięć. Czas przetwarzania wynosi .$O(mn)$

1. Inicjalizacja Zeskanuj pierwszy wiersz i znajdź wszystkie połączone podciągi tego wiersza. Przypisz każdemu rozłącznemu podciągowi unikalny identyfikator dodatni i zapisz go jako wektor o wartości zero, gdzie wynosi zero, a w przeciwnym razie unikalny identyfikator dodatni.$X$

2. Do każdego pozostałego wiersza przypisz unikalne identyfikatory (nigdy nie przypisuj ponownie poprzednich unikalnych identyfikatorów, upewnij się, że twoje identyfikatory ściśle się zwiększają) do podciągów w tym wierszu. Wyświetl poprzedni wiersz plus bieżący wiersz jako macierz na , a wszelkie połączone obszary należy przypisać do ich minimum. Jako przykład:$2$$m$

   $$\begin{array}0010402220333300\\ 506607080009990\end{array} \rightarrow \begin{array}0010402220333300\\ 504402020003330\end{array}$$

   Nie ma potrzeby aktualizowania poprzedniego wiersza dla poprawności tego algorytmu, tylko bieżący.

   Po zakończeniu znajdź zestaw wszystkich identyfikatorów w poprzednim wierszu, które nie łączą się z następnym wierszem, odrzucając duplikaty . Dodaj rozmiar tego zestawu do licznika wysp.

   Możesz teraz odrzucić poprzedni wiersz i przypisać bieżący wiersz do poprzedniego i przejść dalej.

3. Aby poprawnie obsłużyć ostatni wiersz udawać, na dole znajduje się kolejny rząd zer i ponownie uruchom krok 2.$X$

Orlp daje rozwiązanie używając słów spacji, które są bitami przestrzeni (zakładając dla uproszczenia, że ). I odwrotnie, łatwo jest wykazać, że bitów przestrzeni jest potrzebne, zmniejszając rozłączenie zestawu dla twojego problemu.$O(n)$$O(n\log n)$$n=m$$\Omega(n)$

Załóżmy, że Alicja ma wektor binarny a Bob ma wektor binarny i chcą wiedzieć, czy istnieje indeks taki, że . Prowadzą algorytmu dla matrycę, której rzędy są i . Po odczytaniu pierwszego wiersza Alicja wysyła Bob oraz zawartość pamięci, aby Bob mógł ukończyć algorytm i porównać z liczbą połączonych komponentów. Jeśli dwie liczby pasują do siebie, dwa wektory są rozłączne (nie ma indeksu$x_1,\ldots,x_n$$y_1,\ldots,y_n$$i$$x_i=y_i=1$$2\times(2n-1)$$x_1,0,x_2,0,\ldots,0,x_n$$y_1,0,y_2,0,\ldots,0,y_n$$\sum_i x_i$$\sum_i (x_i+y_i)$$i$), i wzajemnie. Ponieważ jakikolwiek protokół dla rozłączenia wymaga bitów (nawet jeśli może on błądzić z małym stałym prawdopodobieństwem), dedukujemy dolną granicę , która obowiązuje nawet dla losowych protokołów, które mogą błądzić z niektórymi małe stałe prawdopodobieństwo.$\Omega(n)$$\Omega(n)$

Możemy ulepszyć rozwiązanie Orlp, używając partycji nieprzekraczających . Matryca czytamy wiersz po rzędzie. Dla każdego wiersza pamiętamy, które 1s są połączone ścieżkami przechodzącymi przez poprzednie rzędy. Odpowiednia partycja nie jest krzyżująca, a zatem może być kodowana przy użyciu bitów (ponieważ partycje nie krzyżujące są liczone przez liczby katalońskie, których tempo wzrostu jest bardziej wykładnicze niż silni). Podczas czytania następującego wiersza utrzymujemy to reprezentowanie i zwiększamy licznik, ilekroć wszystkie końce części nie są podłączone do bieżącego wiersza (licznik przyjmuje dodatkowe bity ). Podobnie jak w rozwiązaniu Orlp, dodajemy ostatni zerowy rząd zer, aby zakończyć przetwarzanie matrycy. To rozwiązanie wykorzystuje$O(n)$$O(\log n)$$O(n)$ bitów, co jest asymptotycznie optymalne, biorąc pod uwagę naszą dolną granicę.