Mahjong-solitaire solver algoritmo, que precisa de uma velocidade-up

Question

Estou desenvolvendo um solucionador de Mahjong-solitário e até agora, eu estou fazendo um bom trabalho. Contudo, não é tão rápido como eu gostaria que fosse por isso estou pedindo para qualquer otimização adicional técnicas de vocês pode saber de.

Todas as peças são conhecidos dos layouts, mas a solução não é. No momento, eu tenho alguns regras que garantem a remoção segura de certos pares de peças iguais (que não pode ser um obstáculo a uma possível solução).

Para maior clareza, um azulejo é livre quando ele pode ser escolhido qualquer momento e azulejo é solto, quando não ligados quaisquer outras peças em tudo.

• Se há quatro peças livres gratuitos disponíveis, removê-los imediatamente.
• Se há três peças que podem ser apanhados e pelo menos um deles é um ladrilho solto, remover os não-soltas.
• Se há três peças que podem ser apanhados e somente uma telha livre (duas perde o), remova o livre e um aleatório solto.
• Se há três telhas soltas disponível, remova dois deles (não importa quais).
• Uma vez que há quatro vezes exatamente o mesmo azulejo, se dois deles são deixados, removê-los já que eles são os únicos.

Meu pesquisas algoritmo de solução em vários segmentos de forma recursiva. Uma vez que um ramo é concluído (para uma posição onde não há mais movimentos) e não conduzir a uma solução, coloca a posição em um vector contendo os maus. Agora, cada vez que um novo ramo é lançado ele vai interagir via as posições ruins para verificar, se essa posição particular já foi verificado.
Este processo continua até que a solução seja encontrada ou todas as posições possíveis estão sendo verificados.

Isso funciona muito bem em um layout que contém, digamos, 36 ou 72 telhas. Mas quando há mais, este algoritmo se torna praticamente inútil devido à enorme quantidade de posições para busca de.

Assim, peço-lhe mais uma vez, se algum de vocês tem boas idéias como implementar mais regras para telha de remoção segura ou qualquer outra velocidade-up especial sobre o algoritmo.

Muito melhores cumprimentos, nhaa123

Answer 1

Eu não entendo completamente como seu solucionador funciona. Quando você tem uma escolha de movimentos, como você decide quais possibilidade de explorar pela primeira vez?

Se você pegar arbitrária, não é bom o suficiente - é apenas busca bruta, basicamente. Você pode precisar explorar as "melhores ramos" em primeiro lugar. Para determinar qual ramos são "melhores", você precisa de uma função heurística que avalia a posição. Então, você pode usar um dos populares algoritmos de busca heurística. Verifique estes:

• A * pesquisa
• Pesquisa feixe

(Google é seu amigo)

Answer 2

Alguns anos atrás, eu escrevi um programa que resolve placas Solitaire Mahjongg por espreitar. Usei-o para examinar um milhão de tartarugas (levou um dia ou algo no meio de um computador: tinha dois núcleos). E parecia que cerca de 2,96 por cento deles não pode ser resolvido

http://www.math.ru.nl/~debondt/mjsolver. html

Ok, isso não era o que você pediu, mas você pode ter um olhar para o código para encontrar algumas heurísticas de poda em que não atravessam a sua mente até agora. O programa não usa mais do que alguns megabytes de memória.

Answer 3

Em vez de um vector contendo as posições "maus", use um conjunto que tem um tempo de pesquisa constante em vez de uma linear.