이 문제에 대한 무차별 대입 솔루션을 어떻게 최적화 할 수 있습니까?
아래에 설명 된 문제에 대한 해결책을 찾고 있습니다. 나는 무차별 대입을 사용하고 있으며 솔루션이 금지되는 지점에 도달 했으므로 가능한 경우 더 많이 최적화해야합니다. 물론 문제를 해결하는 더 좋은 방법이 있다면 더 좋을 것입니다 (무차별 대입이 아닌).
솔루션을 개선하기 위해 할 수있는 일이 있거나 조사 할 수있는 참조 (유사한 문제 등)가 있습니까?
문제
직사각형 보드로 시작합니다. 각 셀은 N 상태 일 수 있으며 각 셀의 초기 상태는 각 셀에 대해 무작위 (0 <= 상태 <N)입니다. 우리는 또한 보드 안에 모두 맞는 다양한 모양을 가지고 있습니다. 모든 모양은 연속적입니다.
각 도형은 보드에 한 번만 배치해야합니다. 도형을 배치하면 도형에 속한 각 셀의 값이 1 씩 증가합니다. 셀의 보드 값이 N에 도달하면 0으로 변경됩니다.
목표는 최종 보드에 값이 0 인 모든 셀이 있도록 각 모양을 배치해야하는 위치를 찾는 것입니다. 항상 하나 이상의 솔루션이 있습니다. 완성 된 보드에서 시작하여 임의의 위치에 임의의 모양을 적용하여 문제가 발생한다고 가정 해 보겠습니다.
보드 크기, 상태 수 N 및 모양 수는 게임의 설정이며 각 '레벨'에 대해 계속 증가합니다 (다른 속도로).
내가 현재하고있는 일
무차별 대입만으로도 일정 크기까지 문제를 해결할 수 있습니다. 몇 가지 최적화가 있습니다. 해결책이 불가능한 지점에 도달 했으므로 논리를 개선하고 싶습니다.
가장 먼저 할 일은 모양을 더 큰 것에서 더 작은 것으로 주문하는 것입니다. 더 작은 것이 내부 반복에서 이동됩니다. (내가 증명하지는 않았지만 더 빠른 것으로 테스트 된) 가정은 솔루션을 생성 할 가능성이 더 높기 때문에 더 작은 모양을 더 많이 이동하는 것이 더 낫다는 것입니다.
둘째, 반복되는 모양의 경우 동일한 결과를 산출하기 때문에 모든 순열을 확인하지 않습니다. 또한 동일한 모양 쌍이 겹칠 때 한 세트의 위치 만 확인합니다 (모든 겹침이 동일한 결과를 생성하기 때문에).
많은 도움이 될 것 같지만 여전히 구현중인 마지막 최적화는 시퀀스의 각 모양에서 이동해야하는 모양의 총 셀 수를 세는 것입니다. 완성 된 보드를 얻는 데 필요한 총 셀 뒤집기 수를 뺀이 숫자는 N의 배수 여야합니다. 그렇지 않은 경우 나머지 모양 위치를 강제로 강제하지 않으며 외부 루프에서 모양을 다시 배치해야합니다.
추가 세부 정보
이를 최적화하는 방법에 대한 다른 팁에 관심이 있습니다. 알려진 알고리즘, 심지어이 문제에 대한 좋은 이름조차도 더 많이 연구하는 데 사용할 수 있습니다.
답변
정수 선형 계획법
문제는 다음과 같이 공식화 될 수 있습니다. 우리는 벡터를받습니다. $v_{i,j} \in (\mathbb{Z}/N\mathbb{Z})^d$, 보드에 $d$ 목표는 벡터가 주어집니다. $c \in (\mathbb{Z}/N\mathbb{Z})^d$, 기능 찾기 $f$ 그래서 $\sum_i v_{i,f(j)}=c$. 이 문제는 정수 선형 계획법으로 해결할 수 있습니다. 이것은$d$-차원 부분 집합 합 문제이므로 다차원 부분 집합 합에 대한 다른 알고리즘을 찾아서 시도해 볼 수도 있습니다.
그런 식으로 어떻게 공식화합니까? 그리드에$d$ 세포, 우리는 모양을 $d$-0과 1의 벡터, 모양으로 덮인 셀에 1이 있습니다. 각 모양은 여러 다른 위치에 배치되어 다른 벡터를 생성 할 수 있습니다.$v_{i,j}$ 에 해당 $j$장소 모양 $i$ 배치 할 수 있습니다. $c$ 원래 그리드에있는 숫자에 해당합니다 (음, 그 숫자의 부정, 모듈로 $N$). 모든 산술은 모듈로 수행됩니다.$N$.
약간 더 똑똑한 무차별 대입
또는 메모리를 시간과 교환하여 무차별 대입을 약간 개선하는 방법이 있습니다. 당신이 가지고 있다고 가정$k$모양. 첫 번째를 배치하는 모든 방법을 열거하여 시작하십시오.$k/2$모든 0의 빈 보드에 셰이프를 배치하고 모든 결과 위치를 해시 테이블 또는 정렬 된 목록에 저장합니다. 그런 다음 마지막을 배치하는 모든 방법을 열거합니다.$k/2$시작 위치에 셰이프를 배치하고 해시 테이블 또는 정렬 된 목록에서 각 결과 위치를 찾습니다. 일치하는 항목을 찾으면 솔루션이 생성됩니다. 이렇게하면 무제한의 메모리가있는 경우 무차별 대입을 좀 더 밀어 붙일 수 있습니다. 잠재적으로 약 두 배의 모양으로 만들 수 있습니다. 이를 최대로 최적화하는 데 관련된 많은 세부 사항이 있지만, 무차별 대입이 당신을 가깝게 만들지 만 약간 부족한 경우 고려할 수있는 아이디어입니다. 여전히 지수 시간 알고리즘이므로 여전히 한계에 도달합니다.