CayleyR: Solving the TopSpin puzzle via cycle intersection

技術要約：CAYLEYR：サイクル交差によるトップスピン・パズルの解決

1. 問題定義
本論文は、$n$ 個のトークンが円形トラック上にあり、幅 $k$ のターンタイル・ウィンドウを持つ置換パズルである TopSpin$(n, k)$ の計算上の課題に対処するものである。目標は、与えられた初期置換を、トラック全体の循環シフト（左 $L$ または右 $R$）と、ターンタイル内の $k$ 個のトークンの反転（$X_k$）という2つの主要な動きを用いて、ターゲットとなる置換へと変換することである。

代数的には、状態空間はケイリーグラフ $\Gamma(G, \{L, R, X_k\})$ に対応し、ここで $G$ は対称群 $S_n$（$k$ が偶数の場合）または交代群 $A_n$（$k$ が奇数の場合）である。パズルを解くことは、このグラフにおける2つの頂点間のパスを見つけることに等しい。著者らは、$n > 10$ の場合、状態空間（$n!$）が超指数関数的に増大するため、幅優先探索（BFS）のような古典的な最短経路アルゴリズムは実行不可能になることを指摘している。さらに、グラフの直径が $\Theta(n^2)$ であるという予想が、難易度をさらに高めている。

2. 手法：反復的サイクル交差（Iterative Cycle Intersection: ICI）
本論文は、レベルごとのグラフ探索とは根本的に異なる戦略である、**反復的サイクル交差（ICI）**アルゴリズムを提案している。ICIは、探索のフロント（境界）を一様に拡張するのではなく、開始状態とターゲット状態の両方からランダムな「サイクル」を生成し、それらのサイクルの集合間の交差を探索する。

アルゴリズムは、開始状態（$\sigma_s$）と最終状態（$\sigma_f$）からそれぞれ拡張される2つの状態ストア（$S$ および $F$）を維持しながら、反復的なラウンド形式で動作する。各ラウンドは以下の4つのフェーズで構成される：

1. ランダムな組み合わせ生成： 長さ $\ell$ のランダムな操作シーケンス（ワード）のバッチを生成する。
2. サイクル拡張： 各シーケンスについて、合成された置換を繰り返し適用して元のシードに戻るまで、生成される全サイクルを計算する。すべての中間状態は、それぞれのストアに記録される。
3. 交差チェック： ハッシュインデックスを用いたルックアップを使用して、$S$ と $F$ の間の共有状態を確認する。もし交差する状態 $\sigma^*$ が見つかった場合、サイクルチェーンを起点まで遡ることでパスを再構成する。
4. ブリッジ選択： 交差が発生しない場合、拡張を再開するための「ブリッジ状態」を選択する。$S$ 内の状態は $\sigma_f$ への距離によってランク付けされ、$F$ 内の状態は $\sigma_s$ への距離によってランク付けされる。両側で最も近い上位10個の状態を考慮し、それぞれから1つをランダムに選択して、次のラウンドの新しいシードとする。

パスの再構成と洗練：
交差が見つかったとき、全ラウンドのセグメントを繋ぎ合わせることで完全なパスを組み立てる。論文では、得られるパスが最短経路であることが保証されていないことが記されている。これに対処するため、パッケージには、中間セグメントをより短いルートに置き換えるための局所的な深度制限付きBFS「ホッピング」を行う後処理ステップ（short path bfs）が含まれている。

ハイブリッド戦略（ハブベース輸送ネットワーク）：
より大規模なインスタンスに対して、本論文はハイブリッドアプローチ（find_path_bfs）について述べている。この手法は、まず両端からの限定的な深さのBFSを用いて疎な「高速道路ツリー（highway trees）」を構築し、「ハブ」状態を特定する。その後、最も近いハブのペアを選択し、その間のギャップを埋めるためにICIアルゴリズムを呼び出す。これにより、確率的なサイクル交差フェーズを開始する前に、実効的な探索距離を短縮することができる。

