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提供了一種新穎的視角來解決複雜的排列難題，同時也展示了圖論與高性能計算的結合潛力。