면적을 최대화하기 위해 사각형을 선택하십시오.

Question

임의의 크기의 2D 이진 매트릭스가 있습니다. 이 행렬에서 최대 면적을 보여주는 일련의 직사각형을 찾고 싶습니다. 제약 조건은 다음과 같습니다.

• 사각형은 행렬의 "0"- 필드 및 "1"- 필드 만 포함 할 수 있습니다.
• 각 직사각형은 다음 직사각형으로부터 주어진 거리를 가져야합니다.

그래서 날이이 행렬 조금 더 설명하자

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

개의 직사각형 사이의 최소 거리가, 최적의 솔루션은 모서리 사각형을 선택하면 될 것이다 따라서 1.하자 (1 , 0) - (3,1) 및 (1,3) - (4,3). 이 직사각형은 최소값입니다. 1 필드는 서로 떨어져 있고 "1"- 필드에 있지 않습니다. 또한이 솔루션은 최대 영역을 갖습니다 (6 + 4 = 10).

최소 거리가 2 인 경우, 영역 4 + 4 = 8 인 경우 최적 (1,0) - (4,0) 및 (1,3) - (4,3)이됩니다. 지금까지

list<rectangle> rectangles; 

struct rectangle { 
    int i,j; // bottom left corner of rectangle 
    int width,length; // width=size in neg. i direction, length=size in pos. j direction 
}; 

에 : 나는 목록에있는 모든 사각형을 저장 Find largest rectangle containing only zeros in an N×N binary matrix

:

는 지금까지,이 게시물에 유사한 사각형을 찾아 달성 , 나는 단지 무차별 체력 - 방법에 대해서만 생각했다. 그러나 물론, 나는 이것에 만족하지 않다.

list에 해당하는 사각형을 찾는 방법에 대한 몇 가지 힌트와 팁을 줄 수 있으면 좋겠으며 내 문제가 해결되기를 바랍니다.

Answer 1

다음 반례가 최대 영역의 모든 조합에도 무차별 검사가 사각형 최적 발견하지 못할 수 있음을 나타낸다 : 위의 예에서

110 
000 
110 

, 2 최대 면적 존재 직사각형, 각 영역 3, 하나의 수직 및 하나의 수평. 둘 다 선택할 수는 없으므로이 사각형의 하위 집합을 선택하는 것이 제한적이라면 할 수있는 최선의 방법은 전체 면적이 3 인 경우 하나를 선택하는 것입니다. 그러나 대신에 수직 영역 인 3 직사각형을 선택하는 경우 , 그리고 가장 왼쪽의 두 개의 0으로 구성된 최대가 아닌 1x2 사각형을 가져 와서 더 나은 총 면적을 얻을 수 있습니다. (최소 분리 거리가 0 인 경우, 최소 분리 거리가 1 인 경우 자신의 예를 들어, 대신 가장 왼쪽 0을 1x1 사각형으로 선택하여 총 면적 4에 대해 여전히 3보다 우수 할 수 있습니다.

특별한 경우에는 분리 거리가 0 인 경우 사소한 알고리즘이 있습니다 : 행렬의 모든 단일 0에 1x1 직사각형을 넣을 수 있습니다. 이 분리 거리가 0보다 큰 경우, 몇 분 전에 문제가 NP 하드가 아닌지 아직 알 수는 없지만 빠른 알고리즘을 아직 보지 못했습니다 ...