algoritmo solutore Mahjong Solitaire-, che ha bisogno di una velocità-up

Question

sto sviluppando un risolutore di Mahjong Solitaire-e finora, sto facendo abbastanza bene. Però, non è così veloce come vorrei che fosse così sto chiedendo per qualsiasi ulteriore ottimizzazione tecniche di voi ragazzi potrebbe sapere di.

Tutte le tessere sono noti i layout, ma la soluzione non è. Al momento, ho pochi regole che garantiscono la rimozione di sicurezza di alcune coppie di stesse mattonelle (che non può essere un ostacolo alla possibile soluzione).

Per chiarezza, una piastrella è libero quando può essere raccolto in qualsiasi momento e piastrelle è allentato, quando non vincolata altre tessere affatto.

• Se ci sono quattro tessere libere libere a disposizione, rimuoverli immediatamente.
• Se ci sono tre tessere che può essere ritirato e almeno uno di loro è una tegola sciolto, rimuovere quelli non sciolti.
• Se ci sono tre tessere che possono essere raccolti e solo una tessera gratuita (due perde), togliere il libero e casuale allentato.
• Se ci sono tre piastrelle sciolto disponibili, rimuovere due di loro (non importa quali).
• Poiché non v'è quattro volte la stessa piastrella esatto, se due di loro sono rimasti, rimuoverli dato che sono gli unici rimasti.

Il mio algoritmo di soluzione ricerche in più thread in modo ricorsivo. Una volta che un ramo è finito (una posizione in cui non v'è più mosse) e non ha portato ad una soluzione, mette la posizione in un vettore contenente cattivi. Ora, ogni volta che un nuovo ramo è lanciato che sarà iterare attraverso le cattive posizioni di verificare, se quella particolare posizione è stato già controllato.
Questo processo continua fino a quando viene trovata una soluzione o tutte le posizioni possibili vengono controllati.

Questo funziona bene su un layout che contiene, per esempio, 36 o 72 tessere. Ma quando c'è di più, questo algoritmo diventa praticamente inutile a causa della enorme quantità di posizioni da ricercare tra.

Quindi, vi chiedo ancora una volta, se qualcuno di voi ha buone idee come implementare più regole per la tegole-rimozione sicura o qualsiasi altro particolare speed-up per quanto riguarda l'algoritmo.

Molto cordiali saluti, nhaa123

Answer 1

Non del tutto a capire come funziona il vostro solver. Quando si dispone di una scelta di mosse, come si fa a decidere quali possibilità di esplorare in primo luogo?

Se si sceglie arbitraria, non è abbastanza buono - è solo ricerca bruta, in fondo. Potrebbe essere necessario esplorare i "rami migliori" prima. Per determinare quali rami sono "migliore", è necessario un funzione euristica che valuta una posizione. Quindi, è possibile utilizzare uno dei popolari algoritmi di ricerca euristici. Controllare questi:

• A * Ricerca
• Ricerca del fascio

(Google è tuo amico)

Answer 2

Alcuni anni fa, ho scritto un programma che risolve tavole Solitaire Mahjongg per sbirciare. L'ho usato per esaminare un milione di tartarughe (ha preso un giorno o qualcosa in mezzo un computer: aveva due core). E sembrava che circa il 2,96 per cento di loro non può essere risolto

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

Ok, che non era quello che hai chiesto, ma si potrebbe avere uno sguardo al codice per trovare alcune euristiche di potatura in esso che non ha attraversato la tua mente finora. Il programma non usa più di qualche megabyte di memoria.

Answer 3

Invece di un vettore che contiene le posizioni "cattivi", utilizzare un insieme che ha un tempo di ricerca costante anziché lineare.