Комментарии 10
После своего появления в 1870-х годов она вошла в стандартный набор игр.
Разрешите поинтересоваться, что за набор?
N в четвёртой степени это как-то очень много.
На практике для маленьких размеров от исходного состояния невозможно уйти дальше фиксированного количества шагов. Для «пятнашки» 3х3 это всего 31 ход.
Можно проверить полным перебором 9! состояний.
На практике для маленьких размеров от исходного состояния невозможно уйти дальше фиксированного количества шагов. Для «пятнашки» 3х3 это всего 31 ход.
Можно проверить полным перебором 9! состояний.
… как возникает случайность?
Сделаем случайный выбор.
Так как всё-таки как возникает случайность? Получается, что случайность поля зависит только лишь от алгоритма случайного выбора и количества ходов (при упорядоченной начальной конфигурации).
для рандомизации поля n на n понадобится n4 ходов
Какой критерий рандомизационности поля они выбрали? И с какой вероятность должен выполняться этот критерий?
каждая плитка с равной вероятностью может находиться в любом квадрате поля
поле… с равной вероятностью может находиться в любом из своего множества возможных конфигураций
Откуда взялись эти определения? Начальная задача имеет совсем другое определение. Как они доказали, что случайное (неизвестное) передвижение пустой плитки при 256 (а не 100500) повторениях даёт нам именно равномерное распределение (а, например, не нормальное)?
Доказали
понадобится n4 ходов
не более чем примерно n4 log n ходов
Как доказали? Как проверили? Какие результаты?
Как они доказали, что случайное (неизвестное) передвижение пустой плитки при 256 (а не 100500) повторениях даёт нам именно равномерное распределение (а, например, не нормальное)?
В статье пропущено решение уравнений Колмогорова для марковского процесса, это просто большая СЛАУ, по которой можно вычислить финальные вероятности состояний.
Учитывая что они «Ради математической изящности» выкинули спец. условия на краях и в углах — скорее всего финальные вероятности состояний распределены равномерно.
По мере увеличения числа переходов вероятности будут стремиться к своим финальным значениям, вопрос лишь насколько быстро это произойдёт (ну и с какой точностью).
Однако вопросов действительно много.
Если рассмотреть шахматную доску (чётное N), то любое перемещение «пустого пространства» будет чередовать белые и чёрные клетки, что сделает часть состояний невозможными для любого фиксированного количества шагов. А это сложно назвать «случайным».
ЕМНИП, в пятнашках нельзя получить все возможные конфигурации. Существуют два сета. Один, который можно решить до "1..2....14..15" и второй, (зеркальный, что ли?) который можно решить до "1..2....15..14" (но не до "1..14..15").
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Математики на примере «пятнашек» вычисляют, как возникает случайность