🤖 machine learning

CayleyPy RL: Pathfinding and Reinforcement Learning on Cayley Graphs

Este artículo presenta el proyecto CayleyPy, que combina el aprendizaje por refuerzo con métodos de distancia de difusión para resolver de manera eficiente el problema de búsqueda de caminos en grafos de Cayley masivos, superando con éxito herramientas clásicas como GAP, proporcionando pruebas sólidas de la conjetura OEIS-A186783 sobre el diámetro del grupo simétrico y estableciendo nuevos límites teóricos al tiempo que invita a la participación de la comunidad a través de desafíos en Kaggle.

Autores originales: A. Chervov, M. Obozov, A. Soibelman, S. Lytkin, I. Kiselev, S. Fironov, A. Lukyanenko, A. Dolgorukova, A. Ogurtsov, F. Petrov, S. Krymskii, M. Evseev, L. Grunvald, D. Gorodkov, G. Antiufeev, G. Verbii

Publicado 2026-05-19

📖 6 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: A. Chervov, M. Obozov, A. Soibelman, S. Lytkin, I. Kiselev, S. Fironov, A. Lukyanenko, A. Dolgorukova, A. Ogurtsov, F. Petrov, S. Krymskii, M. Evseev, L. Grunvald, D. Gorodkov, G. Antiufeev, G. Verbii, V. Zamkovoy, L. Cheldieva, I. Koltsov, A. Sychev, A. Eliseev, S. Nikolenko, N. Narynbaev, R. Turtayev, N. Rokotyan, S. Kovalev, A. Rozanov, V. Nelin, S. Ermilov, L. Shishina, D. Mamayeva, A. Korolkova, K. Khoruzhii, A. Romanov

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

La Gran Imagen: Encontrar el Camino Más Corto a Casa en un Laberinto de Espejos

Imagina que estás en un laberinto gigante e infinito. Pero este no es un laberinto normal con paredes; es un laberinto hecho de reglas. Cada vez que das un paso, sigues una regla específica que cambia tu posición. En matemáticas, esto se llama un grafo de Cayley.

El objetivo de este artículo es resolver un tipo específico de laberinto: el laberinto LRX. Este laberinto se construye utilizando las reglas de barajar una baraja de cartas (o una permutación de números).

Regla L: Desplaza todo un espacio hacia la izquierda.
Regla R: Desplaza todo un espacio hacia la derecha.
Regla X: Intercambia los dos primeros elementos.

El desafío es: Si comienzas con una baraja de cartas en un orden desordenado, ¿cuál es la secuencia más corta de movimientos Izquierda, Derecha e Intercambio para devolverlas al orden perfecto?

El Problema: El Laberinto es Demasiado Grande para los Humanos (y las Computadoras Antiguas)

Para una baraja pequeña de cartas, un humano o un programa informático estándar (como el famoso software matemático GAP) puede encontrar la solución. Pero a medida que aumenta el número de cartas ( $n$ ), el número de arreglos posibles explota.

Para $n=20$ , el laberinto es enorme.
Para $n=100$ , el laberinto es tan grande que tiene más caminos que átomos en el universo.

Los antiguos programas informáticos se quedan atascados. Intentan mapear cada camino individual, se quedan sin memoria y se rinden. Los autores querían ver si la Inteligencia Artificial (IA) podía actuar como un explorador inteligente para encontrar el camino a través de estos laberintos masivos sin mapear cada centímetro.

La Solución: Enseñarle a una IA a "Adivinar" el Camino

Los autores construyeron un sistema llamado CayleyPy RL. Imagínalo como entrenar a un robot para navegar el laberinto. Utilizaron un método llamado Aprendizaje por Refuerzo (RL).

Así es como entrenaron al robot, usando una analogía sencilla:

1. El "Calentamiento" (Distancia de Difusión)
Imagina que sueltas una gota de tinta en un vaso de agua. La tinta se extiende aleatoriamente. Si quieres saber qué tan lejos está un punto específico del centro, puedes ver cuánto tarda la tinta en llegar a él.

La IA primero aprendió observando millones de "caminatas aleatorias" (como la tinta extendiéndose). No conocía el camino más corto, pero aprendió una "sensación" de distancia. Sabía: "Si estoy aquí, generalmente toma unas 50 pasos aleatorios para llegar a casa".
Esto le dio a la IA un mapa aproximado, pero no era perfecto.

