CayleyR: Solving the TopSpin puzzle via cycle intersection

Resumo Técnico: CAYLEYR: RESOLVENDO O QUEBRA-CABEÇA TOPSPIN VIA INTERSECÇÃO DE CICLOS

1. Enunciado do Problema
O artigo aborda o desafio computacional de resolver o quebra-cabeça TopSpin$(n, k)$, um quebra-cabeça de permutação envolvendo $n$ tokens em uma pista circular e uma janela de torniquete de largura $k$. O objetivo é transformar uma permutação inicial dada em uma permutação alvo usando dois movimentos primários: um deslocamento cíclico de toda a pista (Esquerda $L$ ou Direita $R$) e uma reversão dos $k$ tokens dentro do torniquete ($X_k$).

Algebraicamente, o espaço de estados corresponde ao grafo de Cayley $\Gamma(G, \{L, R, X_k\})$, onde $G$ é o grupo simétrico $S_n$ (para $k$ par) ou o grupo alternante $A_n$ (para $k$ ímpar). Resolver o quebra-cabeça equivale a encontrar um caminho entre dois vértices neste grafo. Os autores observam que, para $n > 10$, o espaço de estados ($n!$) cresce super-exponencialmente, tornando intratáveis algoritmos clássicos de busca de caminho mais curto, como a Busca em Largura (BFS). Além disso, o diâmetro conjecturado do grafo é $\Theta(n^2)$, o que agrava a dificuldade.

2. Metodologia: Intersecção de Ciclos Iterativa (ICI)
O artigo propõe uma estratégia fundamentalmente diferente da exploração de grafos nível a nível: o algoritmo de Intersecção de Ciclos Iterativa (ICI). Em vez de expandir a fronteira de busca uniformemente, o ICI gera "ciclos" aleatórios tanto a partir dos estados iniciais quanto dos finais e busca uma intersecção entre essas famílias de ciclos.

O algoritmo opera em rodadas iterativas, mantendo dois depósitos de estados ($S$ e $F$) expandindo-se a partir dos estados inicial ($\sigma_s$) e final ($\sigma_f$), respectivamente. Cada rodada consiste em quatro fases:

1. Geração de Combinação Aleatória: Um lote de sequências de operações aleatórias (palavras) de comprimento $\ell$ é gerado.
2. Expansão de Ciclo: Para cada sequência, o algoritmo computa o ciclo completo de estados gerados pela aplicação repetida da permutação composta até que ela retorne à semente. Todos os estados intermediários são registrados no respectivo depósito.
3. Verificação de Intersecção: O algoritmo verifica estados compartilhados entre $S$ e $F$ usando buscas indexadas por hash. Se uma intersecção $\sigma^*$ for encontrada, o caminho é reconstruído rastreando as cadeias de ciclos de volta às origens.
4. Seleção de Ponte (Bridge Selection): Se não ocorrer uma intersecção, o algoritmo seleciona "estados de ponte" para reiniciar a expansão. Os estados em $S$ são classificados por sua distância a $\sigma_f$, e os estados em $F$ são classificados por sua distância a $\sigma_s$. Os 10 estados mais próximos de cada lado são considerados, e um é escolhido aleatoriamente de cada um para servir como a nova semente para a próxima rodada.

Reconstrução e Refinamento de Caminho:
Quando uma intersecção é encontrada, o caminho completo é montado encadeando os segmentos através de todas as rodadas. O artigo observa que o caminho resultante não é garantido como sendo o mais curto. Para abordar isso, o pacote inclui uma etapa de pós-processamento (short path bfs) que realiza "saltos" (hopping) de BFS local com profundidade limitada para substituir segmentos intermediários por rotas mais curtas.

Estratégia Híbrida (Rede de Transporte Baseada em Hubs):
Para instâncias maiores, o artigo descreve uma abordagem híbrida (find_path_bfs). Este método primeiro constrói "árvores de rodovias" esparsas usando BFS de profundidade limitada de ambos os pontos terminais para identificar estados "hub". Em seguida, seleciona o par de hubs mais próximo e invoca o algoritmo ICI para fazer a ponte entre eles. Isso reduz a distância de busca efetiva antes que a fase de intersecção de ciclos estocástica come-ce.

