Como posso otimizar minha solução de força bruta para esse problema?
Estou trabalhando em uma solução para o problema explicado abaixo. Estou usando força bruta, cheguei ao ponto em que as soluções são proibitivas, então preciso otimizar mais (se possível). Claro, será ainda melhor se houver uma maneira melhor de resolver o problema (não força bruta).
Existe algo que eu possa fazer para melhorar minha solução ou referência que eu possa examinar (problemas semelhantes etc.)?
O problema
Começamos com uma placa retangular. Cada célula pode estar em N estados, e o estado inicial de cada célula é aleatório (0 <= estado < N) para cada célula. Também temos várias formas, todas cabem dentro da prancha. Toda forma é contínua.
Cada forma deve ser colocada uma vez (e apenas uma vez) no tabuleiro. Quando uma forma é colocada, cada célula que pertence à forma terá seu valor aumentado em 1. Se o valor do tabuleiro em qualquer célula atingir N, ele é alterado para 0.
O objetivo é encontrar as posições que cada forma deve ser colocada para que o tabuleiro final tenha todas as células com valor 0. Sempre há pelo menos uma solução. Vamos supor que o problema seja gerado partindo da placa acabada e aplicando formas aleatórias em posições aleatórias.
O tamanho do tabuleiro, o número de estados N e o número de formas são a configuração do jogo e continuam aumentando (em taxas diferentes) para cada 'nível'.
O que estou fazendo atualmente
Eu sou capaz de resolver o problema até certo tamanho usando apenas força bruta. Eu tenho algumas otimizações no lugar. Cheguei a um ponto em que a solução é proibitiva, então gostaria de melhorar minha lógica.
A primeira coisa que estou fazendo é ordenar a forma de maior para menor, a menor será movida nas iterações internas. A suposição (que não provei, mas testei para ser mais rápida) é que é melhor mover mais as formas menores, pois elas têm uma chance maior de gerar uma solução.
Em segundo lugar, para formas repetidas, evito verificar todas as permutações, pois elas produzem o mesmo resultado. Também verifico apenas um conjunto de posições quando um par de formas iguais se sobrepõe (já que todas as sobreposições produzem o mesmo resultado).
Uma otimização final que acho que vai ajudar muito, mas ainda estou implementando é: a cada forma da sequência, conte o total de células nas formas que faltam ser movidas. Esse número, menos o total de viradas de células necessárias para obter uma placa finalizada, deve ser um múltiplo de N. Caso contrário, não adianta forçar brutalmente as posições restantes das formas e devemos reposicionar uma forma em um loop externo.
Detalhes extras
Estou interessado em quaisquer outras dicas sobre como otimizar isso. Algoritmos conhecidos, até mesmo uma boa nomenclatura para esse conjunto de problemas, que eu possa usar para pesquisar mais, seria ótimo.
Respostas
Programação linear inteira
Seu problema pode ser formulado da seguinte maneira: temos vetores$v_{i,j} \in (\mathbb{Z}/N\mathbb{Z})^d$, onde a placa tem$d$células, e o objetivo é, dado um vetor$c \in (\mathbb{Z}/N\mathbb{Z})^d$, encontre uma função$f$de modo a$\sum_i v_{i,f(j)}=c$. Este problema poderia então ser resolvido por programação linear inteira. Isso está relacionado a um$d$-dimensional subset-sum problema, então você também pode encontrar outros algoritmos para soma de subconjuntos multidimensionais e experimentá-los também.
Como o formulamos dessa maneira? Se a grade tiver$d$células, podemos pensar em uma forma como um$d$-vetor de 0's e 1's, com 1's nas células cobertas pela forma. Cada forma pode ser colocada em várias posições diferentes, gerando diferentes vetores.$v_{i,j}$corresponde ao$j$o lugar onde a forma$i$pode ser colocado.$c$corresponde aos números originalmente na grade (bem, a negação desses números, módulo$N$). Toda aritmética é feita módulo$N$.
Força bruta ligeiramente mais inteligente
Como alternativa, aqui está uma maneira de melhorar um pouco a força bruta, trocando memória por tempo. Suponha que você tenha$k$formas. Comece enumerando todas as maneiras de colocar o primeiro$k/2$formas em um quadro vazio de todos os zeros e armazene todas as posições resultantes em uma tabela de hash ou lista classificada. Em seguida, enumere todas as maneiras de colocar o último$k/2$formas na posição inicial e procure cada uma das posições resultantes na tabela de hash ou na lista classificada. Se você encontrar alguma correspondência, isso produzirá uma solução. Isso permitirá que você empurre a força bruta um pouco mais - potencialmente para cerca do dobro de formas - se você tiver uma quantidade ilimitada de memória. Há muitos detalhes envolvidos na otimização ao máximo, mas é uma ideia que você pode considerar se a força bruta o aproximar, mas ficar um pouco aquém. Ainda é um algoritmo de tempo exponencial, portanto ainda atingirá um limite.