Znalezienie lokalne maksima w tablicy 2D

Question

lokalne maksimum w 2D tablicy może być zdefiniowana jako wartość taka, że ​​wszystko to 4 sąsiedzi są mniejsze lub równe do niego, czyli do a[i][j] być lokalne maksimum,

a[i+1][j] <= a[i][j] 
&& a[i-1][j] <= a[i][j] 
&& a[i][j+1] <= a[i][j] 
&& a[i+1][j-1] <= a[i][j] 

Zostałem poproszony o znalezienie wszystkich lokalnych maksimów w danej tablicy 2D.

Naiwnym sposobem wykonania tego byłoby przejrzenie wszystkich elementów i sprawdzenie, czy każdy element jest lokalnym maksimum. To byłby O (n^2). Uważam, że nie można zrobić nic lepszego, chociaż mój przyjaciel twierdzi, że powinien istnieć asymptotycznie lepszy algorytm. Jakieś wskazówki?

Miałem na myśli podział Divide i Conquer, ale uważam, że niemożliwe byłoby wykrycie wszystkich lokalnych maksimów bez przechodzenia przez wszystkie liczby, które musiałyby być O (n^2). Czy mam rację, czy też czegoś brakuje?

Answer 1

Jestem prawie pewien, że nie da się tego rozwiązać w mniej niż porównań O (n^2). Załóżmy macierz 2d na planszy szachowej, w której wszystkie białe kwadraty mają 1, a czarne 0. Będziemy mieli rozwiązania O (n^2), a każde rozwiązanie wymaga co najmniej jednego porównania.

Answer 2

Uważam, że na to pytanie można odpowiedzieć za pomocą tak zwanych argumentów przeciwników, co daje niższą granicę liczby porównań.

I według mnie masz rację ... wymagałoby to co najmniej dwóch porównań.

Answer 3

Jeśli twoja macierz nie jest kwadratowa, twoje rozwiązanie jest w rzeczywistości O(I * J), a nie O(n^2). Ściśle mówiąc masz tylko elementy N w twojej tablicy 2d, więc to rozwiązanie to O(N). Jedynym sposobem, jaki może to być O(n^2), jest sytuacja, gdy tablica jest kwadratowa, tak że I = J = N.

Ponieważ porównanie to jest <=, a nie <, musisz jeszcze sprawdzić następny element, a wszelkie skróty, które wypróbujesz, będą prawdopodobnie zależne od procesora.

Najgorszym przypadkiem jest, że cała tablica jest lokalne maksima, ponieważ cała tablica jest równa tej samej wartości.

Zatem należy odwiedzić każdy element raz, dzięki czemu O(N)

Aby poprawić wydajność osiągana w ten trzeba by użyć wskaźników do dostępu, którego tablicę, jak w większości języków 2d tablice wykonują znacznie gorzej niż 1d tablic .

Answer 4

NIE musiał odwiedzić każdy element:

Wszystko co musisz zrobić, to wizualizować siatkę i widać, że to może być rozwiązane w znacznie mniej niż płaskiej n^2 (lub I * J) . Oto optymalizacje według poziomu:

1] dla macierzy I * J, potrzebujesz tylko wyszukiwania (I-2) * (J-2). Czemu? granice nie mogą być maxima powodu niezdefiniowanych elementów:

e.g. grid[0][J] or grid[I][0] could never be maxima. because of the -1 neighbor. 

więc na 10 przez 12 sieci, zamiast wizyty wszystkie 120 elementów, patrzymy na 80 elementów.

2] jeśli siatka [I] [J] jest maksimum, wówczas możemy pominąć wszystkie komórki sąsiadujące z [I] [J], gdy będziemy kontynuować wyszukiwanie. Spowoduje to dalszą redukcję liczby elementów do porównania.

Dlatego odpowiedź brzmi: nie, nie musisz odwiedzać każdego elementu.

Answer 5

Po prostu heads up, lokalne maksima lub minima siatki 2D mogą być obliczane w czasie O (nlgn) za pomocą strategii dziel i rządź. Jest to nieco lepszy czas związany niż algorytm brute force zawarty w klasie złożoności O (n^2). Ponadto można wprowadzić ulepszenia do algorytmu dziel i podbij, aby uzyskać algorytm O (n) do wyszukiwania ekstremów w sieci 2D.

Sprawdź te notatki na temat teorii za taki szczyt zbieranie algorytmów (jestem pewien ich są więcej materiałów tam):

http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf