Ханойская башня

Математическая головоломка

Модель Ханойской башни (с 8 дисками)

Анимированное решение головоломки «Ханойская башня» для T (4, 3)

Интерактивная экспозиция «Ханойская башня» в Музее Универсума в Мехико

Башня Ханоя (также называемая Проблема храма Бенареса ^[1] или Башня Брахмы или Башня Лукаса ^[2] и иногда употребляемая во множественном числе как Башни , или просто пирамидальная головоломка ^[3] ) - это математическая игра или головоломка , состоящая из трех стержней и ряда дисков разного диаметра , которые могут скользить по любому стержню. Головоломка начинается с дисков, сложенных на одном стержне в порядке убывания размера, наименьший наверху, таким образом приближаясь к конической форме. Цель головоломки - переместить всю стопку на один из других стержней, соблюдая следующие правила: ^[4]

1. За один раз можно перемещать только один диск.
2. Каждый ход заключается в том, что верхний диск берется из одной стопки и кладется на другую стопку или на пустой стержень.
3. Ни один диск не может быть помещен поверх диска, который меньше его.

С тремя дисками головоломку можно решить за семь ходов. Минимальное количество ходов, необходимое для решения головоломки «Ханойская башня», составляет 2 ⁿ − 1 , где n — количество дисков.

Происхождение

Головоломка была изобретена французским математиком Эдуардом Люка , впервые представлена ​​в 1883 году как игра, открытая «Н. Клаусом (де Сиамом)» (анаграмма «Лукас д'Амьен»), ^{[5] [6] [7]} и позже опубликована в виде брошюры в 1889 году ^[8] и в посмертно изданном томе Лукаса « Récréations mathématiques» . ^[9] К игре прилагалась инструкция, описывающая предполагаемое происхождение игры в Тонкине и утверждающая, что, согласно легенде, брахманы в храме в Бенаресе осуществляли движение «Священной башни Брахмы », состоящей из шестидесяти четырех золотых дисков, по тем же правилам, что и в игре, и что завершение строительства башни приведет к концу света. ^[10] Почти сразу же появились многочисленные вариации этой легенды относительно древней и мистической природы головоломки. ^[5]

Если бы легенда была правдой, и если бы жрецы могли перемещать диски со скоростью один в секунду, используя наименьшее количество ходов, им потребовалось бы 2 ⁶⁴  − 1 секунды или примерно 585 миллиардов лет, чтобы закончить ^[11], что примерно в 42 раза превышает предполагаемый текущий возраст Вселенной .

Существует множество вариаций этой легенды. Например, в некоторых рассказах храм — это монастырь , а священники — монахи . Храм или монастырь могут находиться в разных местах, включая Ханой , и могут быть связаны с любой религией . В некоторых версиях вводятся другие элементы, например, тот факт, что башня была создана в начале мира, или что священники или монахи могут делать только один ход в день.

Решение

В головоломку можно играть с любым количеством дисков, хотя во многих игрушечных версиях их около 7–9. Минимальное количество ходов, необходимое для решения головоломки «Ханойская башня» с n дисками, составляет 2 ⁿ − 1 . ^[12]

Итеративное решение

Анимация итерационного алгоритма решения задачи с 6 дисками

Простое решение для игрушечной головоломки — чередовать ходы между наименьшей частью и не наименьшей частью. При перемещении наименьшей части всегда перемещайте ее на следующую позицию в том же направлении (вправо, если начальное число частей четное, влево, если начальное число частей нечетное). Если в выбранном направлении нет позиции башни, переместите часть на противоположный конец, но затем продолжайте движение в правильном направлении. Например, если вы начали с трех частей, вы переместите наименьшую часть на противоположный конец, а затем продолжите движение в левом направлении. Когда очередь переместить не наименьшую часть, есть только один допустимый ход. Сделав это, вы завершите головоломку за наименьшее количество ходов. ^[13]

Более простая формулировка итеративного решения

Итеративное решение эквивалентно повторному выполнению следующей последовательности шагов до тех пор, пока цель не будет достигнута:

• Переместите один диск со штифта A на штифт B или наоборот, в зависимости от того, какой ход является допустимым.
• Переместите один диск со стержня A на стержень C или наоборот, в зависимости от того, какой ход является допустимым.
• Переместите один диск со штифта B на штифт C или наоборот, в зависимости от того, какой ход является допустимым.

При таком подходе стек окажется на колышке B, если количество дисков нечетное, и на колышке C, если количество дисков четное.

Рекурсивное решение

Иллюстрация рекурсивного решения для головоломки «Ханойские башни» с 4 дисками. В файле SVG нажмите серую кнопку, чтобы развернуть или свернуть его

Ключ к рекурсивному решению проблемы — признать, что ее можно разбить на набор более мелких подзадач, к каждой из которых применяется та же общая процедура решения, которую мы ищем ^{[ требуется ссылка ]} , а затем общее решение находится каким-то простым способом из решений этих подзадач. Каждая из этих созданных подзадач, будучи «меньше», гарантирует, что базовый случай(ы) в конечном итоге будет достигнут. Для башен Ханоя:

• Пометьте колышки буквами A, B, C,
• пусть n — общее количество дисков, а
• пронумеруйте диски от 1 (самый маленький, самый верхний) до n (самый большой, самый нижний).

Предположим, что все n дисков распределены по колышкам в допустимых расположениях; предположим, что на исходном колышке находится m верхних дисков , а все остальные диски больше m , поэтому их можно смело игнорировать; чтобы переместить m дисков с исходного колышка на целевой колышек, используя запасной колышек, не нарушая правил:

1. Переместите m − 1 дисков из исходного в запасной колышек, используя ту же общую процедуру решения . Правила не нарушаются, по предположению. Это оставляет диск m в качестве верхнего диска на исходном колышке.
2. Переместите диск m из исходного в целевой колышек, что гарантированно является допустимым ходом, согласно предположениям — простой шаг .
3. Переместим m − 1 диск, который мы только что положили на запасной, с запасного на целевой колышек, используя ту же общую процедуру решения , так, чтобы они были помещены на диск m, не нарушая правил.
4. Базовый вариант — переместить 0 дисков (на шагах 1 и 3), то есть ничего не делать, что не нарушает правила.

Затем полное решение «Ханойской башни» перемещает n дисков с исходного колышка A на целевой колышек C, используя B в качестве запасного колышка.

Этот подход можно строго доказать с помощью математической индукции , и он часто используется в качестве примера рекурсии при обучении программированию.

Логический анализ рекурсивного решения

Как и во многих математических головоломках, найти решение проще, решив немного более общую задачу: как переместить башню из h (высота) дисков с начального колышка f = A (от) на конечный колышек t = C (до), где B — оставшийся третий колышек, и предположим, что t ≠ f . Во-первых, заметим, что задача симметрична относительно перестановок имен колышков ( симметричная группа S ₃ ). Если известно решение для перемещения со колышка A на колышек C , то, переименовав колышки, можно использовать то же самое решение для любого другого выбора начального и конечного колышка. Если есть только один диск (или даже ни одного), задача тривиальна. Если h = 1, то переместите диск со колышка A на колышек C . Если h > 1, то где-то в последовательности перемещений самый большой диск должен быть перемещен со колышка A на другой колышек, предпочтительно на колышек C . Единственная ситуация, которая допускает этот ход, — это когда все меньшие h − 1 дисков находятся на колышке B. Следовательно, сначала все h − 1 меньших дисков должны перейти из A в B. Затем переместить самый большой диск и, наконец, переместить h − 1 меньших дисков со колышка B на колышек C. Наличие самого большого диска не препятствует перемещению h − 1 меньших дисков и может быть временно проигнорировано. Теперь задача сводится к перемещению h − 1 дисков с одного колышка на другой, сначала с A на B , а затем с B на C , но тот же метод можно использовать оба раза, переименовав колышки. Та же стратегия может быть использована для сведения задачи h − 1 к h − 2, h − 3 и так далее, пока не останется только один диск. Это называется рекурсией. Этот алгоритм можно схематизировать следующим образом.

Определите диски в порядке возрастания размера по натуральным числам от 0 до, но не включая h . Таким образом, диск 0 — наименьший, а диск h − 1 — наибольший.

Ниже приведена процедура перемещения башни из h дисков со штифта A на штифт C , где B — оставшийся третий штифт:

1. Если h > 1, то сначала используйте эту процедуру , чтобы переместить h − 1 меньших дисков со штифта A на штифт B.
2. Теперь самый большой диск, т.е. диск h, можно переместить со штифта A на штифт C.
3. Если h > 1, то снова используйте эту процедуру , чтобы переместить h − 1 меньших дисков со штифта B на штифт C.

С помощью математической индукции легко доказать, что вышеприведенная процедура требует минимально возможного количества ходов и что полученное решение является единственным с этим минимальным количеством ходов. Используя рекуррентные соотношения , точное количество ходов, которое требуется этому решению, можно вычислить следующим образом: . Этот результат получается, если отметить, что шаги 1 и 3 требуют ходов, а шаг 2 требует одного хода, что дает . ${\displaystyle 2^{h}-1}$ ${\displaystyle T_{h-1}}$ ${\displaystyle T_{h}=2T_{h-1}+1}$

Нерекурсивное решение

Список ходов для башни, переносимой с одного колышка на другой, созданный рекурсивным алгоритмом, имеет много закономерностей. При подсчете ходов, начиная с 1, порядковый номер диска, который должен быть перемещен во время хода m , равен числу раз, которое m может быть разделено на 2. Следовательно, каждый нечетный ход включает в себя наименьший диск. Можно также заметить, что наименьший диск проходит через колышки f , t , r , f , t , r и т. д. для нечетной высоты башни и проходит через колышки f , r , t , f , r , t и т. д. для четной высоты башни. Это дает следующий алгоритм, который проще выполнить вручную, чем рекурсивный алгоритм.

В альтернативных ходах:

• Переместите самый маленький диск на тот колышек, с которого он недавно не снимался.
• Переместите другой диск законным образом (будет только одна возможность).

Для самого первого хода самый маленький диск кладется на колышек t, если h нечетное, и на колышек r, если h четное.

Также обратите внимание, что:

• Диски, порядковые номера которых имеют четную четность, движутся в том же направлении, что и наименьший диск.
• Диски, порядковые номера которых имеют нечетную четность, движутся в противоположном направлении.
• Если h четное, то оставшийся третий колышек при последовательных ходах — это t , r , f , t , r , f и т. д.
• Если h нечетное, то оставшийся третий колышек при последовательных ходах — r , t , f , r , t , f и т. д.

Обладая этими знаниями, можно восстановить набор дисков в середине оптимального решения, имея не больше информации о состоянии, чем позиции каждого диска:

• Назовите описанные выше ходы «естественным» ходом диска.
• Изучите наименьший верхний диск, который не является диском 0, и обратите внимание, каким будет его единственный (разрешенный) ход: если такого диска нет, то мы находимся либо на первом, либо на последнем ходу.
• Если этот ход является «естественным» ходом диска, то диск не был перемещен с момента последнего хода диска 0, и этот ход следует выполнить.
• Если этот ход не является «естественным» ходом диска, то переместите диск 0.

Двоичное решение

Позиции диска можно определить более непосредственно из двоичного (с основанием 2) представления номера хода (начальное состояние — ход № 0, все цифры 0, а конечное состояние — все цифры 1), используя следующие правила:

• Для каждого диска имеется одна двоичная цифра ( бит ).
• Самый значимый (самый левый) бит представляет наибольший диск. Значение 0 указывает, что наибольший диск находится на начальном штифте, а 1 указывает, что он находится на конечном штифте (правом штифте, если количество дисков нечетное, и среднем штифте в противном случае).
• Битовая строка считывается слева направо, и каждый бит можно использовать для определения местоположения соответствующего диска.
• Бит с тем же значением, что и у предыдущего, означает, что соответствующий диск помещен поверх предыдущего диска на тот же штифт.

  (То есть прямая последовательность единиц или нулей означает, что соответствующие диски находятся на одном и том же штифте.)

• Бит с другим значением, чем предыдущий, означает, что соответствующий диск находится на одну позицию левее или правее предыдущего. Является ли он левым или правым, определяется следующим правилом:
  • Предположим, что начальный колышек находится слева.
  • Также предположим «обёртывание» — так, чтобы правый колышек считался одним колышком «левее» левого колышка, и наоборот.
  • Пусть n будет числом больших дисков, которые расположены на том же колышке, что и их первый больший диск, и добавьте 1, если самый большой диск находится на левом колышке. Если n четное, диск расположен на один колышек правее, если n нечетное, диск расположен на один колышек левее (в случае четного числа дисков и наоборот в противном случае).

Например, в 8-дисковом Ханое:

• Переместить 0 = 00000000.
  • Самый большой диск — 0, поэтому он находится на левом (начальном) штифте.
  • Все остальные диски также имеют номер 0, поэтому они укладываются на него. Следовательно, все диски находятся на начальном колышке.
• Ход 2 ⁸ − 1 = 11111111.
  • Самый большой диск — 1, поэтому он находится на среднем (последнем) штифте.
  • Все остальные диски также имеют номер 1, поэтому они укладываются на него. Таким образом, все диски находятся на последнем колышке, и головоломка завершена.
• Ход 216 ₁₀ = 11011000.
  • Самый большой диск — 1, поэтому он находится на среднем (последнем) штифте.
  • Диск два также имеет номер 1, поэтому он устанавливается сверху, на средний штифт.
  • Диск три — 0, поэтому он на другом колышке. Поскольку n нечетное ( n = 1), он на один колышек левее, т.е. на левом колышке.
  • Диск четыре — 1, поэтому он на другом колышке. Поскольку n нечетное ( n = 1), он на один колышек левее, т.е. на правом колышке.
  • Пятый диск также имеет номер 1, поэтому он кладется сверху, на правый штифт.
  • Диск шесть — это 0, поэтому он на другом колышке. Поскольку n четное ( n = 2), диск находится на один колышек правее, т.е. на левом колышке.
  • Диски семь и восемь также имеют номер 0, поэтому они уложены сверху, на левом штифте.

Исходный и конечный колышки для m -го хода также можно элегантно найти из двоичного представления m с помощью побитовых операций . Если использовать синтаксис языка программирования C , ход m выполняется от колышка (m & m - 1) % 3к колышку ((m | m - 1) + 1) % 3, где диски начинаются на колышке 0 и заканчиваются на колышке 1 или 2 в зависимости от того, четное или нечетное число дисков. Другая формулировка — от колышка (m - (m & -m)) % 3к колышку (m + (m & -m)) % 3.

Кроме того, диск, который нужно переместить, определяется числом раз, которое счетчик перемещений ( m ) может быть разделен на 2 (т. е. числом нулевых битов справа), считая первый ход за 1 и идентифицируя диски числами 0, 1, 2 и т. д. в порядке увеличения размера. Это позволяет очень быстрой нерекурсивной компьютерной реализации находить позиции дисков после m перемещений без ссылки на какой-либо предыдущий ход или распределение дисков.

Операция, которая подсчитывает количество последовательных нулей в конце двоичного числа, дает простое решение проблемы: диски нумеруются с нуля, и при перемещении m количество конечных нулей номера диска перемещается на минимально возможное расстояние вправо (при необходимости возвращаясь влево). ^[14]

Решение в коде Грея

Двоичная система счисления кодов Грея дает альтернативный способ решения головоломки. В системе Грея числа выражаются двоичной комбинацией нулей и единиц, но вместо того, чтобы быть стандартной позиционной системой счисления , код Грея работает на основе предпосылки, что каждое значение отличается от своего предшественника только одним измененным битом.

Если подсчитать в коде Грея размер бит, равный количеству дисков в конкретной Ханойской башне, начать с нуля и вести отсчет по возрастанию, то бит, изменяемый при каждом ходе, будет соответствовать перемещаемому диску, где наименее значимый бит — это наименьший диск, а наиболее значимый бит — наибольший.

Если подсчитывать ходы с 1 и обозначать диски номерами, начиная с 0 в порядке увеличения размера, то порядковый номер диска, который будет перемещен во время хода m, равен числу раз, которое m можно разделить на 2.

Этот метод определяет, какой диск переместить, но не куда его переместить. Для наименьшего диска всегда есть две возможности. Для других дисков всегда есть одна возможность, за исключением случая, когда все диски находятся на одном колышке, но в этом случае либо нужно переместить наименьший диск, либо цель уже достигнута. К счастью, есть правило, которое говорит, куда переместить наименьший диск. Пусть f будет начальным колышком, t — конечным колышком, а r — оставшимся третьим колышком. Если количество дисков нечетное, наименьший диск циклически перемещается по колышкам в порядке f → t → r → f → t → r и т. д. Если количество дисков четное, это должно быть наоборот: f → r → t → f → r → t и т. д. ^[15]

Положение изменения бита в решении кода Грея дает размер диска, перемещаемого на каждом шаге: 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, ... (последовательность A001511 в OEIS ), ^[16] последовательность, также известная как функция линейки , или на единицу больше степени 2 в числе ходов. В языке Wolfram Language дает IntegerExponent[Range[2^8 - 1], 2] + 1ходы для головоломки с 8 дисками.

Графическое представление

Игра может быть представлена ​​неориентированным графом , узлы которого представляют распределение дисков, а ребра — ходы. Для одного диска граф представляет собой треугольник:

Граф для двух дисков представляет собой три треугольника, соединенных так, чтобы образовать углы большего треугольника.

Вторая буква добавляется для обозначения большего диска. Очевидно, что изначально его нельзя переместить.

Самый верхний маленький треугольник теперь представляет возможности одного хода с двумя дисками:

Узлы в вершинах внешнего треугольника представляют собой распределения, в которых все диски находятся на одном и том же штифте.

Для h + 1 дисков возьмите график h дисков и замените каждый маленький треугольник графиком для двух дисков.

Для трех дисков график имеет вид:

Граф игры 7-го уровня показывает связь с треугольником Серпинского .

• назовите колышки a, b и c
• список позиций на диске слева направо в порядке увеличения размера

Стороны самого внешнего треугольника представляют собой кратчайшие пути перемещения башни с одного колышка на другой. Ребро в середине сторон самого большого треугольника представляет собой ход самого большого диска. Ребро в середине сторон каждого следующего меньшего треугольника представляет собой ход каждого следующего меньшего диска. Стороны самых маленьких треугольников представляют собой ходы самого маленького диска.

В общем случае для головоломки с n дисками в графе есть 3 n узлов; каждый узел имеет три ребра к другим узлам, за исключением трех угловых узлов, у которых их два: всегда можно переместить наименьший диск на один из двух других колышков, и можно переместить один диск между этими двумя колышками, за исключением ситуации, когда все диски уложены на один колышек. Угловые узлы представляют три случая, когда все диски уложены на один колышек. Диаграмма для n  + 1 дисков получается путем взятия трех копий диаграммы n -дисков — каждая из которых представляет все состояния и перемещения меньших дисков для одной конкретной позиции нового наибольшего диска — и соединения их в углах тремя новыми ребрами, представляющими единственные три возможности переместить наибольший диск. Таким образом, полученная фигура имеет 3 ^{n + 1} узлов и все еще имеет три угла, оставшихся только с двумя ребрами.

По мере добавления большего количества дисков графическое представление игры будет напоминать фрактальную фигуру, треугольник Серпинского . Очевидно, что подавляющее большинство позиций в головоломке никогда не будут достигнуты при использовании кратчайшего возможного решения; действительно, если жрецы легенды используют самое длинное возможное решение (не посещая повторно ни одну позицию), им потребуется 3 ⁶⁴  − 1 ходов, или более 10 ²³ лет.

Самый длинный неповторяющийся путь для трех дисков можно визуализировать, удалив неиспользуемые ребра:

Кстати, этот самый длинный неповторяющийся путь можно получить, запретив все ходы из a в c .

Гамильтонов цикл для трех дисков имеет вид:

Графики наглядно показывают, что:

• Из любого произвольного распределения дисков существует ровно один кратчайший способ переместить все диски на один из трех колышков.
• Между каждой парой произвольных распределений дисков существует один или два различных кратчайших пути.
• Из каждого произвольного распределения дисков существует один или два различных самых длинных несамопересекающихся пути, позволяющих переместить все диски на один из трех колышков.
• Между каждой парой произвольных распределений дисков существуют один или два различных самых длинных несамопересекающихся пути.
• Пусть N _h — число несамопересекающихся путей для перемещения башни из h дисков с одного колышка на другой. Тогда:
  • N ₁ = 2
  • Н _{ч +1} = ( Н _ч ) ² + ( Н _ч ) ³

Это дает N _h 2, 12, 1872, 6563711232, ... (последовательность A125295 в OEIS )

Вариации

Линейный Ханой

Если все перемещения должны быть между соседними колышками (т. е. если колышки A, B, C, нельзя перемещаться напрямую между колышками A и C), то перемещение стопки из n дисков со колышка A на колышек C занимает 3 ⁿ − 1 перемещений. Решение использует все 3 ⁿ допустимых позиций, всегда выбирая единственный ход, который не отменяет предыдущий ход. Положение со всеми дисками на колышке B достигается на полпути, т. е. после (3 ⁿ − 1) / 2 перемещений. ^{[17] [18]}

Циклический Ханой

В Cyclic Hanoi нам даны три колышка (A, B, C), которые расположены в виде круга с направлениями по часовой стрелке и против часовой стрелки, определяемыми как A – B – C – A и A – C – B – A соответственно. Направление движения диска должно быть по часовой стрелке. ^[19] Достаточно представить последовательность дисков, которые нужно переместить. Решение можно найти с помощью двух взаимно рекурсивных процедур:

Чтобы переместить n дисков против часовой стрелки к соседнему целевому штифту:

1. переместите n − 1 дисков против часовой стрелки к целевому колышку
2. переместить диск № n на один шаг по часовой стрелке
3. переместите n − 1 дисков по часовой стрелке на начальный штифт
4. переместить диск № n на один шаг по часовой стрелке
5. переместите n − 1 дисков против часовой стрелки к целевому колышку

Чтобы переместить n дисков по часовой стрелке к соседнему целевому штифту:

1. переместите n − 1 дисков против часовой стрелки на свободный штифт
2. переместить диск № n на один шаг по часовой стрелке
3. переместите n − 1 дисков против часовой стрелки к целевому колышку

Пусть C(n) и A(n) представляют собой движущиеся n дисков по часовой стрелке и против часовой стрелки, тогда мы можем записать обе формулы:

Решение для циклического Ханоя имеет некоторые интересные свойства:

1. Схемы перемещения башни дисков со штифта на другой штифт симметричны относительно центральных точек.
2. Наименьший диск — это первый и последний перемещаемый диск.
3. Группы наименьших ходов дисков чередуются с одиночными ходами других дисков.
4. Число ходов дисков, указанное C(n) и A(n), минимально.

С четырьмя колышками и больше

Хотя версия с тремя колышками имеет простое рекурсивное решение, известное давно, оптимальное решение задачи о Ханойской башне с четырьмя колышками (называемой головоломкой Рива) не было проверено до 2014 года Бушем. ^[20]

Однако в случае четырех и более колышков алгоритм Фрейма–Стюарта известен без доказательства оптимальности с 1941 года. ^[21]

Для формального вывода точного числа минимальных ходов, необходимых для решения задачи с применением алгоритма Фрейма–Стюарта (и других эквивалентных методов), см. следующую статью. ^[22]

Другие варианты задачи о четырехколышечной Ханойской башне см. в обзорной статье Пола Стокмейера. ^[23]

Так называемые игровые конфигурации «Башни Бухареста» и «Башни Клагенфурта» дают троичные и пятеричные коды Грея. ^[24]

Алгоритм Фрейма–Стюарта

Алгоритм Фрейма–Стюарта описан ниже:

• Пусть — количество дисков. ${\displaystyle n}$
• Пусть — число колышков. ${\displaystyle r}$
• Определим как минимальное количество ходов, необходимое для перемещения n дисков с использованием r колышков. ${\displaystyle T(n,r)}$

Алгоритм можно описать рекурсивно:

1. Для некоторых , , перенесите верхние диски на один колышек, отличный от начального или конечного колышка, делая ходы. ${\displaystyle k}$ ${\displaystyle 1\leq k<n}$ ${\displaystyle k}$ ${\displaystyle T(k,r)}$
2. Не трогая колышек, на котором теперь находятся верхние диски, перенесите оставшиеся диски на целевой колышек, используя только оставшиеся колышки и совершая ходы. ${\displaystyle k}$ ${\displaystyle n-k}$ ${\displaystyle r-1}$ ${\displaystyle T(n-k,r-1)}$
3. Наконец, переместите верхние диски на конечный колышек, делая ходы. ${\displaystyle k}$ ${\displaystyle T(k,r)}$

Весь процесс занимает ходов. Поэтому следует выбрать количество , для которого это количество минимально. В случае 4-х колышков оптимальное значение равно , где — ближайшая целочисленная функция . ^[25] Например, в курсе UPenn CIS 194 по Haskell на первой странице заданий ^[26] указано оптимальное решение для случая 15 дисков и 4-х колышков в размере 129 шагов, что получается для указанного выше значения k . ${\displaystyle 2T(k,r)+T(n-k,r-1)}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle n-\left\lfloor {\sqrt {2n+1}}\right\rceil +1}$ ${\displaystyle \left\lfloor \cdot \right\rceil }$

