Indexación en una base de datos de patrones: solución de cubo de Rubik óptimo de Korf

11

Como proyecto divertido, he estado trabajando en una implementación en C # de Richard Korf's: Encontrar soluciones óptimas para el cubo de Rubik usando bases de datos de patrones.

https://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/korfrubik.pdf

De hecho, lo tengo funcionando, solo estoy tratando de mejorar mi solución.

Una cosa que Korf ve en su artículo es cómo almacena e indexa en las bases de datos de patrones. Idealmente, creo que queremos usar una instancia del cubo de Rubik para generar un índice en una matriz.

Mi pregunta es sobre la mejor manera de generar este índice.

Mi solución es generar un hash perfecto mínimo. Esto implica mantener TODOS los cubos en la memoria hasta que haya descubierto toda la base de datos de patrones y luego generar un hash perfecto mínimo basado en eso. El MPH tarda un par de horas en ejecutarse dependiendo del tamaño de la base de datos de patrones, pero solo necesito hacerlo una vez, ya que lo guardo en el disco. Al final, puedo tirar los cubos y almacenar solo el MPH. De esa manera, puedo tomar un cubo de rubik aleatorio, aplicar el patrón y luego buscar el índice de matriz en el MPH para obtener una longitud de solución estimada.

Creo que Korf y Shultz describen una mejor manera de determinar el índice del cubo en su artículo de 2005 llamado "Búsqueda a gran escala en primer lugar"

https://www.aaai.org/Papers/AAAI/2005/AAAI05-219.pdf

Este artículo describe un algoritmo para generar un índice basado en el ordenamiento lexicográfico de una permutación. Básicamente, puede tomar la permutación {1, 2, 3} y calcular que es la más pequeña con un índice de 0. {1, 3, 2} es la siguiente con un índice de 1 y así sucesivamente.

Siento que debería poder aplicar este algoritmo al cubo de rubik para obtener su índice dentro de una base de datos de patrones, pero me resulta difícil descubrir cómo funcionaría en la práctica.

La base de datos de patrones de esquinas únicas, por ejemplo, contiene todos los cubos de rubik a los que se les han quitado sus pegatinas de borde. Hay exactamente 88,179,840 cubos en este conjunto. Cualquier cubito de esquina en un cubo de rubik puede estar en uno de los 24 estados diferentes. El estado del cubo de la octava esquina se puede calcular en función de los otros 7, por lo que los cubos en la base de datos de patrones de las esquinas tienen 7 valores entre 0 y 23

por ejemplo, {0, 3, 6, 9, 12, 15, 18, 21} define el cubo "resuelto" con todos los adhesivos de borde quitados.

si giro la cara frontal 90 grados, la permutación podría ser: {0, 3, 11, 23, 12, 15, 8, 20}

¿Hay alguna manera de obtener un índice de este tipo de permutaciones?

Cosmosis
fuente
Probablemente encuentres esto interesante.
Tom van der Zanden
¡interesante! dices que él "mira por encima" algo en el periódico. Sería mejor ser más específico sobre la sección que no está "desarrollada". también dices que lo tienes funcionando. ¿Cuál es su implementación de indexación inicial? ¿Es este un proyecto escolar? sugerir más chat de informática en él. También, por ejemplo, bloguear al respecto o abrir el código puede ser útil para otros y dar más detalles. Además, el documento no parece referirse a ninguna función de hash ...
vzn
Implementé el algoritmo de Korf: github.com/benbotto/rubiks-cube-cracker . A mí también me pareció difícil la indexación, así que escribí un artículo al respecto en Medium: medium.com/@benjamin.botto/…
avejidah

Respuestas:

6

No explica qué significan los números del 0 al 23, pero de acuerdo con esta respuesta , puede representar el estado de las esquinas utilizando ocho pares , donde es una permutación de , , y (por ejemplo) está determinado por . En total, esto da grados de libertad. Suponiendo que puede descomponer sus en pares , puede convertir fácilmente una posición en un índice codificando por separado la permutación(pi,oi)(p0,,p7)(0,,7)oi{0,1,2}o7o0,,o68!37=88179840{0,,23}( p 0 , ... , p 7 ) o 0 , ... , o 6 3 7 p + o 8 ! o + p(pi,oi)(p0,,p7)(que el documento AAAI explica cómo hacerlo) y los valores , que puede codificar en la base 3. Poniendo los dos valores juntos de la manera obvia (por ejemplo, u ), obtenemos un índice.o0,,o637p+o8!o+p

Yuval Filmus
fuente
Hola Yuval, gracias por el comentario. Para mí, de 0 a 23 es cómo identifico la posición / orientación única en la que puede estar un cubo de esquina. 8 posiciones por 3 orientaciones por posición = 24. Afortunadamente, puedo dividir fácilmente este valor en tuplas de posición / orientación separadas. Su respuesta me llevó a este código, que es una implementación del algoritmo que está describiendo. github.com/brownan/Rubiks-Cube-Solver/blob/master/cornertable.c Necesitaré hacer un poco de trabajo para hacer esto más genérico (para que pueda manejar patrones diferentes que "esquinas solamente"), pero ahora Estoy en el camino correcto gracias!
Cosmosis