начало тут 👆
🧩 Всем привет!
Есть серия соревнований на Kaggle, где в соревновательной форме можно попробовать решать открытые задачи математики на графах Кэли и подгруппах симметрической группы.
🎯 Суть
Нужно искать кратчайшие пути в графах Кэли — будь то оптимальные решения для куба Рубика 4×4×4 (Rubik’s Revenge), задачи на транспозоны или другие перестановочные головоломки.
В общем случае такие задачи NP-трудные.
Для малых размеров иногда можно найти оптимум, для больших — выигрывает тот, кто строит более короткие пути.
🔬 Научный контекст
Это классическая постановка: разложить элемент группы в произведение генераторов, или — найти путь в графе Кэли.
-Примеры: bubble sort, pancake sorting 🥞 (в котором, к слову, участвовал Билл Гейтс).
-Открытая гипотеза OEIS A065603 предсказывает, что диаметр (т.н. число Бога) равен ⌈(n+1)/2⌉ — она остаётся нерешённой уже 25 лет.
Важность темы подчёркивают работы М. Громова, Т. Тао и других. Дональд Кнут предлагал алгоритмические улучшения.
Применения: биоинформатика (оценка эволюционных расстояний), теория коммуникаций, оптимизация сетей и многое другое.
🤖 RL и компьютерные науки
Состояния = вершины графа Кэли.
Действия = рёбра (разрешённые перестановки).
Награды = всегда "1", пока не найдено решение (там 0).
Итого: классический RL с экстремально разреженной наградой.
Функция ценности = длина пути до решения, а уравнение Беллмана в этом случае напрямую отражает тривиальные соотношения на длинах путей.
Это отличная площадка для тестирования новых методов RL и pathfinding на пространствах колоссального размера (10³³ и больше).
🚀 Практика - соревнования
В соревнованиях можно попробовать себя не только с кубом Рубика, но и с другими задачами:
Pancake sorting
Transposons
Reversals
Glushkov problem
RapapportM2
Rubik's cube 444
Professor Tetraminx
Megaminx
Christophers jewel
SuperCube from IHES
Все они собраны в рамках проекта CayleyPy — это open-source crowd-sourcing инициатива для разработки AI-библиотеки по математике. Можно подключаться и вне Kaggle.
Если интересно поучаствовать, но кажется, что порог входа высокий — я могу сделать введение на созвоне и рассказать основы: что такое графы Кэли, как ставится задача и какие методы уже пробовали.
Продолжение тут и тут👇
#Puzzles #CayleyGraphs #SymmetricGroup #KaggleCompetitions
🧩 Всем привет!
Есть серия соревнований на Kaggle, где в соревновательной форме можно попробовать решать открытые задачи математики на графах Кэли и подгруппах симметрической группы.
🎯 Суть
Нужно искать кратчайшие пути в графах Кэли — будь то оптимальные решения для куба Рубика 4×4×4 (Rubik’s Revenge), задачи на транспозоны или другие перестановочные головоломки.
В общем случае такие задачи NP-трудные.
Для малых размеров иногда можно найти оптимум, для больших — выигрывает тот, кто строит более короткие пути.
🔬 Научный контекст
Это классическая постановка: разложить элемент группы в произведение генераторов, или — найти путь в графе Кэли.
-Примеры: bubble sort, pancake sorting 🥞 (в котором, к слову, участвовал Билл Гейтс).
-Открытая гипотеза OEIS A065603 предсказывает, что диаметр (т.н. число Бога) равен ⌈(n+1)/2⌉ — она остаётся нерешённой уже 25 лет.
Важность темы подчёркивают работы М. Громова, Т. Тао и других. Дональд Кнут предлагал алгоритмические улучшения.
Применения: биоинформатика (оценка эволюционных расстояний), теория коммуникаций, оптимизация сетей и многое другое.
🤖 RL и компьютерные науки
Состояния = вершины графа Кэли.
Действия = рёбра (разрешённые перестановки).
Награды = всегда "1", пока не найдено решение (там 0).
Итого: классический RL с экстремально разреженной наградой.
Функция ценности = длина пути до решения, а уравнение Беллмана в этом случае напрямую отражает тривиальные соотношения на длинах путей.
Это отличная площадка для тестирования новых методов RL и pathfinding на пространствах колоссального размера (10³³ и больше).
🚀 Практика - соревнования
В соревнованиях можно попробовать себя не только с кубом Рубика, но и с другими задачами:
Pancake sorting
Transposons
Reversals
Glushkov problem
RapapportM2
Rubik's cube 444
Professor Tetraminx
Megaminx
Christophers jewel
SuperCube from IHES
Все они собраны в рамках проекта CayleyPy — это open-source crowd-sourcing инициатива для разработки AI-библиотеки по математике. Можно подключаться и вне Kaggle.
Если интересно поучаствовать, но кажется, что порог входа высокий — я могу сделать введение на созвоне и рассказать основы: что такое графы Кэли, как ставится задача и какие методы уже пробовали.
Продолжение тут и тут👇
#Puzzles #CayleyGraphs #SymmetricGroup #KaggleCompetitions
Telegram
Истории (не)успеха (ИИ)ЕИ
В общем, кратко, как это работает — а оно работает (см. тут):
1) Генерируем простым алгоритмом некоторое количество случайных прогулок по графу от собранного состояния до любых, куда заведёт генератор случайных чисел.
2) Компактифицируем дискретный граф…
1) Генерируем простым алгоритмом некоторое количество случайных прогулок по графу от собранного состояния до любых, куда заведёт генератор случайных чисел.
2) Компактифицируем дискретный граф…
👍4