2. El "Entrenamiento Inteligente" (Aprendizaje por Refuerzo)
A continuación, enseñaron a la IA a ser más inteligente. En lugar de solo adivinar basándose en caminatas aleatorias, utilizaron una técnica llamada Deep Q-Learning.

Imagina que la IA está jugando un juego donde recibe una "penalización" por cada paso que da. Quiere llegar a la línea de meta con la menor cantidad de penalizaciones.
La IA probó diferentes movimientos, vio cuáles la acercaban más y ajustó su cerebro (red neuronal) para hacer mejores predicciones.
La Innovación: Combinaron la intuición de la "tinta extendiéndose" con la lógica de "jugar al juego". Esto ayudó a la IA a evitar quedar atrapada en callejones sin salida (mínimos locales) que usualmente atrapan a algoritmos más simples.

3. La "Búsqueda en Haz" (El Equipo de Exploradores)
Esta es la parte más crítica. Imagina que envías a un explorador al laberinto. Si toma un giro incorrecto, lo pierdes.

En cambio, los autores enviaron un equipo de exploradores (un "haz").
En cada intersección, el equipo se divide. Mantienen las 10.000 rutas más prometedoras y descartan las malas.
Al mantener un equipo enorme (millones de rutas en algunos casos), la IA asegura que, incluso si la mayoría de los exploradores se pierden, al menos uno de ellos encontrará el camino perfecto y más corto.

El "Truco Mágico" (El Truco X)

Los autores descubrieron un pequeño atajo divertido. En su código, añadieron una sola línea de lógica:

Si las dos primeras cartas ya están en el orden correcto, no las intercambies.

Suena obvio para un humano, pero para una computadora fue un cambio de juego. Esta pequeña regla, a la que llamaron el "truco X", permitió que su IA resolviera laberintos con 100 cartas ( $n=100$ ).

Sin el truco: La IA solo podía manejar unas 40 cartas.
Con el truco: Manejó más de 100 cartas, superando al antiguo software informático (GAP) que se bloqueaba alrededor de las 20 cartas.

¿Qué Demostraron? (La Parte Matemática)

Más allá de simplemente construir un solucionador rápido, utilizaron su IA para hacer descubrimientos sobre las matemáticas de estos laberintos:

La Conjetura del "Número de Dios": Hay una famosa suposición en matemáticas de que la barajada más difícil posible de $n$ cartas requiere exactamente $n(n-1)/2$ movimientos. La IA probó esto para números enormes y nunca encontró una barajada que fuera más difícil que esto. Apoya fuertemente la idea de que esta fórmula es el límite absoluto.
La Barajada "Más Larga": Identificaron la única barajada más caótica posible (el "elemento más largo") y demostraron exactamente cómo descomponerla en movimientos.
Nuevos Límites: Demostraron matemáticamente que el laberinto no puede ser más pequeño de cierto tamaño ni más grande que otro tamaño, estrechando significativamente la respuesta.
La Forma del Laberinto: Descubrieron que si cuentas cuántas barajadas existen a cada distancia del inicio, los números no siguen una curva de campana perfecta (como una distribución normal). En cambio, siguen una forma extraña y desequilibrada llamada distribución Gumbel.

Los Resultados: IA vs. La Vieja Guardia

El artículo compara su nuevo método de IA contra el sistema de álgebra computacional estándar GAP:

GAP: Puede resolver hasta ~20 cartas. Toma horas o días. Los caminos que encuentra a menudo son largos e ineficientes.
CayleyPy RL (IA): Puede resolver hasta ~100 cartas. Es mucho más rápido. Encuentra caminos que están muy cerca del camino más corto teóricamente posible.

Resumen

Los autores crearon un sistema de IA inteligente que trata problemas matemáticos complejos como un laberinto gigante. Al combinar adivinanzas aleatorias con aprendizaje inteligente y enviando un enorme "equipo" de exploradores virtuales, pueden navegar laberintos que son demasiado grandes para las computadoras tradicionales. Incluso encontraron un pequeño "código de trampa" (el truco X) que les permite resolver problemas 5 veces más grandes que antes, mientras demuestran simultáneamente nuevos hechos matemáticos sobre cómo están estructurados estos laberintos.

