Max Home IndustryЧисло Бога — это наименьшее количество ходов, необходимое для сборки общего кубика Рубика. Мы до сих пор не знаем размер числа Бога для любого куба, кроме стандартного 3x3x3, но теперь мы знаем, как оно зависит от размера куба, и примечательно то, что это становится легче по мере того, как куб становится больше.
Учитывая, что мы занимаемся созданием алгоритмов, вы не можете не задаться вопросом, сколько ходов требуется в целом, чтобы собрать кубик Рубика. Чтобы быть точным, мы хотели бы знать то, что стало называться «числом Бога», то есть наименьшее количество ходов, необходимых для сборки наихудшего из возможных кубов. В случае с привычным кубом 3x3x3 было доказано, что 20 ходов всегда достаточно, чтобы решить даже самую сложную путаницу. На поиск этого результата ушло 35 лет компьютерного времени.
Следующая задача — найти Число Бога для обобщенных кубов — обычно большего размера и поэтому его не так просто решить с помощью перебора. Вопрос в том, как сложность задачи масштабируется с размером куба?
Теперь ответ на этот вопрос есть в документе, который будет представлен на 19-м ежегодном европейском симпозиуме по алгоритмам в сентябре, написанном исследователями из Массачусетского технологического института, Университета Ватерлоо и Университета Тафтса.
Глупый подход к решению проблемы состоит в том, чтобы выполнить набор движений, которые помещают отдельный субкуб в его правильное положение, и повторять, пока все грани не будут завершены. Это дает верхнюю границу порядка n ^ 2 — поскольку количество субкубов всех граней пропорционально n ^ 2, однако хорошо известно, что обычно вы можете добиться большего, используя движения, которые размещают несколько субкубов. в правильное место. Эта эвристика теперь стала формальной, и это привело к тому, что порядок n ^ 2 / logn стал новой верхней границей. В той же статье было показано, что это также нижняя граница.
Это означает, что наименьшее количество ходов, необходимое для решения кубика Рубика nxnxn, пропорционально n ^ 2 / log (n).
Почему это удивительно?
Ну, количество ходов, пропорциональное n ^ 2, является просто отражением того факта, что большее количество поверхностей означает большее количество ходов, но почему это уменьшается на log (n) по мере увеличения размера куба? По мере того, как куб становится больше, должно увеличиваться количество ярлыков к простому решению.
Как n ^ 2 / log n зависит от n и насколько оно меньше, чем n ^ 2
Обратите внимание, что этот результат не сообщает нам Число Бога для куба любого размера, только то, что оно пропорционально n ^ 2 / logn.
Кроме того, в статье выводится асимптотически оптимальное решение для решения общего куба в наихудшем случае. Это также поднимает вопрос о том, сложно ли найти оптимальное решение для общего куба.
Алгоритмы решения кубиков Рубика (pdf)
Смотрите также:
Кубик Рубика прорыв