알고리즘은 2D 어레이 단순화

Question

특정 요소를 덮는 사각형의 최소값을 찾아 내기 위해, I는 다음의 문제를 해결해야한다. 모든 사각형을 포함하는 최소 수의 사각형을 찾습니다. 사각형은 겹쳐서는 안됩니다. 이미 "충분히 좋은"하지만 항상 사각형의 최소 수를 찾을 수없는 해결책을 가지고 List<Rectangle> FindCoveringRectangles(bool[,] array)

: 같은

함수 서명이 보일 수 있습니다. 이 문제를 해결하기 위해 적용 할 수있는 잘 알려진 효율적인 알고리즘이 있는지 알고 싶습니다.

예 :

의 입력 배열 다음 사각형 초래할 수

(가독성 도트로 대체 0)

.......... 
.1.....11. 
.......11. 
...111.... 
...111.... 
...111.... 
....1111.. 
....1111.. 
......11.. 
.......... 

:

(2,2,2,2), 
(2,8,3,9), 
(4,4,6,6), 
(7,5,8,8), 
(9,7,9,8) 

(상단 , 왼쪽, 아래, 오른쪽), 1- 기반

하나 이상의 솔루션이있을 수 있지만 하나이면 충분합니다.

Answer 1

이것은 NP 종류의 문제를 쉽게 나타낼 수있는 종류의 일치하는 문제입니다. 그러나 실제로는 매우 빠른 해결책이있는 것 같습니다!

bfs flood-fill을 사용하면 연결된 각 구성 요소 O(n)을 찾을 수 있습니다. 그러므로 우리는 하나의 연결된 영역을 채워야한다고 가정 할 수 있습니다. 지역이 구멍이없는 경우

, 당신은 this paper에 설명 된 알고리즘을 사용할 수 있습니다 (또는 here on google scholar를.)

O (N N 로그 기록) 알고리즘은 최소 직사각형을 제안한다 간단한 직선형 폴리곤을 분할합니다. 단순한 직선형 폴리곤 P의 경우, 꼭지점이 보이는 쌍은 꼭지점이며, P 내부에있는 가로 또는 세로 선분으로 연결될 수있는 모서리입니다. 정점 가장자리 가시 쌍이 발견되면 단순한 직선형 다각형의 코드로부터 유도 된 2 부분 그래프의 최대 매칭 및 최대 독립 세트는 2 부분 그래프를 구성하지 않고 선형 시간으로 발견 될 수있다. 이 알고리즘 세로 볼록 직선 폴리곤 최소 분할 문제 사용 (가로) 볼록 직선 다각형은 일부 용지는 구멍 영역의 경우를 커버 함

O (n)이 시간에 해소 할 수있다 . 이것들은 O (n^(3/2) logn)에서 실행되지만, 여전히 꽤 잘 맞습니다.

또는, 홀을 사용하지 않고 문제를 풀고 각 홀에 대한 문제를 해결 한 다음 빼기 만하면됩니다. 이것은 최적의 솔루션을 제공하지는 않지만 런타임을 유지할 수 있습니다.

모양을 다른 토폴로지 파트로 분할 할 수도 있지만, 홀 수가 기하 급수적으로 늘어날 수 있습니다.

세 번째로 제안 된 알고리즘을 좀 더 일반적인 경우에 적용 할 수는 있지만 어려울 수 있습니다.