3. 主な貢献
本論文は、主に3つの貢献を挙げている：

1. ICIアルゴリズム： レベルごとの網羅的な探索ではなく、サイクルの交差と距離ガイド付きのブリッジ選択に依存する、置換群のケイリーグラフのための新しい経路探索戦略。
2. cayleyR パッケージ： アルゴリズムを実装したオープンソースのRパッケージ（C++バックエンドとしてRcppを使用）。主な機能は以下の通りである：
   • $O(1)$ の償却時間での挿入およびルックアップを実現するハッシュインデックス化された状態ストレージ。
   • バッチ状態変換およびペアワイズ距離計算のための、オプションのVulkan GPU加速。
   • 可視化および将来的なヒューリスティック利用のための、球体への操作数の幾何学的埋め込みである「天球座標（celestial coordinates）」。
3. スケーラビリティの実証： $n=20$ までのTopSpinインスタンスを、従来の厳密解法では困難であったスケールで解決できることを示す計算実験。

4. 実験結果
著者らは、Linuxワークステーション（AMD Ryzen 5 5600）を用い、cayleyR バージョン 0.1.0/0.2.1 に関するベンチマークを提示している：

• ランキング基準： ランダムな操作シーケンスのランク付け方法がパフォーマンスに大きく影響する。「最もユニークな（most unique）」基準（最も多くの異なる状態を訪問するシーケンスを優先する）は、最も高い成功率（$n=14\text{--}30$ の12インスタンスで83%）を達成したが、非常に長いパスを生成することが多かった。逆に、「最も繰り返される（most repeated）」シーケンスは、一貫して短いパスと高速な探索時間（中央値 < 1秒）を提供し、高い信頼性（成功率75%）を実現した。
• スクランブル距離によるスケーラビリティ： 様々なスクランブル距離（$n_{moves}=20\text{--}150$）を持つ TopSpin(14, 4) において、アルゴリズムは14のインスタンスすべてを解決した。平均探索時間は1.12秒であり、総時間（パス短縮を含む）は平均2.3秒であった。必要なICIサイクルの数はスクランブル距離と単調な相関関係にならず、この手法の確率的な性質を浮き彫りにした。
• パズルサイズ（$n$）によるスケーラビリティ： 固定されたスクランブル距離を持つ $n=10\text{--}16$ のインスタンスにおいて、探索時間は0.5秒未満に留まった。著者らは、アルゴリズムが状態空間のごく一部のみを具現化するため、BFSと比較して $n!$ の超指数関数的な増大に対して感度が低いことを理由としている。

5. 意義と主張
本論文は、cayleyR を、古典的な網羅的探索の限界を超える置換パズルを解くための実用的なツールとして位置づけている。その意義は以下の点にある：

• 効率性： ランダムなサイクル生成とハッシュベースの交差を用いることで、パターンデータベースやBFSによるメモリおよび時間のボトルネックを回避している。
• スケーラビリティ： 状態空間が $20!$ である $n=20$ までのインスタンスを正常に扱うことができる。
• モジュール性： 現在はTopSpinに特化しているが、著者らは、ケイリーグラフとしてモデル化できるのであれば、その基礎となるフレームワーク（サイクル交差、ブリッジ選択、ハッシュインデックス化されたストア）は、他の置換パズル（パンケーキ・ソーティングやハンガリアン・リングなど）にも適用可能であると主張している。

著者らは、ICIが最短経路を保証するものではないこと、および「天球座標」の埋め込みが現在は距離推定のための実験的な可視化ツールであり、確立されたヒューリスティックではないことを認め、ICIに対して謙虚な姿勢を保っている。今後の課題として、サイクル交差のためのホログラフィック双対性の枠組みの探索や、より広範なパズルクラスのためのジェネレーター・インターフェースの一般化が提案されている。