Репост из: Графики каждый день (почти)
Нашу статью взяли на NeurIPS 2025!
arxiv:2502.13266
Статья "A Machine Learning Approach That Beats Large Rubik's Cubes" про то как находить путь на больших графах в принципе, и про то как with zero human knowledge собирать Кубик Рубика 3x3, 4x4, 5x5, пятнашки до 6x6, ... и другие перестановочные пазлы в частности. Для понимания масштаба: кубик 5x5 это 10⁷⁴ состояний, а мы там находим достаточно короткий (лучший из опубликованных) путь сборки. Код к статье доступен на git cayleypy-cube.
Забавно что для меня это началось с этого поста 2 года назад, а потом списались с @Alexander_V_C (огромное ему спасибо) и как-то так и пошла интернет коллаборация. Собственно про метод писал здесь, и потом ещё подробнее напишу. Красиво, что просто немного случайно блуждая по графу, можно обучить модель очень хорошей эвристике, достаточной для ориентирования на широком классе графов.
Мне очень давно хотелось, чтобы какой-нибудь такой сюжет существующий из любопытства в рамках хобби добрался до рецензий. А тут не просто добрался, но и на A* конференцию, ещё и выдвинули на spotlight (топ 15% от принятых работ).
Воот)
arxiv:2502.13266
Статья "A Machine Learning Approach That Beats Large Rubik's Cubes" про то как находить путь на больших графах в принципе, и про то как with zero human knowledge собирать Кубик Рубика 3x3, 4x4, 5x5, пятнашки до 6x6, ... и другие перестановочные пазлы в частности. Для понимания масштаба: кубик 5x5 это 10⁷⁴ состояний, а мы там находим достаточно короткий (лучший из опубликованных) путь сборки. Код к статье доступен на git cayleypy-cube.
Забавно что для меня это началось с этого поста 2 года назад, а потом списались с @Alexander_V_C (огромное ему спасибо) и как-то так и пошла интернет коллаборация. Собственно про метод писал здесь, и потом ещё подробнее напишу. Красиво, что просто немного случайно блуждая по графу, можно обучить модель очень хорошей эвристике, достаточной для ориентирования на широком классе графов.
Мне очень давно хотелось, чтобы какой-нибудь такой сюжет существующий из любопытства в рамках хобби добрался до рецензий. А тут не просто добрался, но и на A* конференцию, ещё и выдвинули на spotlight (топ 15% от принятых работ).
Воот)