Предполагается, что этот алгоритм оптимален для любого количества колышков; его количество ходов равно 2 ^{Θ ( n 1/( r −2) )} (для фиксированного r ).

Общие кратчайшие пути и число 466/885

Любопытное обобщение изначальной цели головоломки — начать с заданной конфигурации дисков, где все диски не обязательно находятся на одном колышке, и прийти за минимальное количество ходов к другой заданной конфигурации. В общем, может быть довольно сложно вычислить кратчайшую последовательность ходов для решения этой задачи. Решение было предложено Андреасом Хинцем и основано на наблюдении, что в кратчайшей последовательности ходов наибольший диск, который необходимо переместить (очевидно, можно игнорировать все наибольшие диски, которые будут занимать один и тот же колышек как в начальной, так и в конечной конфигурации), переместится либо ровно один раз, либо ровно два раза.

Математика, связанная с этой обобщенной задачей, становится еще интереснее, если рассмотреть среднее число ходов в кратчайшей последовательности ходов между двумя начальными и конечными конфигурациями дисков, которые выбираются случайным образом. Хинц и Чан Тат-Хунг независимо друг от друга обнаружили ^{[27] [28]} (см. также ^{[29] : Глава 1, стр. 14} ), что среднее число ходов в n-дисковой башне определяется следующей точной формулой:

