用机器学习破解大尺寸魔方，速度与精度全面超越现有方法。
A Machine Learning Approach That Beats Large Rubik's Cubes
- 通过神经网络估计扩散距离，结合束搜索实现高效路径规划。
- 4×4×4和5×5×5魔方解法长度创纪录，3×3×3最优解率超98%。
- 适合需要快速求解高维组合问题的研究者与竞赛开发者。
本文提出一种基于机器学习的新型路径搜索方法，用于处理极大规模图上的寻路问题。该方法利用神经网络估算扩散距离，并结合束搜索进行路径规划。我们验证了其高效性：在4×4×4和5×5×5魔方上找到了前所未有的短解，优于所有现有求解器，并首次实现了对3×3×3以上魔方的机器学习求解。特别地，其在包含超过1000支队伍参与的Kaggle Santa 2023挑战中，超越了所有单个案例的最佳结果。对于3×3×3魔方，本方法的最优解率超过98%，与专用求解器持平，显著优于DeepCubeA（60.3%）和EfficientCube（69.6%）。此外，该方法求解3×3×3魔方的速度比现有方法快26倍以上，模型训练时间最多节省18.5倍。
原文摘要 · Abstract (English)
The paper proposes a novel machine learning-based approach to the pathfinding problem on extremely large graphs. This method leverages diffusion distance estimation via a neural network and uses beam search for pathfinding. We demonstrate its efficiency by finding solutions for 4x4x4 and 5x5x5 Rubik's cubes with unprecedentedly short solution lengths, outperforming all available solvers and introducing the first machine learning solver beyond the 3x3x3 case. In particular, it surpasses every single case of the combined best results in the Kaggle Santa 2023 challenge, which involved over 1,000 teams. For the 3x3x3 Rubik's cube, our approach achieves an optimality rate exceeding 98%, matching the performance of task-specific solvers and significantly outperforming prior solutions such as DeepCubeA (60.3%) and EfficientCube (69.6%). Additionally, our solution is more than 26 times faster in solving 3x3x3 Rubik's cubes while requiring up to 18.5 times less model training time than the most efficient state-of-the-art competitor.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。