동적 프로그래밍 - 최대 사각형 블록

동적 프로그래밍 - 최대 사각형 블록

저는 1과 0으로 가득 찬 거대한 파일에서 1의 가장 큰 정사각형을 찾아야 합니다.동적 프로그래밍을 사용해야 한다는 것을 알고 있습니다.나는 그것을 2D 어레이에 저장하고 있습니다.가장 큰 사각형을 찾기 위한 알고리즘에 도움이 된다면 정말 좋을 것입니다, 감사합니다!

입력 예:

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

답변:

1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

지금까지 내 코드:

int Square (Sq[int x][int y]) {
   if (Sq[x][y]) == 0) {
       return 0;
   }
   else {
       return 1+MIN( Sq(X-1,Y), Sq(X,Y-1), Sq(X-1,Y-1) );
   }
}

(배열에 이미 입력된 값 포함)

int main() {
    int Sq[5][6]; //5,6 = bottom right conner
    int X = Square(Sq[5][6]);
}

거기서 어떻게 가야 하나요?

솔루션의 개요는 다음과 같습니다.

각 셀에 대해 왼쪽 상단 셀을 사용하여 정사각형을 얼마나 크게 만들 수 있는지 계산합니다.분명히 0이 있는 모든 셀은 카운트가 0이 됩니다.

오른쪽 아래 셀에서 반복하기 시작하고 왼쪽 아래로 이동한 다음 한 행 위로 이동하여 반복합니다.

검색할 때마다 다음 작업을 수행합니다.