${\displaystyle {\frac {466}{885}}\cdot 2^{n}-{\frac {1}{3}}-{\frac {3}{5}}\cdot \left({\frac {1}{3}}\right)^{n}+\left({\frac {12}{59}}+{\frac {18}{1003}}{\sqrt {17}}\right)\left({\frac {5+{\sqrt {17}}}{18}}\right)^{n}+\left({\frac {12}{59}}-{\frac {18}{1003}}{\sqrt {17}}\right)\left({\frac {5-{\sqrt {17}}}{18}}\right)^{n}.}$

Для достаточно большого n только первый и второй члены не сходятся к нулю, поэтому мы получаем асимптотическое выражение : , как . Таким образом, интуитивно мы могли бы интерпретировать дробь как представляющую отношение труда, который нужно выполнить при переходе от случайно выбранной конфигурации к другой случайно выбранной конфигурации, относительно трудности пересечения «самого трудного» пути длины, который включает перемещение всех дисков с одного колышка на другой. Альтернативное объяснение появления константы 466/885, а также новый и несколько улучшенный алгоритм вычисления кратчайшего пути были даны Ромиком. ^[30] ${\displaystyle 466/885\cdot 2^{n}-1/3+o(1)}$ ${\displaystyle n\to \infty }$ ${\displaystyle 466/885\approx 52.6\%}$ ${\displaystyle 2^{n}-1}$

