Znajdowanie podwielokrotności o największej wielkości dla wszystkich 1 w macierzy zawierającej liczby 1 i 0

Question

Załóżmy, że otrzymałeś bitmapę mXn, reprezentowaną przez tablicę M [1..m, 1 .. n], której wpisami są wszystkie 0 lub 1 Blok all-one to podmorska forma M [i .. j, j .. j0], w której każdy bit jest równy 1. Opisz i przeanalizuj wydajny algorytm, aby znaleźć blok w M jako pierwszy obszar

Próbuję stworzyć dynamiczne rozwiązanie programistyczne. Ale mój algorytm rekurencyjny działa w czasie O (n^n), a nawet po zapamiętywaniu nie mogę myśleć o obniżeniu go poniżej O (n^4). Czy ktoś może mi pomóc znaleźć bardziej wydajne rozwiązanie?

Answer 1

Oto algorytm O(numCols*numLines^2). Niech S[i][j] = sum of the first i elements of column j.

będę pracować algorytmu na przykładzie:

M 
1 1 0 0 1 0 
0 1 1 1 0 1 
1 1 1 1 0 0 
0 0 1 1 0 0 

Mamy:

S 
1 1 0 0 1 0 
1 2 1 1 1 1 
2 3 2 2 1 1 
2 3 3 3 1 1 

Rozważmy teraz problem znalezienia maksymalnej subarray wszystkich tych, w jednowymiarowej tablicy . Problem ten można rozwiązać za pomocą tego prostego algorytmu:

append 0 to the end of your array 
max = 0, temp = 0 
for i = 1 to array.size do 
    if array[i] = 1 then 
    ++temp 
    else 
    if temp > max then 
     max = temp 
    temp = 0 

Na przykład, jeśli masz ten 1d tablicy:

1 2 3 4 5 6 
1 1 0 1 1 1 

ty chcesz to zrobić:

Najpierw dołączyć 0:

1 2 3 4 5 6 7 
1 1 0 1 1 1 0 

Zauważ, że za każdym razem, gdy trafisz na 0, wiesz, gdzie ciąg przylegających końców. Dlatego jeśli utrzymujesz sumę bieżącą (zmienną temp) dla bieżącej liczby, możesz porównać tę wartość z maksymalną wartością (max) po zejściu do zera, a następnie zresetować sumę bieżącą. Daje to maksymalną długość ciągłej sekwencji zmiennych w zmiennej max.

Teraz możesz użyć tego podalgorytu, aby znaleźć rozwiązanie swojego problemu. Najpierw dołącz kolumnę 0 do macierzy. Następnie obliczyć S.

Następnie:

max = 0 
for i = 1 to M.numLines do 
    for j = i to M.numLines do 
    temp = 0 
    for k = 1 to M.numCols do 
     if S[j][k] - S[i-1][k] = j - i + 1 then 
     temp += j - i + 1 
     else 
     if temp > max then 
      max = temp 
     temp = 0 

Zasadniczo, dla każdej możliwej wysokości w subarray (istnieją O(numLines^2) możliwych wysokościach), można znaleźć jeden z maksymalnej powierzchni mającej tę wysokość przy zastosowaniu algorytmu do jednowymiarowej tablicy (w O(numCols)).

Rozważmy następujący "obraz":

M 
    1 1 0 0 1 0 0 
i 0 1 1 1 0 1 0 
j 1 1 1 1 0 0 0 
    0 0 1 1 0 0 0 

Oznacza to, że mamy wysokość j - i + 1 stałe. Teraz weź wszystkie elementy macierzy, które są między i i j włącznie:

0 1 1 1 0 1 0 
1 1 1 1 0 0 0 

Zauważ, że podobny problem jednowymiarowy.Podsumujmy kolumny i zobaczyć, co mamy:

1 2 2 2 0 1 0 

Teraz problem sprowadza się do jednowymiarowego przypadku, z tą różnicą, że musimy wybrać podciąg ciągłych j - i + 1 (co jest 2 w tym przypadku) wartości. Oznacza to, że każda kolumna w naszym "oknie" musi być pełna. Możemy to sprawdzić skutecznie, korzystając z matrycy S.

Aby zrozumieć, jak działa S, należy ponownie rozważyć sprawę jednowymiarową: niech s[i] = sum of the first i elements of the vector a. Więc jaka jest suma podciągu a[i..j]? Jest to suma wszystkich elementów do wartości a[j] włącznie, łącznie z sumą wszystkich wartości do włącznie z a[i-1], co oznacza s[j] - s[i-1]. Sprawa 2d działa tak samo, z tym że mamy dla każdej kolumny s.

Mam nadzieję, że jest to jasne, jeśli masz więcej pytań, zapytaj.

Nie wiem, czy to pasuje do twoich potrzeb, ale myślę, że istnieje również algorytm O(numLines*numCols) oparty na dynamicznym programowaniu. Nie mogę tego jeszcze rozgryźć, z wyjątkiem przypadku, w którym podobieństwo, na które masz ochotę, jest kwadratowe. Ktoś może mieć lepszy wgląd, więc poczekaj trochę więcej.

Answer 2

typu O (n) (liczba elementów) roztworu:

A 
1 1 0 0 1 0 
0 1 1 1 1 1 
1 1 1 1 1 0 
0 0 1 1 0 0 

generowanie tablicy C gdzie każdy element reprezentuje liczbę 1S powyżej i w tym to, aż pierwszy 0.

C 
1 1 0 0 1 0 
0 2 1 1 2 1 
1 3 2 2 3 0 
0 0 3 3 0 0 

Chcemy znaleźć wiersz R, a lewy, prawy indeks l, r, który maksymalizuje wartość (r-l+1)*min(C[R][l..r]). Oto algorytm sprawdzania każdego wiersza w czasie O (cols):

