CayleyR: Solving the TopSpin puzzle via cycle intersection

Resumen Técnico: CAYLEYR: RESOLVIENDO EL ROMPECABEZAS TOPSPIN MEDIANTE LA INTERSECCIÓN DE CICLOS

1. Planteamiento del Problema
El artículo aborda el desafío computacional de resolver el rompecabezas TopSpin$(n, k)$, un rompecabezas de permutación que involucra $n$ fichas en una pista circular y una ventana de torniquete de ancho $k$. El objetivo es transformar una permutación inicial dada en una permutación objetivo utilizando dos movimientos principales: un desplazamiento cíclico de toda la pista (Izquierda $L$ o Derecha $R$) y una inversión de las $k$ fichas dentro del torniquete ($X_k$).

Algebraicamente, el espacio de estados corresponde al grafo de Cayley $\Gamma(G, \{L, R, X_k\})$, donde $G$ es el grupo simétrico $S_n$ (para $k$ par) o el grupo alternante $A_n$ (para $k$ impar). Resolver el rompecabezas equivale a encontrar un camino entre dos vértices en este grafo. Los autores señalan que para $n > 10$, el espacio de estados ($n!$) crece super-exponencialmente, lo que hace que los algoritmos clásicos de búsqueda de caminos más cortos como la Búsqueda en Anchura (BFS) sean intratables. Además, el diámetro conjeturado del grafo es $\Theta(n^2)$, lo que agrava la dificultad.

2. Metodología: Intersección de Ciclos Iterativa (ICI)
El artículo propone una estrategia fundamentalmente diferente a la exploración de grafos nivel por nivel: el algoritmo de Intersección de Ciclos Iterativa (ICI). En lugar de expandir el frente de búsqueda de manera uniforme, el ICI genera "ciclos" aleatorios tanto desde el estado inicial como desde el estado final y busca una intersección entre estas familias de ciclos.

El algoritmo opera en rondas iterativas, manteniendo dos almacenes de estados ($S$ y $F$) que se expanden desde el estado inicial ($\sigma_s$) y el estado final ($\sigma_f$), respectivamente. Cada ronda consta de cuatro fases:

1. Generación de Combinaciones Aleatorias: Se genera un lote de secuencias de operaciones aleatorias (palabras) de longitud $\ell$.
2. Expansión de Ciclos: Para cada secuencia, el algoritmo computa el ciclo completo de estados generados mediante la aplicación repetida de la permutación compuesta hasta que esta regresa a la semilla. Todos los estados intermedios se registran en su respectivo almacenero.
3. Verificación de Intersección: El algoritmo busca estados compartidos entre $S$ y $F$ utilizando búsquedas indexadas por hash. Si se encuentra una intersección $\sigma^*$, el camino se reconstruye rastreando las cadenas de ciclos hacia los orígenes.
4. Selección de Puente: Si no ocurre una intersección, el algoritmo selecciona "estados puente" para reiniciar la expansión. Los estados en $S$ se clasifican por su distancia a $\sigma_f$, y los estados en $F$ se clasifican por su distancia a $\sigma_s$. Se consideran los 10 estados más cercanos en cada lado, y se elige uno de forma aleatoria de cada uno para servir como la nueva semilla para la siguiente ronda.

Reconstrucción y Refinamiento de Caminos:
Cuando se encuentra una intersección, el camino completo se ensambla encadenando los segmentos a través de todas las rondas. El artículo observa que el camino resultante no garantiza ser el más corto. Para abordar esto, el paquete incluye un paso de post-procesamiento (short path bfs) que realiza "saltos" de BFS locales de profundidad limitada para reemplazar los segmentos intermedios con rutas más cortas.

Estrategia Híbrida (Red de Transporte Basada en Hubs):
Para instancias más grandes, el artículo describe un enfoque híbrido (find_path_bfs). Este método primero construye "árboles de autopistas" dispersos utilizando BFS de profundidad limitada desde ambos extremos para identificar estados "hub". Luego, selecciona el par de hubs más cercano e invoca el algoritmo ICI para cerrar la brecha entre ellos. Esto reduce la distancia de búsqueda efectiva antes de que comience la fase estocástica de intersección de ciclos.