Магнитный Ханой

В Магнитной башне Ханоя каждый диск имеет две отдельные стороны: Север и Юг (обычно окрашенные в «красный» и «синий»). Диски нельзя размещать с одинаковыми полюсами вместе — магниты в каждом диске предотвращают этот незаконный ход. Кроме того, каждый диск должен быть перевернут при перемещении.

Начальная конфигурация двухцветных башен Ханоя (n=4)

Двухцветные башни Ханоя

Этот вариант знаменитой головоломки «Ханойская башня» был предложен ученикам 3–6 классов на ² -м чемпионате Франции по математическим и логическим играм, проходившем в июле 1988 года.

Окончательная конфигурация двухцветных башен Ханоя (n=4)

Правила головоломки по сути те же: диски переносятся между колышками по одному. Ни в коем случае нельзя класть больший диск на меньший. Разница в том, что теперь для каждого размера есть два диска: один черный и один белый. Также теперь есть две башни из дисков чередующихся цветов. Цель головоломки — сделать башни монохромными (одного цвета). Предполагается, что самые большие диски внизу башен меняются местами.

Ханойская башня

Вариант головоломки был адаптирован в виде игры-солитера с девятью игральными картами под названием « Башня Ханоя» . ^{[32] [33]} Неизвестно, является ли измененное написание оригинального названия преднамеренным или случайным. ^[34]