3. Principais Contribuições
O artigo delineia três contribuições principais:

1. O Algoritmo ICI: Uma nova estratégia de busca de caminho para grafos de Cayley de grupos de permutação que se baseia na intersecção de ciclos e na seleção de ponte guiada por distância, em vez da expansão exaustiva de nível.
2. O Pacote cayleyR: Um pacote R de código aberto (com um backend em C++ via Rcpp) que implementa o algoritmo. As principais características incluem:
   • Armazenamento de estado indexado por hash para inserção e busca com tempo amortizado $O(1)$.
   • Aceleração opcional por GPU Vulkan para processamento em lote de transformações de estado e computações de distância par a par.
   • "Coordenadas celestiais", um mapeamento geométrico de contagens de operações sobre uma esfera para visualização e potencial uso heurístico futuro.
3. Demonstrações de Escalabilidade: Experimentos computacionais mostrando a capacidade do algoritmo de resolver instâncias de TopSpin com $n$ até 20, uma escala anteriormente difícil para resolvedores exatos.

4. Resultados Experimentais
Os autores apresentam benchmarks em uma estação de trabalho Linux (AMD Ryzen 5 5600) usando a versão 0.1.0/0.2.1 do cayleyR:

• Critérios de Classificação: A escolha de como classificar as sequências de operações aleatórias impacta significativamente o desempenho. O critério "mais único" (priorizando sequências que visitam o maior número de estados distintos) alcançou a maior taxa de sucesso (83% em 12 instâncias, $n=14\text{--}30$), mas frequentemente produzia caminhos muito longos. Por outro lado, as sequências "mais repetidas" ofereceram alta confiabilidade (75% de sucesso) com caminhos consistentemente curtos e tempos de busca rápidos (mediana < 1s).
• Escalabilidade com Distância de Embaralhamento (Scramble Distance): No TopSpin(14, 4) com distâncias de embaralhamento variáveis ($n_{moves}=20\text{--}150$, o algoritmo resolveu todas as 14 instâncias. O tempo médio de busca foi de 1,12 segundos, e o tempo total (incluindo o encurtamento do caminho) average de 2,3 segundos. O número de ciclos ICI necessários não se correlacionou monotonicamente com a distância de embaralhamento, destacando a natureza estocástica do método.
• Escalabilidade com o Tamanho do Quebra-Cabeça ($n$): Em instâncias com $n=10\text{--}16$ e distância de embaralhamento fixa, os tempos de busca permaneceram abaixo de 0,5 segundos. Os autores atribuem isso ao fato de o algoritmo materializar apenas uma pequena fração do espaço de estados, tornando-o menos sensível ao crescimento super-exponencial de $n!$ em comparação com o BFS.

5. Significância e Alegações
O artigo posiciona o cayleyR como uma ferramenta prática para resolver quebra-cabeças de permutação que excedem os limites da busca exaustiva clássica. Sua significância reside na:

• Eficiência: Evita os gargalos de memória e tempo de bancos de dados de padrões e do BFS ao usar geração de ciclos aleatórios e intersecção baseada em hash.
• Escalabilidade: Lida com sucesso com instâncias até $n=20$, onde o espaço de estados é $20!$.
• Modularidade: Embora atualmente adaptado para o TopSpin, os autores afirmam que a estrutura subjacente (intersecção de ciclos, seleção de ponte, depósitos indexados por hash) é aplicável a outros quebra-cabeças de permutação (ex: ordenação de panquecas, anéis húngaros), desde que possam ser modelados como grafos de Cayley.

Os autores permanecem modestos quanto à otimalidade das soluções, reconhecendo que o ICI não garante caminhos mais curtos e que o mapeamento de "coordenadas celestiais" é atualmente uma ferramenta de visualização experimental, não uma heurística comprovada para estimativa de distância. O trabalho futuro propõe explorar estruturas de dualidade holográfica para intersecção de ciclos e generalizar a interface do gerador para classes mais amplas de quebra-cabeças.