3. Contribuciones Clave
El artículo detalla tres contribuciones principales:

1. El Algoritmo ICI: Una novedosa estrategia de búsqueda de caminos para grafos de Cayley de grupos de permutación que se basa en la intersección de ciclos y la selección de puentes guiada por la distancia, en lugar de la expansión exhaustiva de niveles.
2. El Paquete cayleyR: Un paquete de R de código abierto (con un backend en C++ vía Rcpp) que implementa el algoritmo. Las características clave incluyen:
   • Almacenamiento de estados indexado por hash para inserción y búsqueda con tiempo amortizado $O(1)$.
     akceleración opcional de GPU mediante Vulkan para el procesamiento por lotes de transformaciones de estado y cálculos de distancia por pares.
   • "Coordenadas celestiales", un embebimiento geométrico de los conteos de operaciones sobre una esfera para visualización y posible uso heurístico futuro.
3. Demostraciones de Escalabilidad: Experimentos computacionales que muestran la capacidad del algoritmo para resolver instancias de TopSpin con $n$ hasta 20, una escala previamente difícil para los resolvedores exactos.

4. Resultados Experimentales
Los autores presentan comparativas en una estación de trabajo Linux (AMD Ryzen 5 5600) utilizando la versión 0.1.0/0.2.1 de cayleyR:

• Criterio de Clasificación: La elección de cómo clasificar las secuencias de operaciones aleatorias impacta significativamente el rendimiento. El criterio de "más único" (priorizando secuencias que visitan la mayor cantidad de estados distintos) logró la mayor tasa de éxito (83% en 12 instancias, $n=14\text{--}30$) pero a menudo produjo caminos muy largos. Por el contrario, las secuencias "más repetidas" ofrecieron una alta fiabilidad (75% de éxito) con caminos consistentemente cortos y tiempos de búsqueda rápidos (mediana < 1s).
• Escalabilidad con la Distancia de Mezcla (Scramble Distance): En TopSpin(14, 4) con distancias de mezcla variables ($n_{moves}=20\text{--}150$), el algoritmo resolvió todas las 14 instancias. El tiempo de búsqueda medio fue de 1.12 segundos, y el tiempo total (incluyendo el acortamiento del camino) promedió 2.3 segundos. El número de ciclos ICI requeridos no se correlacionó monótonamente con la distancia de mezcla, lo que resalta la naturaleza estocástica del método.
• Escalabilidad con el Tamaño del Rompecabezas ($n$): En instancias con $n=10\text{--}16$ y distancia de mezcla fija, los tiempos de búsqueda se mantuvieron por debajo de 0.5 segundos. Los autores atribuyen esto al hecho de que el algoritmo solo materializa una pequeña fracción del espacio de estados, lo que lo hace menos sensible al crecimiento super-exponencial de $n!$ en comparación con BFS.

5. Significado y Reivindicaciones
El artículo posiciona a cayleyR como una herramienta práctica para resolver rompecabezas de permutación que exceden los límites de la búsqueda exhaustiva clásica. Su importancia radica en:

• Eficiencia: Evita los cuellos de botella de memoria y tiempo de las bases de datos de patrones y de BFS mediante la generación de ciclos aleatorios e intersección basada en hash.
• Escalabilidad: Maneja con éxito instancias hasta $n=20$, donde el espacio de estados es $20!$.
• Modularidad: Aunque actualmente está diseñado para TopSpin, los autores afirman que el marco subyacente (intersección de ciclos, selección de puentes, almacenes indexados por hash) es aplicable a otros rompecabezas de permutación (por ejemplo, ordenamiento de panqueques, anillos húngaros), siempre que puedan modelarse como grafos de Cayley.

Los autores mantienen la modestia respecto a la optimalidad de las soluciones, reconociendo que el ICI no garantiza los caminos más cortos y que el embebimiento de "coordenadas celestiales" es actualmente una herramienta de visualización experimental más que una heurística probada para la estimación de distancia. Se propone como trabajo futuro explorar marcos de dualidad holográfica para la intersección de ciclos y generalizar la interfaz del generador para clases de rompecabezas más amplias.