Zachowaj stos par (h, i), gdzie C[R][i-1] < h ≤ C[R][i]. W każdej pozycji cur, powinniśmy mieć h=min(C[R][i..cur]) dla wszystkich par (h, i) na stosie.

Dla każdego elementu:

• Jeśli h_cur>h_top
• • push (h, i).
• Else:
• • Podczas h_cur<h_top:
• • • Pop wierzch stosu.
• • • Sprawdź, czy miałoby to nowy najlepszy, to znaczy(i_cur-i_pop)*h_pop > best.
• • Jeśli h_cur>h_top
• • • push (h, i_lastpopped).

Przykładem w wykonaniu dla trzeciego rzędu w poniższym przykładzie

i =0  1  2  3  4  5 
C[i]=1  3  2  2  3  0 
           (3, 4) 
S=   (3, 1) (2, 1) (2, 1) (2, 1) 
    (1, 0) (1, 0) (1, 0) (1, 0) (1, 0)  
    (0,-1) (0,-1) (0,-1) (0,-1) (0,-1) (0,-1) 

i=0, C[i]=1) push (1, 0).
i=1, C[i]=3) Naciśnij (3, 1).
i=2, C[i]=2) Pop (3, 1). Sprawdź, czy (2-1)*3=3 jest nowy najlepszy.
Ostatni wykryty i miał wartość 1, więc naciśnij (2, 1).
i=3, C[i]=2) h_cur=h_top więc nic nie rób.
i=4, C[i]=3) Naciśnij (3, 4).
i=5, C[i]=0) Pop (3, 4). Sprawdź, czy (5-4)*3=3 jest nowy najlepszy.
Pop (2, 1). Sprawdź, czy (5-1)*2=8 jest nowy najlepszy.
Pop (1, 0). Sprawdź, czy (5-0)*1=5 jest nowy najlepszy.
Koniec. (OK, powinniśmy dodać dodatkowy termin C [cols] = 0 na końcu dla dobrego pomiaru).

Answer 3

Definiowanie nowej matrycy, która będzie przechowywać w A [i, j] dwie wartości: szerokość i wysokość największej submatrix z lewym górnym rogiem na i, j, wypełnij tę macierz zaczynając od dolnego prawego rogu , wierszami od dołu do góry. Znajdziesz cztery przypadki: Wykonaj te przypadki, gdy podana macierz pod adresem [i, j] = 1

przypadek 1: żaden z elementów prawego lub dolnego sąsiada w oryginalnej macierzy nie jest równy bieżącemu, tj .: M [i, j]! = M [i + 1, j] i M [i, j]! = M [i, j + 1] jest M oryginalną macierzą, w tym przypadku wartość A [i, j] jest 1x1

przypadek 2: sąsiedni element po prawej jest równy bieżącemu, ale dolny jest inny, wartość A [i, j] .width to A [i + 1, j] .width + 1 i A [i, j] .height = 1

sprawa 3: element sąsiada na dole jest równy, ale prawy jest inny, A [i, j] .width = 1, A [ i, j] .height = A [i, j + 1] .height + 1

przypadek 4: obie sąsiadów są równe: Trzy prostokąty są uważane:

1. A [i, j] .width = A [i, j + 1] .width + 1; A [i, j] .height = 1;

2. A [i, j] .height = A [i + 1, j] .height + 1; a [i, j].szerokość = 1;

3. A [i, j] .width = min (A [i + 1, j] .width + 1, A [i, j + 1] .width) i A [i, j] .height = min (A [i, j + 1] + 1 A [i + 1, j])

ten z maksymalna powierzchnia w powyższych trzech przypadkach będzie uważany za reprezentujący prostokąta w tym położeniu .

Wielkość największej matrycy, która ma lewy górny róg w i, j to A [i, j] .width * A [i, j] .height, dzięki czemu można zaktualizować maksymalną wartość znalezioną podczas obliczania A [i, j]

dolny rząd i skrajne prawe elementy kolumn są traktowane tak, jakby ich sąsiedzi odpowiednio z dołu iz prawej strony są różni.

Answer 4

Oto implementacja O (N) w języku C#.

Chodzi o to, aby użyć programowania dynamicznego do zbudowania skumulowanej matrycy, która ma rozmiar największej submatrix łącznie z bieżącą komórką.

public static int LargestSquareMatrixOfOne(int[,] original_mat) 
    { 
     int[,] AccumulatedMatrix = new int[original_mat.GetLength(0), original_mat.GetLength(1)]; 
     AccumulatedMatrix[0, 0] = original_mat[0, 0]; 
     int biggestSize = 1; 
     for (int i = 0; i < original_mat.GetLength(0); i++) 
     { 
      for (int j = 0; j < original_mat.GetLength(1); j++) 
      { 
       if (i > 0 && j > 0) 
       { 
        if (original_mat[i, j] == 1) 
        { 
         AccumulatedMatrix[i, j] = Math.Min(AccumulatedMatrix[i - 1, j - 1], (Math.Min(AccumulatedMatrix[i - 1, j], AccumulatedMatrix[i, j - 1]))) + 1; 
         if (AccumulatedMatrix[i, j] > biggestSize) 
         { 
          biggestSize = AccumulatedMatrix[i, j]; 
         } 
        } 
        else 
        { 
         AccumulatedMatrix[i, j] = 0; 
        } 
       } 
       else if ((i > 0 && j == 0) || (j > 0 && i == 0)) 
       { 
        if (original_mat[i, j] == 1) { AccumulatedMatrix[i, j] = 1; } 
        else { AccumulatedMatrix[i, j] = 0; } 
       } 
      } 
     } 
     return biggestSize; 
    }