CayleyR：透過迴圈交集解決TopSpin謎題
cayleyR是一個R語言包，利用凱萊圖中的迴圈交集檢測來解決排列謎題。核心演算法採用迭代雙向搜尋，從初始和目標排列狀態生成隨機操作序列，尋找連線路徑。該包專為TopSpin(n,k)謎題設計，結合C++雜湊索引狀態儲存和可選的Vulkan GPU加速，已在CRAN上釋出。
研究人員近日釋出了cayleyR，一個用於求解排列謎題的R語言包。該包的核心創新在於透過檢測凱萊圖中的迴圈交集來找到連線路徑。排列謎題通常可以建模為對稱群Sn的凱萊圖，其中節點表示排列狀態，邊表示允許的操作。cayleyR的演算法執行迭代雙向搜尋：從初始狀態和目標狀態分別生成隨機的操作序列，這些序列在凱萊圖中形成迴圈；當兩條迴圈相交時，即得到一條解路徑。若未直接發現交集，則採用距離引導的橋接選擇來縮小差距，並重復該過程。
cayleyR主要針對TopSpin(n,k)謎題設計。TopSpin是一個經典的排列難題，由一個圓形滑軌和帶有數字的滑塊組成，透過迴圈移位和字首反轉操作來打亂和還原。其狀態空間正是由迴圈移位和字首反轉生成的凱萊圖。該包不僅提供了數學框架和演算法的詳細描述，還實現了高效的資料結構——使用C++雜湊索引的狀態儲存，並可選配Vulkan GPU加速以提升效能。
cayleyR已在CRAN上公開發布，使用者可直接安裝使用。這項研究為組合搜尋和人工智慧中的路徑規劃問題提供了一個新的工具，特別適用於處理大規模狀態空間。論文作者Yuri Baramykov於2026年7月14日提交了該工作，全文共17頁，包含2張圖表。對於研究群體和演算法愛好者而言，cayleyR提供了一種新穎的視角來解決複雜的排列難題，同時也展示了圖論與高效能運算的結合潛力。