모양과 색상이 다른 사각형의 격자가 있고 동일한 레이아웃의 색상을 나타내는 사각형의 수를 줄이고 싶습니다 (합리적으로 최적에 가깝고 최적은 필요하지 않습니다).
위의 이미지는 매우 단순화 된 경우이며 사각형 사이의 공백은 시각화를위한 것입니다. 실제로 실제로 압축되어 있습니다.
이 작업을 수행하는 데 도움이되는 접근 방식 또는 알고리즘 이름 (Google에 만족)은 무엇입니까?
답변
먼저 소스 사각형을 기본 그리드의 셀로 변환하여 입력을보다 균일하게 만들 수 있습니다. (효과적으로 문제를 래스터 화)
이를 통해 소스 사각형으로 직접 작업 할 때 명확하지 않을 수있는 최적화를 찾을 수 있습니다. 특히 여러 소스 사각형을 분할하여 서로 다르게 조합하는 경우 특히 그렇습니다.
다음으로 깊이 우선 검색 또는 플러드 필링 알고리즘을 사용하여 동일한 색상의 연결된 영역을 찾을 수 있습니다. 연결된 각 영역 ( polyomino )을 개별적으로 고려할 수 있습니다 . 다른 영역에 대한 작업은이 영역에 영향을 줄 필요가 없습니다.
효과적으로 우리는이 polyomino를 사각형으로 해체하는 방법을 찾고 싶습니다 (불행히도 내가 찾을 수있는 대부분의 문헌은 반대 문제입니다.
하나의 간단한 방법은 인접한 사각형의 가로 런을 길고 마른 사각형으로 결합하는 것입니다. 그런 다음 위의 행과 비교하여 각 런 / 로우를 완료하거나 각 셀을 현재 런에 추가 할 때 런 시작과 끝이 일치하면 결합 할 수 있습니다.
나는이 방법이 얼마나 최적에 가까운 지 아직 모른다. 아직 고려하지 않은 행이 지금까지 본 행과 다른 분할을 제안하면 약간의 문제가 발생할 수 있습니다.
런 / 직사각형이 위와 아래의 런으로 정확하게 덮여 있는지 감지 한 다음,이를 분할하고 병합하면이 특정한 경우가 해결되지만 문제가 얼마나 일반적인지 살펴 보지 않았습니다.
또한 우리가 polyomino의 둘레를 걷는 방법을 살펴 보았고 오목한 구석이 생길 때마다 잘라 냈지만이 접근법은 더 오류가 발생하기 쉽습니다. 최적의 결과를 얻으려면 두 개의 오목한 모서리를 연결하는 우선 순위 컷을 필요로하는 것처럼 보이며, 중공이 포함 된 모양에는 특별한 처리가 필요하므로 행 스캔 방법에는 단순 이점이있는 것 같습니다.
내가보고있는 또 다른 방법은 맨 윗줄에서 찾은 첫 번째 실행을 수행하고 가능한 한 확장하는 것입니다. 그런 다음 남은 것의 맨 윗줄에서 첫 번째 실행을 수행하십시오. 이것은 반전 된 T 모양에서 넘어 지므로 최적도 아닙니다.
동적 프로그래밍을 사용하여 최적의 분할을 찾는 방법이 있다고 생각하지만 아직 찾지 못했습니다.