También han puesto su código y desafíos en una plataforma llamada Kaggle, invitando a otras personas a intentar superar sus récords y ayudar a resolver versiones aún más difíciles de estos acertijos.

Resumen Técnico: CayleyPy RL: Búsqueda de Caminos y Aprendizaje por Refuerzo en Grafos de Cayley

Planteamiento del Problema
El artículo aborda el problema de la búsqueda de caminos en grafos de Cayley finitos extremadamente grandes, centrándose específicamente en el grupo simétrico $S_n$ generado por desplazamientos cíclicos izquierdos ( $L$ ), desplazamientos cíclicos derechos ( $R$ ) y una transposición de los dos primeros elementos ( $X$ ). Esta configuración, conocida como el grafo de Cayley LRX, corresponde a la secuencia OEIS A186783. El desafío matemático central consiste en descomponer un elemento del grupo en el producto más corto posible de generadores (encontrar el camino más corto en el grafo). Este problema es NP-duro para grafos de Cayley finitos genéricos. Los sistemas de álgebra computacional clásicos, como GAP, dependen del algoritmo de Schreier-Sims, que a menudo produce caminos exponencialmente largos y falla al manejar grupos con tamaños superiores a $10^{30}$ (aproximadamente $n \approx 20$ para $S_n$ ). Los autores tienen como objetivo desarrollar enfoques eficientes basados en inteligencia artificial capaces de manejar grafos con tamaños hasta $10^{70}$ (por ejemplo, $n \approx 40$ a $100$) mientras producen caminos casi óptimos u óptimos.

Metodología
Los autores proponen una metodología híbrida que combina Aprendizaje por Refuerzo (RL), específicamente Deep Q-Learning (DQN), con una estrategia de pre-entrenamiento basada en distancias de difusión.

Marco de Aprendizaje por Refuerzo: El problema de búsqueda de caminos se enmarca como encontrar el camino más corto desde un estado $s$ hasta el elemento identidad $e$ . Esto se modela utilizando la ecuación de Bellman, donde la función de distancia $d(s)$ satisface $d(s) = 1 + \min_{t \in N(s)} d(t)$ . El DQN estándar se adapta para aproximar esta función de valor utilizando redes neuronales.
Pre-entrenamiento por Distancia de Difusión: Para abordar el problema de la "recompensa dispersa" y el ruido inherente a la inicialización estándar del DQN, los autores introducen una fase de "calentamiento". Generan datos de entrenamiento mediante paseos aleatorios (difusión) que comienzan desde el objetivo. Una red neuronal se entrena primero para predecir el número de pasos en estos paseos aleatorios (distancia de difusión).
DQN Modificado: La red pre-entrenada se ajusta finamente utilizando un algoritmo DQN modificado. Crucialmente, los objetivos de actualización de Bellman se recortan en función del paso de tiempo $k$ en el que un estado fue visitado por primera vez durante la generación del paseo aleatorio. Esto evita que la red sobreestime las distancias y estabiliza el entrenamiento.
Búsqueda en Haz Guiada: Una vez que la red neuronal está entrenada para estimar distancias, sirve como función heurística para un algoritmo de búsqueda en haz. La búsqueda en haz mantiene un número fijo ( $W$ ) de los estados más prometedores en cada paso, expandiendo sus vecinos y seleccionando los mejores $W$ basándose en las predicciones de la red. Esto evita quedar atrapado en mínimos locales, un modo de fallo común en la búsqueda voraz.
El "Truco X": Se introduce una modificación heurística específica para los generadores LRX. Si los dos primeros elementos de una permutación ya están ordenados, el generador $X$ (que los intercambia) se excluye del conjunto de vecinos. Esta modificación de una sola línea reduce drásticamente el espacio de búsqueda y mejora los tiempos de mezcla.
No Retroceso: Los autores incorporan restricciones de no retroceso tanto en la generación de paseos aleatorios como en la búsqueda en haz para reducir la varianza en las estimaciones de distancia y prevenir el estancamiento en mínimos locales.

Contribuciones Clave

