Liczenie wysp w macierzach boolowskich

9

Biorąc pod uwagę n×m Macierz boolowska X, pozwolić 0 pozycje reprezentują morze i 1wpisy 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 (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 O(m) lub O(n) lub 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(010111010)=1;count(101010101)=5;count(111101111)=1;

count(1111100100010110100011011111)=2

count(101111)=1

pgs
źródło
1
1. Co rozumiesz przez „ortogonalny”? Masz na myśli podłączony komponent? 2. Co możemy założyć o sposobie przechowywania matrycy? Czy możemy założyć, że jest on przechowywany w pamięci zewnętrznej (np. Na wolnym dysku twardym), abyś mógł odczytać dowolną część, ale szybciej będzie można odczytać ją pojedynczo? Czy też otrzymujemy matrycę w sposób strumieniowy, gdzie po otrzymaniu części matrycy wejściowej nigdy więcej nie zobaczymy tej części?
DW
1
Fajne dzięki. Zachęcam do edycji pytania w celu wyjaśnienia tych kwestii. Jeśli przesyła strumieniowo, w jakiej kolejności przychodzą bity matrycy? Skanujesz od lewej do prawej między wierszami, a następnie do następnego rzędu?
DW
1
Edytuj pytanie, aby uwzględnić wszystkie te szczegóły. Komentarze są ulotne.
Yuval Filmus
2
Nie wszystkie informacje podane w komentarzach można znaleźć w samym poście. Niektóre z tych informacji są bardzo ważne, na przykład model przesyłania strumieniowego. Komentarze mogą zniknąć, a zatem (i ze względu na standardy społeczności) wszystkie wymagane szczegóły powinny stanowić część głównego postu.
Yuval Filmus
1
Jaka jest wymagana złożoność czasu?
hengxin

Odpowiedzi:

4

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 takaO(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:2m

    010402220333300506607080009990010402220333300504402020003330

    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
źródło
6

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(nlogn)n=mΩ(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 indeksux1,,xny1,,ynixi=yi=12×(2n1)x1,0,x2,0,,0,xny1,0,y2,0,,0,ynixii(xi+yi)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.Ω(n)Ω(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 wykorzystujeO(n)O(logn)O(n) bitów, co jest asymptotycznie optymalne, biorąc pod uwagę naszą dolną granicę.

Yuval Filmus
źródło