1. 인 경우에는 assign 인셀할 0우경count=0
2. ( 또는 에지, " " " " 1" " " " " (" " " " " " " " " " " " " " " " " " 을 할당합니다.count=1
3. 다른 모든 셀의 경우 오른쪽, 오른쪽 아래 및 아래 셀의 개수를 확인합니다.그것들 중에서 가장 적은 것을 가지고 1을 더하고 그것을 카운트에 할당합니다. 유지하기max_count변수를 사용하여 현재까지의 최대 수를 추적할 수 있습니다.

행을가르는마지에막지로렬,max_count원하는 값을 가집니다.

복잡성은 더 이상 행렬의 횡단 비용이 아닙니다.

이것이 통과 후 행렬의 모습입니다.괄호 안의 값은 카운트입니다. 즉, 셀을 왼쪽 상단으로 사용하여 만들 수 있는 가장 큰 정사각형입니다.

1(1) 0(0) 1(1) 0(0) 1(1) 0(0)
1(1) 0(0) 1(4) 1(3) 1(2) 1(1)
0(0) 1(1) 1(3) 1(3) 1(2) 1(1)
0(0) 0(0) 1(2) 1(2) 1(2) 1(1)
1(1) 1(1) 1(1) 1(1) 1(1) 1(1)

Python에서 구현

def max_size(mat, ZERO=0):
    """Find the largest square of ZERO's in the matrix `mat`."""
    nrows, ncols = len(mat), (len(mat[0]) if mat else 0)
    if not (nrows and ncols): return 0 # empty matrix or rows
    counts = [[0]*ncols for _ in xrange(nrows)]
    for i in reversed(xrange(nrows)):     # for each row
        assert len(mat[i]) == ncols # matrix must be rectangular
        for j in reversed(xrange(ncols)): # for each element in the row
            if mat[i][j] != ZERO:
                counts[i][j] = (1 + min(
                    counts[i][j+1],  # east
                    counts[i+1][j],  # south
                    counts[i+1][j+1] # south-east
                    )) if i < (nrows - 1) and j < (ncols - 1) else 1 # edges
    return max(c for rows in counts for c in rows)

LSBRA(X,Y)"X,Y에서 오른쪽 하단이 있는 가장 큰 정사각형"을 의미합니다.

의사 코드:

LSBRA(X,Y):
   if (x,y) == 0:
       0
   else:
       1+MIN( LSBRA(X-1,Y), LSBRA(X,Y-1), LSBRA(X-1,Y-1) )

에지 셀의 경우 MIN 부분을 건너뛰고 (x,y)가 0이 아닌 경우 1만 반환할 수 있습니다.

다음과 같이 "파도"에서 그리드를 대각선으로 통과하여 작업합니다.

    0 1 2 3 4
  +----------
0 | 1 2 3 4 5
1 | 2 3 4 5 6
2 | 3 4 5 6 7
3 | 4 5 6 7 8

또는 가장자리 셀을 채우는 동안 왼쪽에서 오른쪽으로, 위에서 아래로 작업합니다.

    0 1 2 3 4
  +----------
0 | 1 2 3 4 5
1 | 6 7 8 9 .
2 | . . . . .
3 | . . . . .

데이터를 입니다. 모든 계산이 필요합니다. 그래서 모든 것이LSBRA()"데이터베이스"는 실제로 이전 계산 결과의 테이블 룩업일 뿐입니다(동적 프로그래밍 측면은 제외).

작동하는 이유

X, Y에서 오른쪽 아래에 있는 정사각형을 가지려면 다른 세 모서리에 각각 접촉하는 하나의 작은 차원의 중첩 제곱을 포함해야 합니다.즉, 가진다는 것은

XXXX
XXXX
XXXX
XXXX

당신은 또한...

XXX.    .XXX    ....    ....
XXX.    .XXX    XXX.    ....
XXX.    .XXX    XXX.    ....
....    ....    XXX.    ...X

세 개의 N 크기 사각형(각 LSBRA 검사)과 현재 사각형도 "사용"되어 있는 한 (N+1) 크기 사각형이 있습니다.

가장 먼저 떠오르는 알고리즘은 다음과 같습니다.

1. 열/행 1과 열/행 2가 있는 경우, 즉 각 항목과 다른 열/행의 해당 항목 간에 '&&' 작업을 수행합니다.
2. 길이 21이 있으면 2x2 제곱에 도달했음을 의미하는 결과 열을 확인합니다.
3. 그리고 앞의 두 개의 결과와 함께 다음 칸.길이가 31인 경우 3x3 정사각형에 도달했습니다.
4. 모든 열이 사용될 때까지 반복합니다.
5. 열 2부터 1-4를 반복합니다.

그것은 꽤 간단하고 당신의 문제가 숙제처럼 들리기 때문에 당신에게 구현을 보여드리지 않겠습니다.또한 입력이 매우 크면 속도가 느려지기 때문에 훨씬 더 효율적인 방법이 있을 수 있습니다.

입력 행렬을 다음과 같이 합니다.M x x m

T[i][j] 가장 큰입니다.(i,j).

표를 채우는 일반 규칙:

if (M[i][j] == 1) {
  int v = min(T[i][j-1], T[i-1][j]);
  v = min(v, T[i-1][j-1]);
  T[i][j] = v + 1;
}
else 
  T[i][j] = 0;

는 결제곱크최니다입값대의 입니다.T.

움T[i][0]그리고.T[0][j]사소합니다.

이 알고리즘이 당신의 대용량 파일에 사용될 수 있을지는 모르겠지만, 당신은 전체 행렬을 저장할 필요는 없고 현재 줄과 이전 줄만 저장할 필요가 있습니다.

다음 참고 사항은 일반적인 아이디어를 이해하는 데 도움이 될 수 있습니다.

• 크기가 오른쪽 바닥 각도(i-1, j), (i, j-1), (i-1, j-1)인 모든 제곱은 크기가 s+1인 오른쪽 바닥 각도(i, j)의 제곱 내부에 있습니다.
• (i, j)에 오른쪽 하단 모서리가 있는 s+1 크기의 제곱이 있는 경우, 오른쪽 하단 각(i-1, j), (i, j-1), (i-1, j-1)이 있는 최대 제곱의 크기는 적어도 s입니다.
• 반대의 경우도 마찬가지입니다.만약 (i-1, j), (i, j-1), (i-1, j-1)에서 아래쪽 직각을 갖는 적어도 하나의 정사각형의 크기가 s보다 작다면, (i, j)에서 오른쪽 아래쪽 모서리를 갖는 정사각형의 크기는 s+1보다 클 수 없습니다.

가장 비효율적이지만 간단한 방법은 다음과 같습니다.

1. 첫 번째 항목을 선택합니다.1인지 확인하고, 1x1 정사각형인지 확인합니다.

2. 아래에 하나, 오른쪽에 하나를 선택합니다. 1인 경우 2열 2, 1, 2x2 정사각형인 경우 2열 2를 선택합니다.

3. 3행 col 1, col 2, col 3을 확인하고, 1행 col 3, 2행 col 3(1, 3x3인 경우)을 확인합니다.

4. 그래서 기본적으로 행과 콜을 함께 확장하고 경계 안에 있는 모든 세포를 확인합니다.0을 맞추자마자 깨져서 1점 연속으로 이동하고 다시 시작합니다.

5. 행 끝에서 다음 행으로 이동합니다.

6. 끝까지

당신은 아마도 루프 등이 있는 동안 그것들이 어떻게 들어맞는지 볼 수 있을 것이고, 어떻게.&&s는 0을 확인하는 데 사용될 수 있으며, 당신이 그것을 볼 때, 당신은 아마도 그것이 어떻게 속도를 낼 수 있는지도 알게 될 것입니다.하지만 다른 답이 방금 언급했듯이, 그것은 약간 숙제처럼 들리기 때문에 실제 코드는 당신에게 맡기겠습니다.

행운을 빕니다.

여기서 핵심은 동적 프로그래밍을 사용하여 실제 영역 대신 영역의 루트를 추적할 수 있다는 것입니다.

알고리즘은 다음과 같습니다.

max-square라고 하는 int의 2D 배열을 저장합니다. 여기서 인덱스 i, j에 있는 요소는 i, j가 오른쪽 하단 모서리에 있는 정사각형의 크기를 나타냅니다.(만약 max[i,j] = 2라면, 지수 i,j가 2^2 = 4의 제곱의 오른쪽 아래 모서리라는 것을 의미합니다)

각 지수 i,j:

i,j에서 원소가 0이면 max-제곱 i,j를 0으로 설정합니다.

기타:

최대 제곱[i - 1, j] 및 최대 제곱[i, j - 1] 및 최대 제곱[i - 1][j - 1]의 최소값을 구합니다.max-square[i, j]를 1 + 3의 최소값으로 설정합니다.귀납적으로 최대 제곱 배열을 채웁니다.공정에서 최대값을 찾거나 계속 추적하여 해당 값 ^2를 반환합니다.

사람들이 제안한 솔루션을 살펴 보십시오. https://leetcode.com/discuss/questions/oj/maximal-square?sort=votes

N을 2D 배열에 있는 셀의 양이라고 합니다.모든 최대 빈 직사각형을 나열하는 매우 효율적인 알고리즘이 있습니다.가장 큰 빈 사각형은 이러한 빈 사각형 중 하나 안에 있으며, 최대 빈 사각형 목록이 계산되면 이를 찾는 것은 사소한 일입니다.이러한 목록을 만들기 위한 O(N) 알고리즘을 제시하는 논문은 소스 코드(최적화되지 않음)뿐만 아니라 www.ulg.ac.be/telecom/rectangles 에서도 확인할 수 있습니다.가장 큰 빈 직사각형의 수가 N으로 제한된다는 증거가 있습니다(논문 참조).따라서 가장 큰 빈 정사각형을 선택하는 것은 O(N)로 수행할 수 있으며, 전체 방법도 O(N)입니다.실제로 이 방법은 매우 빠릅니다.전체 코드가 C의 40줄을 넘지 않아야 하기 때문에 구현은 매우 쉽습니다(모든 최대 빈 직사각형을 나열하는 알고리즘은 약 30줄의 C를 사용합니다).

언급URL : https://stackoverflow.com/questions/1726632/dynamic-programming-largest-square-block