Solving Large Rubik's Cubes within a Factor of of Optimal
En palabras de los autores
We design optimized algorithms to solve the Rubik's Cube within moves. This upper bound is asymptotically within a factor of of the known lower bound, which applies to almost all instances. The constant is also the first explicit constant factor for the known upper bound of , where the implicit constant of the previous algorithm was (ten duodecillion). Thus we improve the upper-bound constant by a factor of more than (330 undecillion). Our algorithm runs in time linear in the input size , and uses extra space (beyond the state of the cube). Our implementation is the first practical cube solver to generate solutions of length . Our latest solver outperforms existing solvers for as small as .
En palabras simples Resumen con IA
Los autores diseñaron algoritmos para resolver cubos de Rubik grandes usando a lo sumo 30.5 n² / log n movimientos. Este resultado está dentro de 2.37 veces la mejor solución posible para casi todos los casos. Mejoraron la constante anterior de aproximadamente 10 duodecillones a 30.5. Su algoritmo se ejecuta en tiempo lineal y usa relativamente poca memoria extra.
Escrito por Kimi K2.5 usando solo el abstract de arriba. Jev verificó que cada oración esté respaldada por las oraciones del abstract que cita y eliminó las que no. Pasá el cursor por una oración para ver de dónde sale. Se eliminó 1 oración por no estar respaldada por el abstract.
Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 41 pages, 18 figures, 16 tables. Project page: https://largecubebench.org