CayleyR: Solving the TopSpin puzzle via cycle intersection

Sintesi Tecnica: CAYLEYR: RISOLVERE IL PUZZLE TOPSPIN VIA INTERSEZIONE DI CICLI

1. Definizione del Problema
Il documento affronta la sfida computazionale di risolvere il puzzle TopSpin$(n, k)$, un puzzle di permutazioni che coinvolge $n$ gettoni su una pista circolare e una finestra di un tornello di larghezza $k$. L'obiettivo è trasformare una data permutazione iniziale in una permutazione target utilizzando due mosse primarie: uno scorrimento ciclico dell'intera pista (Sinistra $L$ o Destra $R$) e un ribaltamento dei $k$ gettoni all'interno del tornello ($X_k$).

Algebricamente, lo spazio degli stati corrisponde al grafo di Cayley $\Gamma(G, \{L, R, X_k\})$, dove $G$ è il gruppo simmetrico $S_n$ (per $k$ pari) o il gruppo alternante $A_n$ (per $k$ dispari). Risolvere il puzzle equivale a trovare un percorso tra due vertici in questo grafo. Gli autori osservano che per $n > 10$, lo spazio degli stati ($n!$) cresce super-esponenzialmente, rendendo intrattabile la ricerca classica dei cammini minimi tramite Breadth-First Search (BFS). Inoltre, il diametro congetturale del grafo è $\Theta(n^2)$, complicando ulteriormente la difficoltà.

2. Metodologia: Iterative Cycle Intersection (ICI)
Il documento propone una strategia fondamentalmente diversa dall'esplorazione del grafo livello per livello: l'algoritmo Iterative Cycle Intersection (ICI). Invece di espandere la frontiera di ricerca in modo uniforme, l'ICI genera "cicli" casuali sia dallo stato iniziale che da quello finale e cerca un'intersezione tra queste famiglie di cicli.

L'algoritmo opera in round iterativi, mantenendo due depositi di stati ($S$ e $F$) che si espandono rispettivamente dallo stato iniziale ($\sigma_s$) e dallo stato finale ($\sigma_f$). Ogni round consiste in quattro fasi:

1. Generazione di Combinazioni Casuali: Viene generata una serie di sequenze di operazioni casuali (parole) di lunghezza $\ell$.
2. Espansione del Ciclo: Per ogni sequenza, l'algoritmo calcola l'intero ciclo di stati generato applicando ripetutamente la permutazione composta finché non ritorna al seme. Tutti gli stati intermedi vengono registrati nel rispettivo deposito.
3. Controllo di Intersezione: L'algoritmo controlla la presenza di stati condivisi tra $S$ e $F$ utilizzando lookup indicizzati tramite hash. Se viene trovata un'intersezione $\sigma^*$, il percorso viene ricostruito tracciando le catene dei cicli a ritroso verso le origini.
4. Selezione del Ponte (Bridge Selection): Se non si verifica alcuna intersezione, l'algoritmo seleziona degli "stati ponte" per riavviare l'espansione. Gli stati in $S$ sono classificati in base alla loro distanza da $\sigma_f$, e gli stati in $F$ in base alla loro distanza da $\sigma_s$. I 10 stati più vicini su ciascun lato vengono presi in considerazione, e uno viene scelto casualmente da ciascuno per servire come nuovo seme per il round successivo.

Ricostruzione e Raffinamento del Percorso:
Quando viene trovata un'intersezione, il percorso completo viene assemblato concatenando i segmenti attraverso tutti i round. Il documento nota che il percorso risultante non è garantito essere il più breve. Per affrontare questo problema, il pacchetto include un passaggio di post-elaborazione (short path bfs) che esegue un "hopping" locale di tipo BFS a profondità limitata per sostituire i segmenti intermedi con rotte più brevi.

Strategia Ibrida (Hub-Based Transport Network):
Per istanze più grandi, il documento descrive un approccio ibrido (find_path_bfs). Questo metodo costruisce prima alberi autostradali sparsi ("highway trees") utilizzando BFS a profondità limitata da entrambi gli endpoint per identificare gli stati "hub". Successivamente, seleziona la coppia di hub più vicina e invoca l'algoritmo ICI per colmare il divario tra di essi. Ciò riduce la distanza di ricerca effettiva prima che inizi la fase stocastica di intersezione dei cicli.