Avances Algorítmicos: El artículo presenta una combinación novedosa de pre-entrenamiento por distancia de difusión y DQN modificado. Este enfoque supera las limitaciones del DQN estándar (recompensas dispersas, objetivos ruidosos) y supera a los métodos clásicos.
Puntos de Referencia de Rendimiento: Los métodos propuestos encuentran exitosamente caminos para grafos de Cayley LRX hasta $n \approx 44$ sin conocimiento previo y hasta $n \approx 100$ al utilizar el "truco X". Esto excede significativamente las capacidades de GAP, que se limita a $n \approx 20$ . Los métodos de IA producen caminos más cortos y se ejecutan más rápido que GAP para $n$ comparables.
Resultados Matemáticos y Conjeturas:
- Conjetura del Diámetro: Los autores respaldan firmemente la conjetura OEIS-A186783 de que el diámetro del grafo de Cayley LRX es $n(n-1)/2$ . Lo verificaron mediante BFS de fuerza bruta para $n \le 15$ y mediante descomposición con IA para $n$ hasta 200 (a través de desafíos en Kaggle), sin encontrar ninguna descomposición más corta que la longitud conjeturada.
- Elemento Más Largo: Identifican un único "elemento más largo" $\ell_n = (1, 0, n-1, n-2, \dots, 3, 2)$ y proporcionan una descomposición explícita de longitud $n(n-1)/2$ .
- Límites: El artículo prueba una cota inferior para el diámetro de $n(n-1)/2 - n/2 - 1$ y una cota superior de $n(n-1)/2 + 3n$ mediante un algoritmo constructivo. Un algoritmo empírico sugiere una cota más ajustada de $n(n-1)/2 + n/2$ .
- Distribución de Crecimiento: Los experimentos numéricos sugieren que la función de crecimiento del grafo LRX sigue una distribución Gumbel sesgada a la izquierda para $n$ grande, en contraste con la distribución gaussiana observada en grafos de transposición de vecinos.
- Tiempo de Mezcla: Mientras que los paseos aleatorios estándar tienen tiempos de mezcla entre $O(n^3)$ y $O(n^3 \log n)$ , los autores conjeturan que los paseos aleatorios modificados con el "truco X" se mezclan más rápido, con una complejidad temporal de $O(n^2)$ .
- Espectro: El espectro del grafo LRX parece seguir una distribución uniforme.
Código Abierto y Crowdsourcing: Los autores lanzaron el proyecto "CayleyPy" y crearon desafíos en Kaggle para obtener soluciones crowdsourced para descomponer el elemento más largo y encontrar algoritmos óptimos, fomentando la colaboración entre las comunidades de IA y matemáticas.

Resultados

Eficiencia: Para $n=20$ , GAP requiere más de 41 minutos para encontrar un camino de longitud 217,944, mientras que el método de distancia de difusión encuentra el camino óptimo de longitud 190 en menos de 4 minutos.
Escalabilidad: Con el "truco X", el sistema resolvió instancias para $n=100$ (tamaño del grafo $\approx 10^{157}$ ) en aproximadamente 8.5 horas en una sola GPU, encontrando un camino de longitud 16,632 (en comparación con el diámetro conjeturado de 4,950).
Rendimiento del Modelo: Modelos simples como Perceptrones Multicapa (MLP) y Boosting de Gradiente (CatBoost/XGBoost) a menudo superaron a arquitecturas complejas como Transformers y CNNs para esta tarea específica.
Búsqueda en Haz: La tasa de éxito de encontrar un camino depende altamente del ancho del haz, mostrando una mejora superlineal a medida que aumenta el tamaño del haz, análogo al "intercambio de ideas" en una comunidad de investigación.

Significado
El artículo afirma que los experimentos computacionales, particularmente aquellos que aprovechan la IA, pueden avanzar significativamente la investigación matemática sobre grafos de Cayley. Demuestra que los métodos de IA pueden "superar" a los sistemas de álgebra computacional clásicos tanto en escalabilidad (manejo de $n$ mucho más grandes) como en calidad de solución (encontrar caminos más cortos y casi óptimos). El trabajo cierra la brecha entre la teoría de grupos teórica y la IA práctica, proporcionando cotas rigurosas, nuevas conjeturas sobre tiempos de crecimiento y mezcla, y un marco para resolver problemas de búsqueda de caminos en espacios de estados extremadamente grandes que previamente eran intratables. Los autores posicionan esto como un paso hacia la aplicación de la IA a otros problemas de planificación complejos en la ciencia teórica.