Acabei de receber uma imagem ... A imagem abaixo do meu jogo mostra alguns blocos escuros, que foram reconhecidos como parte de uma forma de "T". Como pode ser visto, o código escureceu os blocos com as manchas vermelhas e não viu as formas "T" com os contornos verdes.
Meu código percorre x / y, marca os blocos como usados, gira a forma, repete, muda de cor, repete.
Comecei a tentar corrigir essa verificação com grande apreensão. A ideia atual é:
- faça um loop pela grade e anote todas as ocorrências de padrão (NÃO marcando os blocos conforme usados) e colocando-os em uma matriz
- faça um loop pela grade novamente, dessa vez observando quais blocos são ocupados por quais padrões e, portanto, quais são ocupados por vários padrões.
- circulando pela grade novamente, desta vez observando quais padrões obstruem quais padrões
Isso parece certo ... O que eu faço agora?
Eu acho que teria que
- tente várias combinações de formas conflitantes, começando pelas que obstruem a maioria dos outros padrões primeiro. Como abordar este?
- use o racional que diz que tenho 3 formas conflitantes, ocupando 8 blocos, e as formas são 4 blocos cada, portanto, só posso ter no máximo duas formas.
(Também pretendo incorporar outras formas, e provavelmente haverá uma ponderação de pontuação que precisará ser considerada ao passar pelas formas conflitantes, mas isso pode ser outro dia)
Não acho que seja um problema de empacotamento de lixeira, mas não sei ao certo o que procurar. Espero que faça sentido, obrigado por sua ajuda
EDIT Apesar da clareza da pergunta, todos parecem ter entendido, sim,
Quero encontrar o máximo de formas "T" em cada cor
(porque se eu lhe desse pontos por dois e você fizesse três, você ficaria um pouco irritado)
Respostas:
Deixe-me ver se eu entendi direito, os blocos marcados em vermelho eram azuis e o algoritmo encontrou uma forma de T e os marcou em vermelho, está correto? Seu objetivo é encontrar o maior número possível de formas em T com os mesmos blocos coloridos, correto até agora, espero. Atualmente, você os marca depois de encontrá-los e isso diminui a utilidade do algoritmo (já que você pode estar perdendo a solução ideal). Você planeja procurar todas as formas e depois escolher quais usar e qual não usar. Estou correto até agora? Porque você deseja maximizar a quantidade de blocos contidos nas formas T quando o algoritmo é concluído.
Se eu estiver correto, a seguir, é a solução ideal para sua situação na minha opinião.
Usaremos a Programação Linear Inteira.
Acredito que usei este no passado:
http://sourceforge.net/projects/lpsolve/
http://lpsolve.sourceforge.net/5.5/Java/README.html
(Você pode fazê-lo funcionar com muitas linguagens, eu usei com PHP, Java e C)
O que faremos é registrar todas as formas possíveis de T no quadro e usar o ILP para maximizar a quantidade de blocos cobertos. ILP é exponencialmente complexo. Considerando o tamanho da sua placa, isso não será um problema. Fiz perguntas min / max muito mais complicadas em gráficos com ILP e demorou apenas uma fração de segundo para concluir e de 30 a 90 segundos com centenas de vértices (no seu caso, cai na fração de segundo).
O que eu recomendaria fazer:
0 <= Bi <= 1
) Como os valores são números inteiros, isso deixa 0 ou 1.Bi + Bj <= 1
)Este é um conhecimento valioso, usei resolvedores lineares frequentemente para projetos de trabalho.
O ILP é basicamente uma maneira de resolver problemas de seleção nos quais você deseja atingir um máximo ou um mínimo para alguma função linear.
Você pode ler mais aqui, usando Programação Linear Inteira e Programação Linear é a mesma para o programador, apenas que Integer é muito mais complexo para o computador, o que pode resultar em longos tempos de execução. Não no seu caso, é muito simples e, no pior dos casos, leva apenas menos de milissegundos.
Eu acho que você poderia ler mais aqui:
http://en.wikipedia.org/wiki/Integer_linear_programming#Integer_unknowns
Isso explica bem:
http://fisher.osu.edu/~croxton_4/tutorial/
É basicamente um solucionador de problemas de decisão, como tomar decisões que maximizam o resultado desejado. Isso assume que a função que julga o resultado é linear e, no seu caso atual específico, é. A função que avalia o resultado nesse caso resume os blocos de todas as formas em T que você decidiu escurecer.
Matematicamente, como definir as variáveis: no nosso caso atual, os booleanos (escureci a forma de T com o índice i ou não) com os valores ótimos para maximizar o resultado que queremos: escurecendo o máximo de blocos possível sem escurecer as formas de interseção em T. Contanto que o resultado desejado possa ser calculado com uma função linear quando você tiver todas as variáveis definidas, ele o resolverá. No nosso caso, verificamos quais formas T escurecemos e somamos os blocos que cobrem.
Sei que isso não é trivial, portanto, se você optar por dar o salto, fique à vontade para comentar e eu o elaborarei.
fonte
Depois de ter uma lista de todas as formas em T (possivelmente sobrepostas) ocorrendo em sua grade, o que resta é um problema de empacotamento máximo definido .
Em geral, esse é um problema completo do NP. No entanto, sua grade é pequena o suficiente (e normalmente se divide em subproblemas independentes ainda menores), para que seja possível obter soluções exatas.
Adendo: Aqui está um algoritmo de pesquisa de retrocesso básico que pode fazer o truque:
Aqui,
{X, Y, Z}
indica o conjunto contendo os elementosX
,Y
eZ
(com{}
sendo o conjunto vazio), e|Q|
indica o tamanho do conjuntoQ
.Na função recursiva, o conjunto
A
contém as formas disponíveis para a solução restante,S
as formas no candidato atual à solução eM
é a solução máxima até o momento (que você pode armazenar como uma variável global em vez de retorná-la ao backup). cadeia de chamadas). A importante otimização está na linha marcada com// upper bound
, que remove galhos da árvore de pesquisa que possivelmente não podem retornar uma solução melhor queM
.(Na verdade, como sabemos que cada forma de T contém exatamente quatro locais, um limite superior muito melhor pode ser obtido substituindo
|B|
-se pelo número de locais distintos cobertos pelas formasB
, dividido por quatro e arredondado para baixo (e da mesma forma para|A|
o linha marcada com// shortcut
). Contudo, o algoritmo conforme indicado acima funciona para coleções arbitrárias de formas.)Uma possível otimização adicional, que eu não implementei acima, seria verificar no início da função recursiva se
A
divide em vários subconjuntos independentes, no sentido de que nenhuma forma em subconjuntos diferentes se sobreponha e, em caso afirmativo, aplique o algoritmo para cada um dos subconjuntos separadamente. (De qualquer forma, você definitivamente desejará fazer isso pelo menos uma vez no nível superior antes de chamar o algoritmo recursivo.) Classificar as formasA
adequadamente antes de fazer um loop sobre elas, por exemplo, em ordem crescente pelo número de formas sobrepostas, também pode ajudar .fonte