Приложения

Топографическое 3D-изображение АСМ многослойного палладиевого нанолиста на кремниевой пластине со структурой, похожей на Ханойскую башню. ^[35]

Ханойская башня часто используется в психологических исследованиях по решению проблем . Существует также вариант этой задачи под названием «Лондонская башня» для нейропсихологической диагностики и лечения расстройств исполнительной функции . ^[36]

Чжан и Норман ^[37] использовали несколько изоморфных (эквивалентных) представлений игры для изучения влияния эффекта представления в дизайне задач. Они продемонстрировали влияние на производительность пользователя, изменив способ представления правил игры, используя вариации в физическом дизайне компонентов игры. Эти знания повлияли на разработку фреймворка TURF ^[38] для представления взаимодействия человека и компьютера .

Ханойская башня также используется в качестве схемы ротации резервных копий при выполнении резервного копирования компьютерных данных, когда задействовано несколько лент/носителей. ^{[ необходима ссылка ]}

Как упоминалось выше, Ханойская башня популярна для обучения рекурсивным алгоритмам начинающих программистов. Иллюстрированная версия этой головоломки запрограммирована в редакторе emacs , доступ к которому осуществляется путем ввода Mx hanoi. Также имеется пример алгоритма, написанного на Prolog . ^{[ требуется цитата ]}

Ханойская башня также используется нейропсихологами в качестве теста, пытающимися оценить дефицит лобных долей . ^[39]

В 2010 году исследователи опубликовали результаты эксперимента, который показал, что вид муравьев Linepithema humile успешно смог решить трехдисковую версию задачи о Ханойской башне с помощью нелинейной динамики и феромонных сигналов. ^[40]

В 2014 году ученые синтезировали многослойные палладиевые нанолисты со структурой, похожей на Ханойскую башню. ^[35]

В популярной культуре

В научно-фантастическом рассказе «Now Inhale» Эрика Фрэнка Рассела человек содержится в плену на планете, где местный обычай заключается в том, чтобы заставлять пленника играть в игру, пока она не будет выиграна или проиграна, прежде чем его казнят. Главный герой знает, что спасательный корабль может прибыть через год или больше, поэтому он решает сыграть в Towers of Hanoi с 64 дисками. Эта история отсылает к легенде о буддийских монахах, игравших в эту игру до конца света. ^{[41] [42] [43]}

В рассказе «Небесный игрушечник» 1966 года о Докторе Кто злодей заставляет Доктора играть в игру «Ханойская башня» из десяти фигур, состоящую из 1023 ходов, под названием «Трилогическая игра», в которой фигуры, сложенные друг на друга, образуют пирамиду. ^{[42] [44]}

В 2007 году концепция задачи о ханойских башнях была использована в головоломках 6, 83 и 84 в игре Professor Layton and the Diabolical Box , но диски были заменены на блины. Головоломка была основана на дилемме, в которой шеф-повар ресторана должен был переместить стопку блинов с одной тарелки на другую, используя основные принципы оригинальной головоломки (т. е. три тарелки, на которые можно было переложить блины, невозможность положить больший блин на меньший и т. д.)

В фильме 2011 года « Восстание планеты обезьян » эта головоломка, названная в фильме «Башня Лукаса», используется в качестве теста для изучения интеллекта обезьян. ^[42]

Головоломка регулярно появляется в приключенческих играх и головоломках . Поскольку ее легко реализовать и легко распознать, она хорошо подходит для использования в качестве головоломки в более крупной графической игре (например, Star Wars: Knights of the Old Republic и Mass Effect ). ^[45] Некоторые реализации используют прямые диски, но другие маскируют головоломку в какой-то другой форме. Существует аркадная версия от Sega . ^[46]

15-дисковая версия головоломки появляется в игре Sunless Sea как замок в гробнице. Игрок имеет возможность кликать по каждому ходу головоломки, чтобы решить ее, но игра отмечает, что для ее завершения потребуется 32 767 ходов. Если особенно преданный игрок кликает до конца головоломки, выясняется, что завершение головоломки не открывает дверь.

