최소한의 세분을 찾는 방법
https://stackoverflow.com/questions/1268826
-
13-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
당신이 캔버스가 있고이 캔버스에는 이미 몇 가지 물체가 있다고 상상해보십시오. "발견되지 않은"영역을 사각형으로 덮는 최소한의 방법을 어떻게 찾을 수 있습니까?
필자의 경우 "캔버스"는 HTML-DIV 컨테이너이고 객체는 중첩 된 div-container입니다. 다음과 같이 보일 수 있습니다. http://www.encodechain.com/demo/200908_optimize.png왼쪽에는 "시작"이 있고 오른쪽에는 가능한 첫 "단계"가 있습니다.
나는 이것에 대한 알고리즘이 있다는 것을 알고 있지만 현재 이름을 기억할 수 없습니다.
해결책
내가 찾을 수있는 가장 좋은 것은이 논문이었습니다. 가장 적은 사각형으로 사각형 타일링. 이 논문은 흥미로운 독서이지만 때때로 "보편적 상수"에 대한 이야기로 이론 영역에 깊이 파고 들었다. "K 제곱으로 N에 의한 크기 M의 사각형"의 문제가 NP- 완성인지 여부는 확실하지 않습니다. 다른 응답에서 언급 한 바와 같이, 귀하의 질문은 NP- 완료 인 포장 문제와 유사합니다. 물론, 당신의 문제는 당신이 비류 영역을 다루고 있기 때문에이 백서에서 다루는 문제의 일반화입니다. 당신은 당신의 영역을 최소 수의 직사각형으로 나누는 것으로 시작할 수 있습니다. 그리고 마지막으로, 그렇게 효율적으로 할 수 있더라도, 그 사각형을 최적으로 기울일 때 전반적인 최적의 타일링이 발생하는지 확실하지 않습니다.
저자가 지적했듯이, 탐욕스러운 알고리즘은 시작하기에 좋은 곳입니다. 지역이 가득 차있을 때까지 할 수있는 가장 큰 사각형을 내려 놓으십시오.
