algoritmo de solucionador de mahjong-solitario, que necesita una velocidad de marcha

Question

Estoy desarrollando un solucionador de Mahjong Solitaire-y hasta ahora, que estoy haciendo bastante bien. Sin embargo, no es tan rápido como me gustaría que fuera así que estoy pidiendo ninguna optimización adicional técnicas de ustedes puede saber de.

Todos los azulejos se conocen a partir de los diseños, pero la solución no lo es. Por el momento, tengo unos pocos reglas que garantizan una extracción segura de ciertos pares de fichas mismo (que no puede ser un obstáculo para posible solución).

Para mayor claridad, un azulejo es libre cuando se puede tomar en cualquier momento y el azulejo está suelto, cuando no ligado cualquier otro azulejos en absoluto.

• Si hay cuatro fichas libres libres disponibles, eliminarlos inmediatamente.
• Si hay tres fichas que pueden ser recogidos y por lo menos uno de ellos es una baldosa floja, retire los no sueltos.
• Si hay tres fichas que pueden ser recogidos y sólo una baldosa libre (dos PERDIDAS), retire el libre y al azar floja.
• Si hay tres baldosas sueltas disponibles, eliminar dos de ellos (no importa cuáles).
• Puesto que es cuatro veces el mismo azulejo exacta, si dos de ellos se quedan, eliminarlos, ya que son los únicos que quedan.

Mi algoritmo de solución búsquedas en múltiples hilos de forma recursiva. Una vez que finaliza una rama (a una posición donde no hay más movimientos) y no conduce a una solución, se pone en la posición de un vector que contiene los malos. Ahora, cada vez que una nueva rama se puso en marcha que va a iterar a través de las malas posiciones para comprobar si esa posición en particular se ha comprobado ya.
Este proceso continúa hasta que la solución se encuentra o se están comprobado todas las posiciones posibles.

Esto funciona muy bien en una disposición que contiene, por ejemplo, 36 o 72 piezas. Pero cuando hay más, este algoritmo se vuelve bastante inútil debido a la enorme cantidad de posiciones a buscar.

Por lo tanto, te pido una vez más, si alguno de ustedes tiene buenas ideas la forma de aplicar más reglas para la baldosa-extracción segura o cualquier otra aceleración particular en relación con el algoritmo.

Muy cordial saludo, nhaa123

Answer 1

No entiendo completamente cómo funciona el solucionador. Cuando usted tiene una opción de movimientos, ¿cómo decidir qué posibilidad de explorar en primer lugar?

Si usted escoge arbitraria, no es lo suficientemente bueno - es sólo la búsqueda bruta, básicamente. Puede que sea necesario para explorar los "mejores" ramas en primer lugar. Para determinar qué ramas están "mejor", se necesita una función heurística que evalúa una posición. A continuación, puede utilizar uno de los algoritmos heurísticos de búsqueda populares. Verlas:

• búsqueda A *
• Búsqueda haz

(Google es tu amigo)

Answer 2

Hace algunos años, escribí un programa que resuelve tableros Solitaire Mahjongg al espiar. Lo utilicé para examinar un millón de tortugas (tomó un día o algo en medio de un ordenador: tenía dos núcleos). Y parecía que alrededor del 2,96 por ciento de ellos no puede ser resuelto

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

Ok, eso no era lo que pidieron, pero es posible que tenga una mirada en el código para encontrar algunas heurísticas de poda en los mismos que no cruzaron su mente hasta el momento. El programa no utiliza más de unos pocos megabytes de memoria.

Answer 3

En lugar de un vector que contiene las posiciones de "malos", utilizar un conjunto que tiene un tiempo de búsqueda constante en lugar de uno lineal.