Впервые это было использовано в качестве испытания в Survivor Thailand в 2002 году, но вместо колец детали были сделаны в виде храма. Сук Джай бросила вызов, чтобы избавиться от Джеда, хотя Ши-Энн прекрасно знала, как завершить головоломку. Задача представлена ​​как часть наградного испытания в эпизоде ​​2011 года американской версии сериала Survivor TV . Оба игрока ( Оззи Ласт и Бенджамин «Тренер» Уэйд ) изо всех сил пытались понять, как решить головоломку, и им помогали их соплеменники.

В Genshin Impact эта головоломка показана в квесте-тусовке Фарузан "Early Learning Mechanism", где она упоминает, что видит ее как механизм и использует ее для создания прототипа игрушки для детей. Она называет это стеками пагоды .

Смотрите также

• Модель ABACABA
• Резервная схема ротации , приложение TOH
• Багенадье
• Рекурсия (информатика)
• « Девять миллиардов имен Бога », 1953 год, рассказ Артура Кларка с предпосылкой, схожей с сюжетом игры.

Примечания

1. "A000225 - OEIS". oeis.org . Получено 2021-09-03 .
2. Хофштадтер, Дуглас Р. (1985). Метамагические темы: поиски сущности разума и паттерна . Нью-Йорк: Basic Books. ISBN 978-0-465-04540-2.
3. Кон, Эрнст М. (1963). «Устройство для демонстрации некоторых элементарных свойств целых чисел». Учитель математики . 56 (2). Национальный совет учителей математики: 84. doi :10.5951/MT.56.2.0084. ISSN  0025-5769 . Получено 9 марта 2021 г.
4. Weisstein, Eric W. "Ханойская башня". mathworld.wolfram.com . Получено 20.10.2023 .
5. Хинц, Андреас М.; Клавжар, Санди; Милутинович, Урош; Петр, Кирилл (31 января 2013 г.). Ханойская башня – мифы и математика . Спрингер. ISBN 978-3034802369.
6. Стокмейер, Пол К. «Ханойская башня: библиография» (PDF) . Получено 21.02.2024 .
7. де Парвиль, Анри (1883-12-27). «Ревю наук». Журнал дебатов . Проверено 21 февраля 2024 г.
8. Лукас, Эдуард (1889). Jeux scientifiques pour servir à l'histoire, à l'enseignement et à la pratique du Calcul et du Dessin (на французском языке). Париж: Шамбон и Бай . Проверено 27 января 2024 г.
9. Лукас, Эдуард (1892). Récréations mathématiques (на французском языке). Том. 3. Библиотека Альберта Бланшара, 1979. с. 58.
10. Стокмейер, Пол К. «Инструкции по Ханойской башне на английском языке, страница 1» . Получено 21.02.2024 .
11. Москович, Иван (2001). 1000 игровых мыслей: головоломки, парадоксы, иллюзии и игры . Workman. ISBN 978-0-7611-1826-8.
12. Петкович, Миодраг (2009). Знаменитые головоломки великих математиков . AMS Bookstore. стр. 197. ISBN 978-0-8218-4814-2.
13. Трошкин, М. «Судный день наступает: нерекурсивный анализ рекурсивной задачи о ханойских башнях». Фокус . 95 (2): 10–14.
14. Уоррен, Генри С. (2003). "Раздел 5-4: Подсчет конечных нулей". Hacker's delight (1-е изд.). Boston MA: Addison-Wesley. ISBN 978-0-201-91465-8.
15. Миллер, Чарльз Д. (2000). "Гл. 4: Двоичные числа и стандартный код Грея". Математические идеи (9-е изд.). Эддисон Уэсли Лонгман. ISBN 978-0-321-07607-6. Архивировано из оригинала 2004-08-21.
16. Грос, Л. (1872). Теория дю Багенодье . Лион: Эме Вентринье.
17. "Уголок вопросов — Обобщение задачи о ханойских башнях". math.toronto.edu . Получено 28.07.2023 .
18. Хинц, Андреас М.; Клавзар, Санди; Милутинович, Урош; Петр, Сирил; Стюарт, Ян (2013). Ханойская башня – мифы и математика (1-е изд.). Базель: Springer Science+Business Media . С. 241–259. ISBN 9783034802369.
19. Гедеон, ТД (1996). «Циклические башни Ханоя: итеративное решение, полученное путем преобразования». The Computer Journal . 39 (4): 353–356. doi :10.1093/comjnl/39.4.353.
20. Буш, Т. (2014). «Кватриемный тур по Ханое» (PDF) . Бык. Бельг. Математика. Соц. Саймон Стевин . 21 (5): 895–912. дои : 10.36045/bbms/1420071861. S2CID  14243013. Архивировано из оригинала (PDF) 21 сентября 2017 г.
21. Стюарт, Б. М.; Фрейм, Дж. С. (март 1941 г.). «Решение сложной задачи 3819». American Mathematical Monthly . 48 (3): 216–9. doi :10.2307/2304268. JSTOR  2304268.
22. Клавзар, Санди; Милутинови, Уро; Петрб, Сирил (2002). «Вариации на тему головоломки «Четырехстоечная Ханойская башня» (Постскриптум)» . Congressus Numerantium . 102 .
23. Стокмейер, Пол (1994). «Вариации на тему головоломки «Четырехстоечная Ханойская башня»» (Постскриптум) . Congressus Numerantium . 102 : 3–12.
24. Herter, Felix; Rote, Günter (2018-11-14) [2018-08-09, 2017-12, 2017-08-09, 2016-04-22]. "Loopless Gray Code Enumeration and the Tower of Bucharest" (PDF) . Theoretical Computer Science . 748 . Berlin, Germany: 40–54. arXiv : 1604.06707 . doi :10.1016/j.tcs.2017.11.017. ISSN  0304-3975. S2CID  4014870. Архивировано (PDF) из оригинала 2020-12-16 . Получено 2020-12-16 .[1] (15/18/19/24 страницы)
25. "University of Toronto CSC148 Slog". 5 апреля 2014 г. Получено 22 июля 2015 г.
26. "UPenn CIS 194 Введение в Haskell Задание 1" (PDF) . Получено 31 января 2016 г. .
27. Хинц, А. (1989). «Ханойская башня». L'Enseignement Mathématique . 35 : 289–321. дои : 10.5169/уплотнения-57378.
28. Чан, Т. (1988). «Статистический анализ проблемы ханойских башен». Internat. J. Comput. Math . 28 (1–4): 57–65. doi :10.1080/00207168908803728.
29. Стюарт, Ян (2004). Еще одна прекрасная математика, в которую вы меня втянули... . Курьер Довер. ISBN 978-0-7167-2342-4.
30. Ромик, Д. (2006). «Кратчайшие пути в графе Ханойской башни и конечные автоматы». Журнал SIAM по дискретной математике . 20 (3): 610–622. arXiv : math/0310109 . doi :10.1137/050628660. S2CID  8342396.
31. Прасад Витал Чаугуле (2015). «Рекурсивное решение задачи о двухцветных ханойских башнях» (PDF) . Журнал занимательной математики (4): 37–48. ISSN  2182-1976.
32. Арнольд, Питер (28.05.2003). Карточные игры для одного. Sterling Publishing Company. ISBN 978-0-600-60727-4.
33. Хеджес, Сид Г. (2018-03-06). Книга о хобби для всех. Read Books Ltd. ISBN 978-1-5287-8344-6.
34. "Башня терпения Ханоя (AKA Башня терпения Ханоя)". bbcmicro.co.uk . Получено 17 октября 2020 г.
35. Yin, Xi; Liu, Xinhong; Pan, Yung-Tin; Walsh, Kathleen A.; Yang, Hong (4 ноября 2014 г.). «Hanoi Tower-like Multilayered Ultrathin Palladium Nanosheets». Nano Letters . 14 (12): 7188–94. Bibcode : 2014NanoL..14.7188Y. doi : 10.1021/nl503879a. PMID  25369350.
36. Shallice, T. (1982-06-25). «Специфические нарушения планирования». Philosophical Transactions of the Royal Society of London. B, Biological Sciences . 298 (1089): 199–209. Bibcode : 1982RSPTB.298..199S. doi : 10.1098/rstb.1982.0082. ISSN  0080-4622. PMID  6125971.
37. Чжан, Дж. (1994). «Представления в распределенных когнитивных задачах» (PDF) . Когнитивная наука . 18 : 87–122. doi :10.1016/0364-0213(94)90021-3.
38. Чжан, Цзяцзе; Вальджи, Мухаммад Ф. (2011). «TURF: На пути к унифицированной структуре удобства использования EHR». Журнал биомедицинской информатики . 44 (6): 1056–67. doi : 10.1016/j.jbi.2011.08.005 . PMID  21867774.
39. Бирс, SR; Розенберг, DR; Дик, EL; Уильямс, T.; О'Херн, KM; Бирмахер, B.; Райан, CM (1999). «Нейропсихологическое исследование функции лобной доли у детей, не знакомых с психотропными препаратами, с обсессивно-компульсивным расстройством». Американский журнал психиатрии . 156 (5): 777–9. doi :10.1176/ajp.156.5.777. PMID  10327915. S2CID  21359382.
40. Reid, CR; Sumpter, DJ; Beekman, M. (январь 2011 г.). «Оптимизация в естественной системе: аргентинские муравьи решают проблему ханойских башен». J. Exp. Biol . 214 (Pt 1): 50–8. CiteSeerX 10.1.1.231.9201 . doi :10.1242/jeb.048173. PMID  21147968. S2CID  18819977. 
41. Рассел, Эрик Фрэнк (апрель 1959). «Теперь вдохни». Повести. Поразительная научная фантастика . Т. 63, № 2. С. 31–77.
    • Перепечатано: Рассел, Эрик Фрэнк (2000). «Now Inhale». В Katze, Рик (ред.). Основные ингредиенты: Избранные рассказы Эрика Фрэнка Рассела . Фрамингем, Массачусетс: NESFA Press. стр. 399–417. ISBN 978-1-886778-10-8.
42. Bonanome, Marianna C.; Dean, Margaret H.; Dean, Judith Putnam (2018). "Self-like Groups". Выборка замечательных групп: Thompson's, Self-similar, Lamplighter и Baumslag-Solitar . Компактные учебники по математике. Cham, Швейцария: Springer. стр. 96. doi :10.1007/978-3-030-01978-5_3. ISBN 978-3-030-01976-1.
43. Birtwistle, Graham (январь 1985). «The coroutines of Hanoi». ACM SIGPLAN Notices . 20 (1): 9–10. doi :10.1145/988284.988286. S2CID  7310661.
44. "Четвертое измерение: Небесный игрушечный мастер". Доктор Кто . BBC One . Получено 2 апреля 2021 г.
45. "Башня Ханоя (концепция видеоигры)". Giantbomb.com . Получено 2010-12-05 .
46. "Tower of Hanoi / Andamiro". Sega Amusements. Архивировано из оригинала 2012-03-01 . Получено 2012-02-26 .

Внешние ссылки

• Вайсштейн, Эрик В. «Ханойская башня». MathWorld .