3. Contributi Chiave
Il documento delinea tre contributi principali:

1. L'Algoritmo ICI: Una nuova strategia di ricerca del percorso per i grafi di Cayley dei gruppi di permutazione che si basa sull'intersezione di cicli casuali e sulla selezione del ponte guidata dalla distanza, piuttosto che sull'espansione esaustiva dei livelli.
2. Il Pacchetto cayleyR: Un pacchetto R open-source (con un backend in C++ tramite Rcpp) che implementa l'algoritmo. Le caratteristiche chiave includono:
   • Archiviazione degli stati indicizzata tramite hash per inserimento e lookup con complessità ammortizzata $O(1)$.
   • Accelerazione opzionale tramite GPU Vulkan per il calcolo batch delle trasformazioni di stato e delle distanze a coppie.
   • "Coordinate celesti", un embedding geometrico dei conteggi delle operazioni su una sfera per la visualizzazione e il potenziale uso futuro come euristica.
3. Dimostrazioni di Scalabilità: Esperimenti computazionali che mostrano la capacità dell'algoritmo di risolvere istanze di TopSpin con $n$ fino a 20, una scala precedentemente difficile per i solver esatti.

4. Risultati Sperimentali
Gli autori presentano benchmark su una workstation Linux (AMD Ryzen 5 5600) utilizzando cayleyR versione 0.1.0/0.2.1:

• Criteri di Classificazione: La scelta di come classificare le sequenze di operazioni casuali impatta significativamente le prestazioni. Il criterio "più unico" (priorità alle sequenze che visitano il maggior numero di stati distinti) ha ottenuto il tasso di successo più alto (83% su 12 istanze, $n=14\text{--}30$) ma spesso produceva percorsi molto lunghi. Al contrario, le sequenze "più ripetute" hanno offerto un'alta affidabilità (75% di successo) con percorsi costantemente brevi e tempi di ricerca rapidi (mediana < 1s).
• Scalabilità con la Distanza di Scramble: Su TopSpin(14, 4) con distanze di scramble variabili ($n_{moves}=20\text{--}150$), l'algoritmo ha risolto tutte le 14 istanze. Il tempo medio di ricerca è stato di 1,12 secondi, con il tempo totale (inclusa l'accorciatura del percorso) che mediamente raggiungeva i 2,3 secondi. Il numero di cicli ICI richiesti non è correlato monotonicamente con la distanza di scramble, evidenziando la natura stocastica del metodo.
• Scalabilità con la Dimensione del Puzzle ($n$): Su istanze con $n=10\text{--}16$ e distanza di scramble fissa, i tempi di ricerca sono rimasti sotto i 0,5 secondi. Gli autori attribuiscono ciò al fatto che l'algoritmo materializza solo una piccola frazione dello spazio degli stati, rendendolo meno sensibile alla crescita super-esponenziale di $n!$ rispetto alla BFS.

5. Significato e Rivendicazioni
Il documento posiziona cayleyR come uno strumento pratico per risolvere puzzle di permutazione che superano i limiti della ricerca esaustiva classica. La sua importanza risiede in:

• Efficienza: Evita i colli di bottiglia di memoria e tempo dei database di pattern e della BFS utilizzando la generazione di cicli casuali e l'intersezione basata su hash.
• Scalabilità: Gestisce con successo istanze fino a $n=20$, dove lo spazio degli stati è $20!$.
• Modularità: Sebbene attualmente focalizzato su TopSpin, gli autori affermano che il framework sottostante (intersezione di cicli, selezione del ponte, depositi indicizzati tramite hash) è applicabile ad altri puzzle di permutazione (es. pancake sorting, Hungarian Rings), purché possano essere modellati come grafi di Cayley.

Gli autori rimangono modesti riguardo all'ottimalità delle soluzioni, riconoscendo che l'ICI non garantisce i percorsi minimi e che l'embedding delle "coordinate celesti" è attualmente uno strumento di visualizzazione sperimentale piuttosto che un'euristica provata per la stima della distanza. Si propone come lavoro futuro l'esplorazione di framework di dualità olografica per l'intersezione dei cicli e la generalizzazione dell'interfaccia del generatore per classi di puzzle più ampie.