기와 알고리즘

Question

저는 퍼즐을 풀어야하는 문제에 직면 해 있습니다.

예. 20x20 (예 : 미터)의 (가변) 영역이 있습니다. 가변 크기를 가진 다수 주어진 세트 조각이있다. 4x3, 4x2, 1x5 조각 등등. 이러한 조각은 또한 내 문제에 더 많은 고통을 추가하려면 추가 할 수 있습니다. 퍼즐의 요점은 주어진 조각으로 20x20의 전체 영역을 채우는 것입니다.

은 무엇 이러한 위업을 달성하기위한 좋은 시작 알고리즘 것입니까? 효율성을 위해 열린 공간을 계산하는 경험적 방법을 사용하려고합니다. 조각에 따라, 일반적으로 너무 좋은 구조와 더불어, Exact Cover problem의 사전

Answer 1

에서

감사합니다. 휴리스틱 알고리즘에 대해서는 잘 모르지만, 잘 작동해야하는 몇 가지 정확한 옵션이 있습니다. 정확한 커버와 마찬가지로 보통

, 당신은 효율적으로 Algorithm X을 구현하기 위해 Dancing Links, 방법을 사용할 수 있습니다.

덜 일반적으로, 당신은 아마 제로 억제 의사 결정 다이어그램이 문제를 해결할 수 있습니다. 그것은 타일에 달려있다. 보너스로 전체 솔루션 (대개 너무 큰) 세트를 명시 적으로 저장하지 않고 모든 가능한 솔루션을 표시하고 계산하거나 일부 속성으로 생성 할 수 있습니다.

BDD 계열은 (- 그런 ZDDs하지만 스파 스보다 더 대칭 같은 BDD 계열을 가능한 타일 게재 위치를 몇 사용하여 솔루션과 같이 매우 희소하기 때문에) 같은 일을 달성하기 위해 더 많은 노드를 사용하여뿐만 아니라에 대해 작동합니다 .

또는 당신이 SAT 문제로 돌려 수는, 당신은 적은 정보 (예를 들어 어떤 솔루션 수)를 얻을 수 있지만, 빠른 쉬운 솔루션이 있다면.