모든 가장자리가 4 가지 색상을 가질 수있는 타일 세트가 있습니다.
이 타일의 주어진 세트 (유한)로부터 최대 가능한 사각형 빌드를 찾는 작업입니다. 타일을 회전 할 수 있습니다.
이 작업을위한 솔루션을 찾기 위해 3 가지 알고리즘을 설계해야합니다. 하나의 완전하고 두 개의 aproximations.
분명히 알고리즘 수업을위한 나의 임무이기 때문에 완전한 솔루션에 대해 묻지는 않는다.
Im은 이미 역 추적을 사용하여 (sqrt (n) 크기의 사각형을 검색합니다. 찾을 수없는 경우 작게 찾기를 시도하지만) 근접 알고리즘을 만드는 방법을 모릅니다.
나는 그것이 좋은 aproach가 아니라는 것을 문서화하기 위해 특별한 경우에만 좋은 대답을 찾을 수있는 어리석은 일이 될 것이라고 생각하지만, 여전히 더 빨리 되돌아 가고 꽤 좋은 것을 필요로한다.
또한이 NP-hard 문제입니까? 내 백 트랙킹 알고리즘은 기하 급수적인데, 더 좋은 알고리즘은 없다는 것을 의미하지는 않습니다 ...유한 타일 세트에서 최대 사각형 찾기 (근사값)
편집 : 기하 급수적 인 시간을 가진 완전한 알고리즘을 가지고 있습니다.이 알고리즘에 대해 몇 가지 힌트를 줄 수 있습니까? 다항식 시간 문제 또는 더 나은 다음 기하 급수적 인 문제?
EDIT2 :이 문제는 사각형 격자 그래프 (http://mathworld.wolfram.com/GridGraph.html)로 그래프를 줄이는 문제로 바뀔 수 있다는 생각이 들었습니다. 타일을 격자를 그리는 방식으로 배열 할 수 있다면 여전히 문제가 있지만 이는 시작하기 좋은 시점 일 수 있습니다. 예를 들어 그래프를 제곱 - 그리드 그래프로 환원시키는 욕심 또는 다른 근접 알고리즘이 있습니까?
"모든 가장자리는 네 가지 색상 중 하나를 가질 수 있습니다"라고 가정 할 때 각 타일의 네 모서리는 모두 색이 지정되어 있으며 타일의 색상 세트는 어떤 순서로도 될 수 있으며 1 ~ 4 색으로 구성 될 수 있습니다. 바깥 쪽 타일의 바깥 쪽 가장자리는 제한되지 않으며, 구성된 정사각형의 인접한 타일 가장자리는 일치하는 색상을 갖습니다. 예를 들어, 색상이 R, G, B, P이고 타일 집합이 S = {RRRR, RPPP, RRBG, PGRB}이면 2x2 제곱을 집합으로 바둑판 식으로 배열 할 수 있습니다. 권리? –
24 @@ jwpat7 네, 맞습니다. – Pax0r